Задача линейного программирования в общем виде содержит три основных элемента модели:
- управляемые переменные;
- целевую функцию;
- ограничения на значения управляемых переменных.
При этом ограничения имеют вид неравенств или уравнений, связывающих управляемые переменные. В эти ограничения и целевую функцию управляемые переменные входят линейным образом.
Задача заключается в том, чтобы подобрать такие неотрицательные значения управляемых переменных, при которых целевая функция принимает наименьшее или наибольшее значение, причем выполняются все ограничения.
Таким образом, в общем виде задача формулируется следующим образом:
Найти неотрицательные значения переменных x 1, …, xn, при которых целевая функция
f = a 1 x 1+ … + anxn ® max (min),
причем выполняются ограничения вида
b 1 x 1+ … + bnxn = b;
c 1 x 1+ … + cnxn ≥ c;
d 1 x 1+ … + dnxn ≤ d.
Ограничения могут быть в любом количестве и иметь любой из приведенных видов или несколько видов. Впрочем, все ограничения можно привести к одному виду, а требование максимизации функции f заменить на требование минимизации противоположной функции – f, и наоборот.
Геометрический смысл задачи линейного программирования удобно проиллюстрировать для случая, когда имеются две управляемые переменные. Для удобства назовем их х и у.
Пусть одно из ограничений имеет вид 2 x – y ≥ 1. Чтобы изобразить соответствующую область на координатной плоскости, преобразуем уравнение к виду y ≤ 2 x – 1. Изображаем на рис.1 прямую y = 2 x – 1; искомая область – это полуплоскость, расположенная ниже этой прямой. Для удобства снабжаем прямую «бахромой», расположенной с той стороны, где находится заданная область.
Изобразим аналогично области, задаваемые остальными ограничениями (для наглядности считаем, что все ограничения являются неравенствами). Пересечение всех полуплоскостей образует некоторый выпуклый многоугольник, возможно, неограниченный. Хотя, возможно, пересечение окажется пустым, тогда задача является некорректной и не имеет решения. Если пересечение непустое, то назовем его допустимым многоугольником. Любая точка допустимого многоугольника определяет пару значений (x; y), для которых выполняются все ограничения задачи, и можно определить значение целевой функции для этих значений.
Рис.2
Рассмотрим теперь целевую функцию f. Для определенности возьмем
f = 2 x – 3 y, и пусть f → max. Рассмотрим всевозможные прямые вида
2 x – 3 y = a, где а меняет свои значения. Например, при а = 0 имеем прямую 2 x – 3 y = 0, или y = 2/3 x. Для произвольного а прямая имеет уравнение
y = 2/3 x – a /3. Все эти прямые параллельны друг другу. Можно сказать, что это одна прямая, двигающаяся параллельно самой себе с изменением а. В нашем случае при увеличении а прямая движется вниз.
Для любой точки прямой y = 2/3 x – a /3, пересекающей допустимый многоугольник, значение целевой функции f равно а. С увеличением а прямая опускается вниз. Если допустимый многоугольник ограничен, то в некоторый момент прямая дойдет до границы многоугольника. Соответствующей точке многоугольника и будет соответствовать максимальное значение целевой функции. Если же допустимый многоугольник неограничен, то возможно, что прямая все-таки достигнет его крайней точки, и задача будет иметь решение. Но возможно также, что прямую можно передвигать в соответствующем направлении неограниченно, и она все время будет пересекать допустимый многоугольник. В этом случае задача не будет иметь решения, так как целевую функцию можно увеличивать неограниченно.
Для решения задачи линейного программирования разработан симплекс-метод, заключающийся в построении специальных симплекс-таблиц. Но нет нужды разбирать его суть, так как созданы специальные компьютерные средства для решения этой задачи. Одно из этих средств разработано для программы EXCEL.
4. РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ СРЕДСТВАМИ EXCEL
Покажем решение задачи, имеющую следующую математическую формулировку.
Найти неотрицательные значения переменных Х1, Х2, Х3, Х4, Х5, при которых целевая функция
f = 9,3Х1 + 8,5Х2 +5,1Х3 + 1,4Х4 + 3,7Х5 ® min.
При этом выполняются ограничения на переменные:
0,93Х1 – 0,31Х2 + 0,42Х3 + 0,29Х4 + 0,3Х5 ≥ 7,9;
27Х1 + 53Х2 + 49Х3 + 7Х4 – 10Х5 ≥ 830;
– 3Х2 + 3Х3 + Х5 = 20;
0,87Х1 – 0,51Х2 + 0,53Х3 – 0,26Х4 – 0,42Х5 ≤ 7.
Запускаем EXCEL. Создаем в рабочем листе таблицу с коэффициентами ограничений и целевой функции. Дополняем таблицу строками и столбцами, показанными на рисунке 3, где граница исходной таблицы выделена жирной линией.
В ячейках столбца G вычисляются выражения, стоящие в левых частях ограничений и в целевой функции. Вводим в ячейку G4 формулу =СУММПРОИЗВ(B4:F4;B$9:F$9). Растягиваем ее вниз до ячейки G8, содержащей значение целевой функции.
Рис.3
Символы в столбце «Знак» не будут участвовать в вычислениях, они помогают в дальнейшем при задании ограничений. В столбце «Объем ограничений» указываем значения ограничений из математической модели.
В строке «Значения переменных», ячейках В9 – F9, содержатся значения управляемых переменных. На данном этапе их можно не заполнять, там по умолчанию стоят нули.
Все подготовлено для решения задачи.
Выбираем команду Сервис Þ Поиск решения. Откроется диалоговое окно, показанное на рис.4.
Рис.4
Заполняем поля Установить целевую ячейку и Изменяя ячейки, щелкнув на соответствующей ячейке таблицы или выделив диапазон ячеек. Устанавливаем переключатель в области Равной на Минимальному значению. Чтобы заполнить поле Ограничения, нажимаем клавишу Добавить. В результате откроется диалоговое окно Добавление ограничения на рис.5.
Рис.5
В поле Ссылка на ячейку вводим адреса ячеек из столбца «Формула», содержащего левые части ограничений. В поле Ограничение вводим соответствующие значения из столбца «Объем ограничения». В центральном поле ставим знак ограничения из раскрывающегося списка. Введя очередное ограничение, нажимаем Добавить, а введя последнее – ОК. В результате вернемся к заполненному диалоговому окну Поиск решения. С помощью клавиш Изменить и Удалить можем ввести коррективы в список ограничений.
Далее нажимаем клавишу Параметры. Откроется диалоговое окно Параметры поиска решения на рис.6. Здесь обязательно ставим флажок в поле Неотрицательные значения. Для ускорения работы программы ставим флажок в поле Линейная модель. Остальные поля можно не трогать. Нажимаем ОК.
Рис.6
Снова откроется диалоговое окно Поиск решения. Нажимаем клавишу Выполнить. В результате получим заполненную таблицу и откроется диалоговое окно Результаты поиска решения.
Рис.7
В поле Тип отчета активируем нужные нам типы отчета и нажимаем ОК. Полученное решение будет сохранено и создадутся три новых листа с указанными типами отчетов.
В Отчете по результатам будут показаны все результаты.
В Отчете по устойчивости показано, как могут изменяться параметры задачи, чтобы найденное оптимальное решение осталось без изменения.
В Отчете по пределам показано, как могут меняться значения переменных (каждое в отдельности, когда остальные зафиксированы), чтобы ограничения задачи продолжали выполняться, и как изменится при этом целевая функция.
Лабораторная работа
«Оптимизации количества удобрений, вносимых в поле»
Постановка задачи. Агроному необходимо определить количество органических и минеральных удобрений для подкормки зерновых культур таким образом, чтобы полная стоимость вносимых удобрений была минимальной. Стоимость и химический состав последних показаны ниже в таблице 1.
Таблица 1. Стоимость и химический состав удобрений
| Удобрение | Стоимость, руб/т | Азот, % | Фосфор, % | Калий, % |
| Органическое удобрение | 0,6 | 0,15 | 0,4 | |
| Аммофос | ||||
| Азофоска | ||||
| NPK | ||||
| Карбамид |
Минимальная потребность в элементах питания и площади посева культур приведены в следующей таблице.
Таблица 2. Потребность в питательных веществах и площади возделывания культур
| Озимая пшеница | Озимая рожь | Яровая пшеница | Яровой ячмень | Овес | |
| Азот, ц/га | 0,6 | 0,5 | 0,8 | 0,5 | 0,6 |
| Фосфор, ц/га | 0,7 | 0,7 | 0,6 | 0,5 | 0,6 |
| Калий, ц/га | 0,4 | 0,3 | 0,2 | 0,3 | 0,4 |
| Площадь, га | 220 + 10 а | 350 – 10 а | 190 + 10 а | 210 + 10 а | 420 – 20 а |
В наличии имеется 300 т органических удобрений, которые нужно израсходовать полностью. Количество минеральных удобрений нужно подобрать таким образом, чтобы их суммарная стоимость была минимальной.
Рис.8
Для решения задачи создаем рабочий лист EXCEL, внеся на него данные из таблиц, как показано на рис.8. Здесь обрабатывается информация по двум из пяти культур.
Управляемые переменные – это количество удобрений каждого вида, вносимых под каждую культуру. Их значения будут содержаться в массиве, заданном строками 9 – 10 и столбцами C – G. Названия строк и столбцов описывают назначение каждой ячейки.
Рассмотрим три столбца H, I, J, соответствующие озимой пшенице. Столбец «Выход» показывает, сколько питательного вещества каждого вида будет запланировано для внесения на поле, когда определятся значения в строке 9, соответствующей озимой пшенице. В ячейку Н5 вводим формулу =СУММПРОИЗВ($C5:$G5;$C$9:$G$9)/100 и растягиваем ее вниз на три ячейки. В столбце «Потребность» показана потребность поля в каждом питательном веществе. В ячейку J5 вводим формулу =I5*I$8 и растягиваем ее вниз на три ячейки. Аналогично заполняются столбцы, Соответствующие ржи, но управляемые переменные берутся из соответствующей строки 10.
В строке 11 подсчитывается общее количество удобрений каждого вида. В ячейку С11 вводим формулу =СУММ(C9:C10) и растягиваем ее до ячейки G11.
В ячейке Н12 подсчитывается общая стоимость удобрений, это значение целевой функции. Вводим в нее формулу
=СУММПРОИЗВ(C11:G11;C12:G12).
Теперь вызываем Сервис Þ Поиск решения. В открывшееся диалоговое окно вносим всю необходимую информацию. Ограничения по количеству питательных веществ можно вводить не по одному, а списком, выделяя по запросу нужные массивы.
Рис.9
Выполняем необходимые процедуры с кнопкой Параметры, нажимаем Выполнить и получаем решение задачи
Рис.10
Расчет по всем заданным культурам производим, дополнив таблицу соответствующими строками и столбцами.
Замечание. В полученном решении все органическое удобрение направлено под рожь. При желании можно его распределить принудительно, исключив переменные столбца С из списка управляемых. Можно также этот столбец разбить на два столбца: в одном распределить принудительно часть органического удобрения, а в другом оставшуюся часть распределить оптимально. В задаче можно также учесть не только стоимость удобрения, но и стоимость его внесения, что сделает решение более оптимальным.