Тема 1 Введение в линейное программирование

План

1 Исторический экскурс

2 Ограничения в модели ЛП

3 Графическое решение задачи ЛП

4 Графический анализ чувствительности.

1.1 Исторический экскурс

Своим рождением линейное программирование обязано Леониду Витальевичу Канторовичу, академику, лауреату Государственной (1949), Ленинской (1965) и Нобелевской (1975) премий по экономике. В 1938 году молодому (двадцатипятилетнему) математику, профессору Ленинградского университета Л.В.Канторовичу было предложено помочь фанерному тресту в решении задачи поиска наивыгоднейшего распределения работы восьми лущильных станков по пяти различным номенклатурам материалов при известной производительности каждого станка. Ученый решил эту задачу, а также нашел общее в постановке и решении ряда других (сходных с вышеуказанной) задач:

• как организовать производство, обеспечив максимальное выполнение плана при условии заданного ассортимента?

• как оптимальным образом раскроить материалы?

• как наиболее полно использовать механизмы?

• как оптимально распределить посевную площадь?

• как наилучшим образом выполнить план строительства при данных ресурсах?

• как составить оптимальный план перевозок?

Результаты своих исследований в данном направлении Л.В.Канторович изложил в монографии «Математические методы организации и планирования производства» (1939). Результаты данной работы сыграли огромную роль в оптимальном планировании и были впоследствии отмечены высшими наградами. В США метод линейного программирования был переоткрыт почти 10 лет спустя Дж.Данцигом и Т.Купмансом.

1.2 Ограничения в модели линейного программирования

В этом разделе на простом примере с двумя переменными показаны основные элементы модели линейного программирования (ЛП). Далее это пример будет обобщен в общую задачу ЛП.

Пример 1.1

Частная компания производит краску для внутренних и наружных работ из сырья двух типов: М1 и М2. Таблица 1.1 представляет основные данные для задачи.

Отдел маркетинга компании ограничил из-за спроса производство краски для внутренних работ до 2 тонн, а также поставил условие, чтобы ежедневное производство краски для внутренних работ не превышало более чем на тонну аналогичный показатель производства краски для внешних работ. Компания хочет определить оптимальное (наилучшее) соотношение между видами выпускаемой продукции для максимизации общего ежедневного дохода.

Таблица 1.1

	Расход сырья (в тоннах) на тонну краски		Максимально возможный ежедневный расход сырья
	для наружных работ	для внутренних работ
Сырье М1	6	4	24
Сырье М2	1	2	6
Доход на тонну краски (тыс.руб.)	5	4

Задача (модель) ЛП включает три основных элемента:

1. Переменные, которые следует определить.

2. Целевая функция, подлежащая оптимизации.

3. Ограничения, которым должны удовлетворять переменные.

Переменные модели:

х₁- ежедневный объем производства краски для наружных работ;

х₂- ежедневный объем производства краски для внутренних работ.

Используя эти переменные, далее строим целевую функцию. Логично предположить, что целевая функция (ЦФ), как суммарный ежедневный доход, должна возрастать при увеличении ежедневных объемов красок.

В соответствии с целями компании получаем задачу:

максимизировать z=5x₁+4x₂. (1.1)

Итак, остался не определенным последний элемент модели - условия (ограничения), которые должны учитывать ограниченные возможности ежедневного потребления сырья и ограниченность спроса на готовую продукцию. Другими словами, ограничения на сырье можно записать следующим образом:

(1.2)