Линейное программирование рассматривается не только как наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения [4], но и как специальный класс оптимизационных задач, в котором все отношения между переменными выражаются линейными функциями, а переменные принимают действительные значения [1]. Основоположниками линейного программирования считаются Л.В. Канторович (1912–1986) и Д. Данциг (1914–2005). Впервые задача линейного программирования (ЗЛП) в России была сформулирована в 1939 г. Л.В. Канторовичем, который применил математическую модель этой задачи в экономике и разработал метод решения. В 1975 г. Л.В. Канторович получил Нобелевскую премию за достижения в этой области [2]. В 1947 г. американский ученый Д. Данциг разработал алгоритм решения ЗЛП [1].
Математическая модель ЗЛП [4] имеет вид
(1)
(2)
Содержание ЗЛП формулируется следующим образом: необходимо найти набор действительных чисел (вектор) Хопт = (х1, х2, …, хn), доставляющий экстремум (максимум или минимум) линейной целевой функции (1) и удовлетворяющий системе ограничений (2). ЗЛП может иметь одно или множество оптимальных решений Хопт, которые называются альтернативным отпимумом [4]. Выявление альтернативного оптимума в решении ЗЛП представляется важным условием понимания существенных взаимосвязей, обеспечивающих достижение целевой функцией оптимального значения. При изучении ЗЛП с двумя переменными обязательно рассматривается графический способ ее решения. Критерием альтернативного оптимума в этом случае выступает совпадение оптимальной линии уровня целевой функции Lопт с одной из сторон многоугольника области допустимых решений (ОДР), а оптимальное решение Хопт находится по формуле
(3)
где Хопт1 и Хопт2 – оптимальные решения в угловых точках области допустимых решений (ОДР); 0 ≤ t ≤ 1; (хопт11; хопт12) и (хопт21; хопт22) – координаты угловых точек ОДР [4].
Развитие программного обеспечения современных компьютеров расширяет способы решения задач оптимизации в учебном процессе. Программа «Поиск решения» электронных таблиц Excel позволяет в автоматическом режиме находить только одно оптимальное решение Хопт и значение целевой функции L(Хопт) [3]. Если ЗЛП имеет единственное решение, то данная программа определяет его однозначно. Если ЗЛП имеет альтернативный оптимум, то пользователю становится известно одно частное решение. В отчете о результатах вычислений данная программа сигнализирует о множестве оптимальных решений, отмечая в статусе одной из функциональных зависимостей системы ограничений связанность с целевой функцией (если ЗЛП с двумя переменными имеет единственное решение, то связанность с целевой функцией фиксируется у двух функциональных зависимостей системы ограничений). Составление множества Хопт становится возможным, если моделируются ситуации, при которых обеспечивается достижение условий для использования формулы (3).
Проведем анализ математической модели ЗЛП с двумя переменными и альтернативным оптимумом, которая имеет следующий вид
(4)
(5)
Коэффициенты переменных в одном из неравенств системы ограничений пропорциональны коэффициентам целевой функции, что и определяет характерное расположение линии уровня целевой функции Lопт и одной из сторон М1М2 многоугольника ОДР (рис. 1).
Рис. 1.
Угловой коэффициент 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.
Рис. 2.
Четырехугольник М1М2М3М4 – это ОДР системы ограничений (9) (рис. 2), сторона М2М3 совпадает с оптимальной линией уровня целевой функции Lопт(Хопт) = 20. Координаты вершин М2(0; 2) и М3(2; 1) определяют оптимальные решения Хопт1 и Хопт2, а их подстановка в формулу (3) подтверждает ранее полученный результат Хопт (12). Нахождение множества оптимальных решений ЗЛП с двумя переменными при использовании программы «Поиск решения» требует соблюдения условий (составление и решение ЗЛП1 и ЗЛП2), рассмотренных в данной работе.