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

 

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

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

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

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

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

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

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

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

 

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

 

Предприятие может выпускать п видов продукции Р₁,Р₂,….., Р_п, располагая для этого т различными ресурсами R₁, R₂ ,…… R_m в количествах b₁, b₂,….,b_т соответственно. Известно, что для выпуска единицы продукции Р_j необходимо затратить a_ij единиц ресурса R_i (i = 1, 2,..., m - ресурсы; j = 1, 2,..., n – виды продукции). Кроме того, известен доход от продажи единицы каждого вида продукции — c₁, с₂,..., с _n соответственно, где c_j — стоимость единицы продукта Р_j, например 1 штуки, 1 тонны и т. п.

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

Для удобства дальнейших выводов и рассуждений сведем исходную информацию в единую табл. 2.1, где через x_j обозначим объемы продукции Р_j , выпускаемой предприятием. Тогда набор переменных (х₁, х₂,…., х_n) представляет собой не что иное, как производственную программу предприятия.

 

Доход, полученный предприятием при производстве продукта P_j в количестве x_j составит с_j x_j, а при реализации производственной программы (х₁, х₂,…., х_n) будет равен величине

Z = c₁x₁ + c₂x₂ +….+ с_jx_j +….... + с_nx_n.

 

Табл. 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

 

 

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

Ресурса R₁ потребуется: а₁₁x₁ + a₁₂x₂ +…..+а_1nx_n, в то время как в наличии имеется b₁.

Ресурса R₂ потребуется: а₂₁х₁ + a₂₂x₂ +…..+ а_2nx_n, в то время как в наличии имеется b₂.

………………………….

R_i – a_i1x₁ +………….+a_inx_n

………………………….

Ресурса R_m потребуется: a_m1x₁ + a_m2x₂ +..+ a_mnx_n, в то время как в наличии имеется b_m.

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

 

а₁₁x₁ + a₁₂x₂ +…..+а_1nx_n b₁

а₂₁х₁+ a₂₂x₂+…..+а_{2 n}x_n b₂

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

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

a_m1x₁ + a_m2x₂ +…..+ a_mnx_n b_m

 

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

x₁ > 0, x₂ > 0,..., х_n > 0.

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

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

 

Z = c₁x₁ + c₂x₂ +….+ с_jx_j +…....+ с_nx_n.

 

при условии, что переменные (х₁, х₂,…., х_n) удовлетворяют системе ограничений

а₁₁x₁ + a₁₂x₂ +…..+а_1nx_n b₁

а₂₁х₁ + a₂₂x₂ +…..+а_{2 n}x_n b₂

……………………………

……………………………

a_m1x₁ + a_m2x₂ +…..+ a_mnx_n b_m

 

x₁ > 0, x₂ > 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_в + c_C • x_C

или

Z = 10х_А + 12х_в + 8x_C

Подсчитаем расходы ресурсов, необходимые для выполнения производственной программы х_А, х_в, х_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,1x_C человеко-часов при запасе 1600 человеко-часов. Следовательно, при поиске оптимальной программы должно выполняться условие

0,3х_А + 0,2х_в + 0.1x_C 1600.

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

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

Z = 10х_А + 12х_в + 8x_C

 

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

 

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

0,2х_А + 0,7х_в + 0,3х_C 2300.

0,3х_А + 0,2х_в + 0.1x_C 1600.

 

х_А 0, х_в 0, х_C 0

 

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

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

 

Медициной установлена суточная потребность организма в питательных веществах Т₁ Т₂,,..., Т_т (белки, жиры, углеводы и т.д.), а именно: человеку они необходимы в количествах не менее, чем b₁, b₂,…, b_т некоторых условных единиц (например, мг). В продаже имеются продукты питания П₁, П₂,..., П_n, стоимость которых известна и равна c₁, с₂.,…., c_n,соответственно (с_j — стоимость единицы продукта П_j, например 1 кг, 1 л, 1 упаковки и т.д.). Известно также, что питательное вещество T_i содержится в единице продукта П_j в количестве а_{i j} единиц (i = 1, 2,..., т; j = 1, 2,..., n).

Требуется составить продуктовую корзину с минимальной стоимостью, т.е. определить количество продуктов каждого вида (x₁, х₂.,….., х_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. Тогда для некоторого продуктового набора (х₁, х₂,….., х_n)

Z =c₁x₁ +c₂x₂ +…….+c_nx_n.

 

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

• Вещества T₁ содержится: а₁₁x₁, + а₁₂ х₂ +... + а_1nх_n,в то время как его должно быть не менее чем b₁.

• Вещества Т₂содержится: a₂₁x₁ + a₂₂x₂ + … + a_2nx_n,в то время как его должно быть не менее чем b₂.

• …………………………

• Вещества Т_mсодержится: a_mlx₁ + a_m2x₂ +... + а_mnх_n, в то время как его должно быть не менее чем b_т.

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

 

x₁ 0, x₂ 0, …….,x_n 0

 

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

 

Z =c₁x₁ +c₂x₂ +…….+c_nx_n.

 

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

 

а₁₁x₁, + а₁₂ х₂ +... + а_1nх_n b₁

а₁₁x₁, + а₁₂ х₂ +... + а_1nх_n b₂

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

a_mlx₁ + a_m2x₂ +... + а_mnх_n b_m

 

x₁ 0, x₂ 0, …….,x_n 0

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

 

Пример 2.2.

 

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

 

Табл. 2.4.

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

 

Решение

 

Обозначим через x₁ х₂, х₃, х₄ количество (в кг) приобретаемых продуктов каждого вида. Тогда стоимость продуктового набора будет равна

Z = 45х₁, + 60x₂ + 70х₃ + 80х₄.

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

x₁+ 2х₃+ 5х₄ 50.

 

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

Кроме того, переменные x₁, х₂, х₃, х₄ не могут быть отрицательными числами.

 

Объединяя полученные результаты, получаем следующую оптимизационную задачу: необходимо найти такой набор значений переменных x₁, х₂, х₃, х₄ (количество продуктов каждого вида), который обращает целевую функцию (стоимость продуктового набора) в минимум:

Z = 45х₁, + 60x₂ + 70х₃ + 80х₄ min

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

x₁ + 0 x₂ + 2x₃ + 5x₄ 50

3 x₁ + 5 x₂ + 0x₃ + 4x₄ 60

0 x₁ + 4 x₂ + 7x₃ + 0x₄ 40

x₁ 0, x₂ 0, х₃ 0, х₄ 0.

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

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

 

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

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

x_k d_k

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

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