Линейное программирование. 1. введение в линейное программирование
![]()
|
1.ВВЕДЕНИЕ В ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕЛинейное программирование (ЛП) – это метод оптимизации моделей, в которых целевые функции и ограничения строго линейны. ЛП успешно применяется в военной области, индустрии, сельском хозяйстве, транспортной отрасли, экономике, системе здравоохранения и даже в социальных науках. Задача, в которой требуется найти экстремум функции ![]() при ограничениях: ![]() ![]() ![]() ![]() называется задачей линейного программирования. Задача в краткой записи имеет вид ![]() ![]() ![]() ![]() 1.1.Модели линейного программирования с двумя |
| Расход сырья (в тоннах) на тонну краски | Максимально возможный ежедневный расход сырья | |
Для наружных работ | Для внутренних работ | ||
Сырье С1 | 6 | 4 | 24 |
Сырье С2 | 1 | 2 | 6 |
Доход (в тыс. долл.) на тонну краски | 5 | 4 | |
Отдел маркетинга компании ограничил ежедневное производство краски для внутренних работ до 2 т (из-за отсутствия надлежащего спроса), а также поставил условие, чтобы ежедневное производство краски для внутренних работ не превышало более, чем на 1 т аналогичный показатель производства краски для внешних работ. Компания хочет определить оптимальное (наилучшее) соотношение между видами выпускаемой продукции для максимизации общего ежедневного дохода.
Задача (модель) линейного программирования (ЗЛП), как и любая задача исследования операций, включает три основных элемента.
Переменные, которые следует определить.
Целевая функция, подлежащая оптимизации.
Ограничения, которым должны удовлетворять переменные.
Определение переменных – первый шаг в создании модели. В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ. Обозначим эти объемы как переменные модели:
![](1057295_html_3596e9b404ee33e.gif)
![](1057295_html_ddd88c38ef9a1b74.gif)
Используя эти переменные, далее строим целевую функцию. Логично предположить, что целевая функция, как суммарный ежедневный доход, должна возрастать при увеличении ежедневных объемов производства красок. Обозначим эту функцию через z (она измеряется в тысячах долларов) и положим, что
![](1057295_html_8c619f74044b42a5.gif)
В соответствии с целями компании получаем задачу:
Максимизировать
![](1057295_html_8c619f74044b42a5.gif)
![](1057295_html_7b216f37f5aaf034.gif)
Итак, остался не определенным последний элемент модели условия (ограничения), которые должны учитывать ограниченные возможности ежедневного потребления сырья и ограниченность спроса на готовую продукцию. Другими словами, ограничения на сырье можно записать следующим образом.
![](1057295_html_41f05f83c4f1bf03.png)
Из таблицы с данными имеем следующее.
Используемый объем сырья
![](1057295_html_d6c48a8b1329f0b7.gif)
Используемый объем сырья
![](1057295_html_1035ea867c261622.gif)
Поскольку ежедневный расход сырья С1 и С2 ограничен соответственно 24 и 6 тоннами, получаем следующие ограничения.
![](1057295_html_55ef31e780fc0b52.gif)
![](1057295_html_518649e4716770e8.gif)
Существует еще два ограничения по спросу на готовую продукцию:
максимальный ежедневный объем производства краски для внутренних работ не должен превышать 2 т, т.е.
![](1057295_html_ade1a9a6e595bcb7.gif)
ежедневный объем производства краски для внутренних работ не должен превышать ежедневный объем производства краски для наружных работ более чем на одну тонну (разность между ежедневными объемами производства красок для внутренних и наружных работ не должна превышать одной тонны), т.е.
![](1057295_html_85bcc02a62a57bf2.gif)
Еще одно неявное ограничение состоит в том, что переменные
![](1057295_html_d8403e25811896f8.gif)
![](1057295_html_f431a0b60f31844b.gif)
Таким образом, к сформулированным выше ограничениям необходимо добавить условие неотрицательности переменных:
![](1057295_html_f704424159c52516.gif)
![](1057295_html_44c78fd1ece21223.gif)
Максимизировать
![](1057295_html_8c619f74044b42a5.gif)
![](1057295_html_2e5cc6dc692e9a0c.gif)
при выполнении следующих ограничений:
![](1057295_html_f3442d5c92848793.gif)
![](1057295_html_f5db419160f8bf96.gif)
![](1057295_html_94034934a9b6f05e.gif)
![](1057295_html_56da2a637edc590e.gif)
![](1057295_html_f704424159c52516.gif)
![](1057295_html_44c78fd1ece21223.gif)
Любое решение, удовлетворяющее ограничениям модели, является допустимым. Например, решение
![](1057295_html_50a80b54d4e2b33a.gif)
![](1057295_html_9b7fd08aec9114d8.gif)
![](1057295_html_a72998a5730306e3.gif)
![](1057295_html_b7b428d338f90c3a.gif)
![](1057295_html_2adb9ad2d43290b2.gif)
Итак, задача сформулирована.
Теперь встает вопрос о нахождении оптимального допустимого решения, доставляющего максимум целевой функции. После некоторых раздумий приходим к выводу, что задача имеет много (фактически, бесконечно много) допустимых решений. По этой причине невозможна подстановка значений переменных для поиска оптимума, т.е. нельзя применить простой перебор всех допустимых решений. Следовательно, необходима эффективная процедура отбора допустимых решений для поиска оптимального.