Классические задачи линейного программирования

 

Задачи линейного программирования (ЗЛП) впервые были сформулированы в 30-х годах прошлого столетия. Большая роль в создании теории и разработке методов их решения принадлежит российским ученым: А. Н. Толстому (первая постановка задачи по формированию оптимального плана перевозок — 1930 г.), академику JI.B. Канторовичу (систематические исследования и разработка общих методов решения — 1939 г.). М.К. Гавурину (метод потенциалов для решения транспортных задач — совместно с Л. В. Канторовичем в 1949 г.), В. В. Новожилову, А.Р. Лурье, академику А. Г. Аганбегяну, Д. Б. Юдину и многим другим. Среди зарубежных ученых необходимо отметить Б. Эгервари, Г.У. Куна (задачи о назначениях, транспортная задача, «венгерский метод» — 1931 г.), Дж. Данцига (автор симплекс-метода — 1947-1949 гг.).

Модели линейного программирования отличаются наглядностью и относительной простотой. Их использование во многих практически важных задачах, связанных с принятием решений, оказалось высокоэффективным, в связи с чем они получили до­вольно широкое распространение. К числу наиболее известных задач линейного программирования относятся:

1. задачи о распределении ограниченных ресурсов (задачи оптимального планирования);

2. задачи об оптимальной корзине продуктов (задачи о диете, задачи оптимального смешения);

3. задачи оптимального раскроя (материалов, заготовок);

4. транспортные задачи;

5. задачи о назначениях.

В теории линейного программирования перечисленные задачи часто называют классическими. Их традиционно считают «базовыми», или основными, поскольку большинство реальных управленческих ситуаций, сформулированных в терминах линейного программирования, как правило, относятся к одному из вышеприведенных типов.

 

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

 

Предприятие может выпускать п видов продукции Р12,….., Рп , располагая для этого т различными ресурсами R1, R2 ,…… Rm в количествах b1, b2 ,….,bт соответственно. Известно, что для выпуска единицы продукции Рj необходимо затратить aij единиц ресурса Ri (i = 1, 2,..., m - ресурсы;j = 1, 2,..., n – виды продукции). Кроме того, известен доход от продажи единицы каждого вида продукции — c1, с2,..., сn соответственно, где cj — стоимость единицы продукта Рj, например 1 штуки, 1 тонны и т. п.

Требуется так спланировать производственную программу — объемы выпуска каждого вида продукции (в штуках, тоннах и т.п.), — чтобы максимизировать доход предприятия.

Для удобства дальнейших выводов и рассуждений сведем исходную информацию в единую табл. 2.1, где через xj обозначим объемы продукции Рj , выпускаемой предприятием. Тогда набор переменных (х1, х2,…., хn) представляет собой не что иное, как производственную программу предприятия.

 

Доход, полученный предприятием при производстве продукта Pj в количестве xj составит сj xj , а при реализации производственной программы (х1, х2,…., хn) будет равен величине

Z = c1x1 + c2x2 +….+ сjxj +….... + сnxn.

 

Табл. 2.1.

  Продукция   Запасы ресурсов
P1 P2 …….Pj Pn
Объемы выпуска
x1 x2 ……xj xn
R1 a11 a12 …… a1n b1
R2 a21 a22 …….. a2n b2
…….Ri aij ……bi
Rm am1 am2 ……. amn bm
Доход c1 c2 ……cj cn

 

 

Подсчитаем, какое количество ресурсов будет израсходовано, если выбрать некоторый план (х1, х2,…., хn).

Ресурса R1 потребуется: а11x1 + a12x2 +…..+а1nxn, в то время как в наличии имеется b1.

Ресурса R2 потребуется: а21х1 + a22x2 +…..+ а2nxn , в то время как в наличии имеется b2.

………………………….

Ri – ai1x1 +………….+ainxn

………………………….

Ресурса Rm потребуется: am1x1 + am2x2 +..+amnxn , в то время как в наличии имеется bm.

Очевидно, что производственная программа может быть выполнена только в том случае, если имеющихся ресурсов окажется достаточно, т. е. при выполнении условий

 

а11x1 + a12x2 +…..+а1nxn b1

а21х1+ a22x2+…..+а2nxn b2

………………………………

………………………………

am1x1 + am2x2 +…..+amnxn bm

 

Кроме того, понятно, что переменные решения х1, х2,…., хn должны быть неотрицательными числами, т. е.

x1 > 0, x2 > 0,..., хn > 0.

Объединяя полученные результаты, получаем следующую задачу линейного программирования.

Требуется найти совокупность значений 1, х2,…., хn), обращающих в максимум целевую функцию

 

Z = c1x1 + c2x2 +….+ сjxj +…....+ сnxn.

 

при условии, что переменные 1, х2,…., хn) удовлетворяют системе ограничений

а11x1 + a12x2 +…..+а1nxn b1

а21х1 + a22x2 +…..+а2nxn b2

……………………………

……………………………

am1x1 + am2x2 +…..+amnxn bm

 

x1 > 0, x2 > 0,..., хn > 0.

 

Пример 2.1.

Химическая фабрика выпускает три разновидности стирального порошка марок А, В, С. Доход от реализации 1 кг порошка каждого наименования известен и составляет, соответственно, сА = 10, сВ = 12, сС= 8 руб. Недельные запасы и удельные расходы ресурсов, необходимых для производства 1 кг порошка каждой марки, приведены в табл. 2.2.

Табл. 2.2.

Ресурсы, необходимые для производства Марка стирального порошка Недельные запасы ресурсов
А В С
Сырье, кг 1,4 1,2 1,5
Оборудование, (нормо-часы) 0,2 0,7 0,3
Трудозатраты, (человеко-часы) 0,3 0,2 0,1

 

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

Решение

Обозначим через хА, хв, хС недельные объемы выпуска стиральных порошков марок А, В, С (кг). Тогда доход от реализации порошков при производственной программе хА, хв, хС

 

Z = cА • хА + св • xв + cC • xC

или

Z = 10хА + 12хв + 8xC

Подсчитаем расходы ресурсов, необходимые для выполнения производственной программы хА, хв, хC.

• Сырья будет израсходовано 1,4хА + 1,2хв + 1,5хC (кг) при запасе, равном 15 000 кг. Следовательно, для того чтобы программу можно было реализовать, необходимо выполнить условие

1,4ха + 1,2хв + 1,5хC 15 000.

• Расход ресурса «оборудование» составит 0,2хА + 0,7хв + 0,3хC нормо-часов при запасе 2300 нормо-часов. Следовательно, при выборе производственной программы необходимо выполнить условие

0,2хА + 0,7хв + 0,3хC 2300.

• Расход ресурса «трудозатраты» составит 0,3хА + 0,2хв + 0,1xC человеко-часов при запасе 1600 человеко-часов. Следовательно, при поиске оптимальной программы должно выполняться условие

0,3хА + 0,2хв + 0.1xC 1600.

• Кроме того, переменные хА, хВ хC не могут принимать отрицательных значений, т. е. хА > 0, хв > 0, хC > 0.

Объединяя результаты, получаем следующую задачу линейного программирования. Необходимо сформировать такую производственную программу (хА, хв, xC) (определить объемы выпуска продукции каждой марки), при которой целевая функция (доход от реализации)

Z = 10хА + 12хв + 8xC

 

будет максимальной, при условии, что переменные хА, хв, xC удовлетворяют системе ограничений

 


1,4ха + 1,2хв + 1,5хC 15 000.

0,2хА + 0,7хв + 0,3хC 2300.

0,3хА + 0,2хв + 0.1xC 1600.

 

хА 0, хв 0, хC 0

 

Заметим, что и целевая функция, и ограничения в рассмотренном примере линейны относительно переменных хА, хв, xC. Следовательно, это задача линейного программирования.

Задача об оптимальной корзине продуктов (задача о диете)

 

Медициной установлена суточная потребность организма в питательных веществах Т1 Т2, ,..., Тт (белки, жиры, углеводы и т.д.), а именно: человеку они необходимы в количествах не менее, чем b1 , b2 ,…, bт некоторых условных единиц (например, мг). В продаже имеются продукты питания П1 , П2 ,..., Пn , стоимость которых известна и равна c1 , с2.,…., cn ,соответственно (сj — стоимость единицы продукта Пj, например 1 кг, 1 л, 1 упаковки и т.д.). Известно также, что питательное вещество Ti содержится в единице продукта Пj в количестве аi j единиц (i = 1, 2, ..., т; j = 1, 2,..., n).

Требуется составить продуктовую корзину с минимальной стоимостью, т.е. определить количество продуктов каждого вида (x1, х2.,….., хn), которые следует приобрести, для того чтобы, с одной стороны, удовлетворить суточную потребность организма в питательных веществах, а с другой — израсходовать минимум средств. Исходная информация, необходимая для формулировки задачи, приведена в табл. 2.3.

 

Табл. 2.3.

Необходимые питательные вещества Продукты питания   Минимально необходимая потребность
П1 П2 …….Пj Пn
 
x1 x2 ……xj xn
Т1 a11 a12 ……. a1n b1
Т2 a21 a22 …… a2n b2
…….Тi     …aij   ……bi
Тm am1 am2 ……. amn bm
Стоимость единицы продукта c1 c2 ……cj cn  

 

Обозначим стоимость искомой корзины через Z. Тогда для некоторого продуктового набора (х1, х2,….., хn)

Z =c1x1 +c2x2 +…….+cnxn.

 

Подсчитаем количество каждого питательного вещества Ti , i = 1, 2,..., т, содержащегося в корзине (х1, x2,……xn).

• Вещества T1 содержится: а11x1, + а12 х2 + ... + а1nхn ,в то время как его должно быть не менее чем b1.

• Вещества Т2содержится: a21x1 + a22x2 + … + a2nxn ,в то время как его должно быть не менее чем b2.

• …………………………

• Вещества Тmсодержится: amlx1 + am2x2 + ... + аmnхn , в то время как его должно быть не менее чем bт.

• Кроме того, из смысла задачи следует, что переменные решения х1, х2,….., хn не могут быть отрицательными числами, т. е.

 

x1 0, x2 0, …….,xn 0

 

В результате приходим к следующей задаче линейного программирования: необходимо найти такой набор значений для переменных (х1, х2,….., хn), которые обращают в минимум целевую функцию

 

Z =c1x1 +c2x2 +…….+cnxn.

 

и одновременно удовлетворяют системе ограничений

 

а11x1, + а12 х2 + ... + а1nхn b1

а11x1, + а12 х2 + ... + а1nхn b2

…………………………………

amlx1 + am2x2 + ... + аmnхn bm

 

x1 0, x2 0, …….,xn 0

Как и ранее, целевая функция и ограничения линейны, следовательно, это задача линейного программирования.

 

Пример 2.2.

 

Месячная потребность организма в витаминах и питательных веществах А, В, С указана в табл. 2.4 (значения условные). Содержание А, В, С в 1 кг доступных покупателю фруктов — яблок, апельсинов, бананов и лимонов — приведено в табл. 2.4. Требуется построить оптимизационную модель, с помощью которой можно решить, какие продукты и в каких количествах следует покупать для удовлетворения потребности организма в витаминах и питательных веществах А, В, С, при условии, что стоимость продуктового набора должна быть минимальной.

 

Табл. 2.4.

Микроэлементы и витамины Продукты   Потребность
x1 x2 x3 x4
А
В
С
Цена за 1 кг  

 

Решение

 

Обозначим через x1 х2, х3, х4 количество (в кг) приобретаемых продуктов каждого вида. Тогда стоимость продуктового набора будет равна

Z = 45х1, + 60x2 + 70х3 + 80х4.

Содержание А в продуктовом наборе будет равно х1+ 0 x2 + 2х3 + 5х4. Причем, согласно требованиям, его количество должно быть не менее 50 условных единиц. Тогда получаем первое ограничивающее условие:

x1+ 2х3+ 5х4 50.

 

Рассуждая аналогично, получим ограничивающие условия по другим компонентам.

Кроме того, переменные x1 , х2 , х3, х4 не могут быть отрицательными числами.

 

Объединяя полученные результаты, получаем следующую оптимизационную задачу: необходимо найти такой набор значений переменных x1, х2, х3, х4 (количество продуктов каждого вида), который обращает целевую функцию (стоимость продуктового набора) в минимум:

Z = 45х1, + 60x2 + 70х3 + 80х4 min

и при этом удовлетворяет системе ограничений

x1 + 0 x2 + 2x3 + 5x4 50

3 x1 + 5 x2 + 0x3 + 4x4 60

0 x1 + 4 x2 + 7x3 + 0x4 40

x1 0, x2 0, х3 0, х4 0.

Так как и целевая функция, и ограничения линейны, это задача линейного программирования.

Формы записи задач ЛП

 

Несмотря на различие формулировок, в рассмотренных задачах много общего, а именно: линейность целевой функции и ограничений, а также условие неотрицательности переменных. Отличие заключается в знаках неравенств и целях оптимизации: в одном случае требуется максимизировать целевую функцию, в другом — минимизировать.

Что касается знака неравенств в ограничениях (больше, меньше или равно), то в задачах как первого, так и второго типа они могут быть любыми, в зависимости от реальных условий. Например, при формировании производственной программы часто необходимо учесть условия уже подписанных контрактов, например: продукцию Рк нужно поставить в количестве не менее чем dk. Тогда к системе ограничений по ресурсам будет добавлено дополнительное ограничение по выполнению контрактных обязательств:

xk dk

Если ставится требование израсходовать один из ресурсов полностью, то соответствующее ограничение будет записано в виде равенства. В общем случае задачи линейного программирования могут содержать ограничения как в виде неравенств разных знаков, так и в виде равенств.

При решении задач современными стандартными программными средствами в Excel или с помощью других специализированных пакетов выполнять процедуры приведения моделей к некоторому стандартному виду, как правило, не требуется.