Нахождение альтернативного максимума задачи линейного программирования с помощью программы "Поиск решения"

Размещено на http://www.allbest.ru//

1

Размещено на http://www.allbest.ru//

Нахождение альтернативного максимума задачи линейного программирования с помощью программы «Поиск решения»

Овчинникова О.И.

Линейное программирование рассматривается не только как наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения [4], но и как специальный класс оптимизационных задач, в котором все отношения между переменными выражаются линейными функциями, а переменные принимают действительные значения [1]. Основоположниками линейного программирования считаются Л.В. Канторович (1912-1986) и Д. Данциг (1914-2005). Впервые задача линейного программирования (ЗЛП) в России была сформулирована в 1939 г. Л.В. Канторовичем, который применил математическую модель этой задачи в экономике и разработал метод решения. В 1975 г. Л.В. Канторович получил Нобелевскую премию за достижения в этой области [2]. В 1947 г. американский ученый Д. Данциг разработал алгоритм решения ЗЛП [1].

Математическая модель ЗЛП [4] имеет вид

Содержание ЗЛП формулируется следующим образом: необходимо найти набор действительных чисел (вектор) Хопт = (х1, х2, …, хn), доставляющий экстремум (максимум или минимум) линейной целевой функции (1) и удовлетворяющий системе ограничений (2). ЗЛП может иметь одно или множество оптимальных решений Хопт, которые называются альтернативным отпимумом [4]. Выявление альтернативного оптимума в решении ЗЛП представляется важным условием понимания существенных взаимосвязей, обеспечивающих достижение целевой функцией оптимального значения. При изучении ЗЛП с двумя переменными обязательно рассматривается графический способ ее решения. Критерием альтернативного оптимума в этом случае выступает совпадение оптимальной линии уровня целевой функции Lопт с одной из сторон многоугольника области допустимых решений (ОДР), а оптимальное решение Хопт находится по формуле

где Хопт1 и Хопт2 - оптимальные решения в угловых точках области допустимых решений (ОДР); 0 ? t ? 1; (хопт11; хопт12) и (хопт21; хопт22) - координаты угловых точек ОДР [4].

Развитие программного обеспечения современных компьютеров расширяет способы решения задач оптимизации в учебном процессе. Программа «Поиск решения» электронных таблиц Excel позволяет в автоматическом режиме находить только одно оптимальное решение Хопти значение целевой функции L(Хопт) [3]. Если ЗЛП имеет единственное решение, то данная программа определяет его однозначно. Если ЗЛП имеет альтернативный оптимум, то пользователю становится известно одно частное решение. В отчете о результатах вычислений данная программа сигнализирует о множестве оптимальных решений, отмечая в статусе одной из функциональных зависимостей системы ограничений связанность с целевой функцией (если ЗЛП с двумя переменными имеет единственное решение, то связанность с целевой функцией фиксируется у двух функциональных зависимостей системы ограничений). Составление множества Хопт становится возможным, если моделируются ситуации, при которых обеспечивается достижение условий для использования формулы (3).

Проведем анализ математической модели ЗЛП с двумя переменными и альтернативным оптимумом, которая имеет следующий вид

(4)

(5)

Коэффициенты переменных в одном из неравенств системы ограничений пропорциональны коэффициентам целевой функции, что и определяет характерное расположение линии уровня целевой функции Lопт и одной из сторон М1М2 многоугольника ОДР (рис. 1).

Размещено на http://www.allbest.ru//

1

Размещено на http://www.allbest.ru//

Рис. 1. Граница ОДР (ОДР располагается ниже отрезка М1М2)

Угловой коэффициент k прямой Lопт равен отношению коэффициентов целевой функции (k = c2/c1). Если увеличить c1 на положительную величину д, а c2 оставить без изменения, то линия уровня Lопт совершит поворот по ходу часовой стрелки и примет положение, которое на рис. 1 отмечено как Lопт2. При таком изменении целевой функции (4) ЗЛП будет иметь одно оптимальное решение, которому будут соответствовать значения координат точки М2 (рис. 1). Если увеличить c2 на положительную величину д, а c1 оставить без изменения, то линия уровняLопт совершит поворот против хода часовой стрелки и примет положение, которое на рис. 1 отмечено как Lопт1. При этом изменении целевой функции (4) ЗЛП будет иметь также одно оптимальное решение, которому будут соответствовать значения координат точки М1 (рис. 1). Нахождение координат точек М1 и М2, которые являются угловыми в ОДР, позволяет составить множество Хопт при использовании формулы (3). Установление Хопт ЗЛП, заданной математической моделью (4)-(5), с помощью программы «Поиск решения» требует определения Хопт1 и Хопт2, которые относятся к ЗЛП1 и ЗЛП2. Система ограничений ЗЛП1 и ЗЛП2 описывается системой неравенств (5). Математические модели целевых функций L1(X) и L2(X) этих задач соответственно будут иметь вид

(6)(7)

Иллюстрация изложенной выше идеи о применении программы «Поиск решения» для нахождения альтернативного максимума осуществляется на примере решения ЗЛП, которая представлена математической моделью

(8)

(9)

Функциональные зависимости (8) и (9) вводятся в ячейки электронного процессора Excel, а в соответствующих разделах диалогового окна программы «Поиск решения» фиксируются их адреса. Автоматический поиск Хопт и L(Хопт) завершается сообщением результата: х1 = 0,8; х2 = 1,6; L(0,8; 1,6) = 20. Для определения Хопт1 и Хопт2 следует составить ЗЛП1 и ЗЛП2 с единой ОДР, которая описывается системой неравенств (9). Величине д можно, например, присвоить значение, равное 0,5. Математические модели целевых функций L1(x1; x2) и L2(x1; x2) соответственно для ЗЛП1 и ЗЛП2 составляются по формулам (6), (7) и принимают с учетом выбранной д следующий вид

(10)

(11)

Результат работы программы «Поиск решения» для ЗЛП1 и ЗЛП2: Хопт1 = (0; 2), L1(0; 2) = 21, Хопт2 = (2; 1), L2(2; 1) = 21. Нахождение Хопт1 и Хопт2 позволяет записать множество всех оптимальных решений ЗЛП (8)-(9) по формуле (3) в матричном виде

Проверка полученного результата (12) может проводиться через его сравнение с результатом, к которому приведет применение другого способа решения ЗЛП. Использование графического способа решения [4] ЗЛП (8)-(9) отражено на рис. 2.

альтернативный задача линейный программирование

Размещено на http://www.allbest.ru//

1

Размещено на http://www.allbest.ru//

Рис. 2. Линия уровня целевой функции Lопт и ОДР

Четырехугольник М1М2М3М4 - это ОДР системы ограничений (9) (рис. 2), сторона М2М3 совпадает с оптимальной линией уровня целевой функции Lопт(Хопт) = 20. Координаты вершин М2(0; 2) и М3(2; 1) определяют оптимальные решения Хопт1 и Хопт2, а их подстановка в формулу (3) подтверждает ранее полученный результат Хопт (12). Нахождение множества оптимальных решений ЗЛП с двумя переменными при использовании программы «Поиск решения» требует соблюдения условий (составление и решение ЗЛП1 и ЗЛП2), рассмотренных в данной работе.

Список литературы

Алексеева Е.В. Построение математических моделей целочисленного линейного программирования. Примеры и задачи: учеб. пособие / Новосиб. Гос. ун-т. Новосибирск, 2012. 131 с.

Вершик А.М. Леонид Витальевич Канторович: человек и ученый: В 2 т. Новосибирск:

Изд-во СО РАН. Филиал «Гео», 2002. Т.1.

Вуколов Э.А. Основы статистического анализа. Практикум по статситическим методам и исследованию операций с использованием пакетов STATISTICA и EXCEL: учеб. пособие. - 2-е изд,, испр. и доп. - М.: ФОРУМ, 2008. 464 с.

Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании: учеб. пособие. Издательство: Дело, 2008 г. 688 с.

Размещено на Allbest.ru