Типовые задачи, решаемые методами линейного программирования

Круг задач, решаемых при помощи методов линейного программирования достаточно широк:

· задача об оптимальном использовании ресурсов при производственном планировании;

· задача о смесях (планирование состава продукции);

· задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");

· транспортные задачи (анализ размещения предприятия, перемещение грузов).

1.Задача об оптимальном использовании ресурсов при производственном планировании. Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида ( ). Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, bi и cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей.

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

3. Транспортная задача. Под транспортной задачей понимают целый ряд задач, имеющих определенную специфическую структуру. Наиболее простыми транспортными задачами являются задачи о перевозках некоторого продукта из пунктов отправления в пункты назначения при минимальных затратах на перевозку. Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно. Обычно начальные условия транспортной задачи записывают в так называемую транспортную таблицу. В ячейках таблицы в левом верхнем углу записывают показатели затрат (расходы по доставке единицы продукта между соответствующими пунктами), под диагональю каждой ячейки размещается величина поставки xij (т.е. xij - количество единиц груза, которое будет перевезено от i-го поставщика j-му потребителю). Необходимо определить наиболее дешевый вариант перевозок, при этом каждый поставщик должен отправить столько груза, сколько имеется у него в запасе, а каждый потребитель должен получить нужное ему количество продукции.

Задача (модель) линейного программирования, как и любая задача исследования операций, включает три основных элемента:

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

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

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

В общем виде модель записывается следующим образом.

Целевая функция:

c1x1 + c2x2 + ... + cnxn → max(min)

(1.1)

Ограничения:

a11x1 + a12x2 + ... + a1nxn {≤ = ≥} b1, a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2, ... am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm

(1.2)

Требование неотрицательности:

xj ≥ 0

(1.3)

При этом aij, bi, cj() - заданные постоянные величины. Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3). Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми. Вектор, удовлетворяющий ограничениям (1.2) и (1.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (1.1) достигает своего максимального (минимального) значения, называется оптимальным.

Пример решения задачи линейного программирования

Рассмотрим на конкретном примере.Для изготовления изделий A, B, C и D, фабрика расходует в качестве сырья сталь и цветные металлы, имеющиеся в ограниченном количестве. Указанные изделия производят спомощью токарных и фрезерных станков. Определить план выпуска продукции, при котором будет достигнута максимальная прибыль. Необходимые данные приведены в таблице:

Вид ресурса	Объем ресурса	Нормы расхода на одно изделие
A	B	C	D
Сталь, кг
Цв. Металлы, кг
Токарные станки, станко-час
Фрезерные станки, станко-час
Прибыль, ден. ед.

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

2) сформулировать в экономических терминах двойственную задачу и составить еематематическую модель;

3) используя решение исходной задачи и соответствие между двойственными переменными, найти компоненты оптимального плана двойственной задачи — двойственные оценки у*_i;

4) указать наиболее дефицитный и недефицитный (избыточный) ресурс, если он имеется;

5) с помощью двойственных оценок у_i* обосновать рациональность оптимального плана, сопоставив оценку затрат f_min израсходованных ресурсов и максимальный доход z_maxот реализации готовой продукции по всему оптимальному плану и по каждому виду продукции в отдельности;

6) построить матрицу взаимозаменяемости ресурсов;

7) оценить целесообразность приобретения ∆b_k = 3 единиц ресурса Р_kпо цене с_k=0,5 (к=3) за единицу;

8) установить размеры максимальной прибыли при изменении ресурса Р₁, на -20 единиц, Р₂— на 40 единиц, Р₃ — на -10 единиц, Р₄ — на 30 единиц. Оценить раздельное влияние этих изменений и суммарное их влияние на прибыль.

9) установить, целесообразно ли выпускать новую продукцию, на единицу которой ресурсы Р₁, Р₂и Р₃ ,Р₄ расходуются в количествах 12, 5, 17 и 9 единиц, а цена единицы готовой продукции составляет 5 ден. ед.

10) Компьютерная реализация:

10.1. Решить прямую и двойственную задачи. Построить диаграммы по полученным результатам (т.е. представить в виде диаграммы полученные прямое и двойственное решения)

10.2. Создать отчеты по результатам, пределам и устойчивости для прямой и двойственной задач. Дать пояснения к полученным в отчетах результатам и сравнить полученные результаты с результатами п. I. (т.е. с результатами, полученными без использования компьютера)

10.3. Решить задачи из п. I. 8) (4 задачи) и оценить раздельное и суммарное влияние этих изменений с помощью диаграммы.

Решить исходную задачу при условии, что решение должно быть целочисленным.

2.1.Обозначим через Х₁ , Х₂ , Х₃ , Х₄ - количество изделий каждого вида соответственно, планируемого к выпуску, а через f – величину прибыли от реализации этих изделий. Тогда, учитывая значение прибыли от единицы продукции П₁ = 4 ден. ед., П₂= 2 ден. ед., П₃= 4 ден. ед., П₄= 3 ден. ед., запишем сум­марную величину прибыли – целевую функцию в следующем виде:

f = 4Х₁ + 2Х₂ +4Х₃ + 3Х₄ (мах) (2.1)

Переменные Х₁, Х₂, Х ₃, Х₄ должны удовлетворять ограничениям, наклады­ваемым на расход имеющихся в распоряжении предприятия ресурсов. Так, затраты ресурса P₁(сталь, кг) на выполнение плана (Х₁, Х₂, Х₃, Х₄) составят (10Х₁ + 20Х₂ +15Х₃+18Х₄) ед., где 10Х₁ – затраты ресурса P₁ на выпуск Х₁ ед. изделий А; 20Х₂- затраты ресурса P₂ на выпуск Х₂ ед. изделий Б и т.д. Понятно, что указанная сумма не может превышать имеющийся запас P₁ в 250 кг., т.е.

10Х₁ + 20Х₂ +15Х₃+18Х₄≤250 (2.2)

Аналогично получаем ограничение по расходу ресурса P₂ (цветные металлы, кг.)

0Х₁ + 5Х₂ + 8Х₃+ 7Х₄ ≤40 (2.3)

ограничение по расходу ресурсов P₃ (токарные станки, станко-час)

15Х₁ + 18Х₂ +12Х₃+ 20Х₄ ≤100 (2.4)

ограничение по расходу ресурсов P₄ (фрезерные станки, станко-час)

8Х₁ + 12Х₂ + 11Х₃+ 10Х₄ ≤80. (2.5)

По смыслу задачи переменные Х₁, Х₂, Х ₃, Х₄ не могут выражаться отрицатель­ными числами, т.е.

Х_j≥0 (j=1,4) (2.6)

Соотношения (2.1) - (2.6) образуют экономико-математическую модель данной задачи.

Итак, математически задача сводится к нахождению числовых значений Х₁*, Х₂*, Х ₃*, Х₄^* переменных Х₁, Х₂, Х ₃, Х₄, удовлетворяющих линейным нера­венствам (2.2) - (2.6) и доставляющих максимум линейной функции (2.1)

Прежде чем решать задачу линейного программирования симплекс-методом, ее модель приводят к канонической форме. Основным признаком канонической формы является запись ограничений задачи в виде равенств. В нашем же случае ограничения (2.2) - (2.5) имеют вид неравенств типа "≤". Чтобы преобразовать их в эквивалентные уравнения, введем в левые части неравенств дополнительные (балансовые) неотрицательные переменные Х₅, Х₆, Х₇, Х₈, обозначающие разности между правыми и левыми частями этих нера­венств. В результате модель можно записать в виде

f = 75Х₁ + 35Х₂ +40Х₃ +20Х₄ (мах) (2.7)

10Х₁ + 20Х₂ +15Х₃+18Х₄+ Х₅ = 250

0Х₁ + 5Х₂ + 8Х₃+ 7Х₄ + Х₆ = 40

15Х₁ + 18Х₂ +12Х₃+ 20Х₄ + Х₇ = 100 (2.8)

8Х₁ + 12Х₂ + 11Х₃+ 10Х₄ + Х₈ = 80

Х_j≥0 (j=1,8) (2.9)

Заметим здесь же, что дополнительные переменные Х₅, Х₆, Х₇, Х₈имеют вполне определенный экономический смысл - это возможные остатки ресур­сов соответственно P₁, P₂, P₃ ,Р₄. Их еще называют резервами.

Анализируя каноническую модель (2.7) - (2.9), замечаем, что каждая из переменных Х₅, Х₆, Х₇, Х₈ входит только в одно из уравнений системы (2.8). Это обстоятельство свидетельствует о том, что в системе (2.8) переменные Х₅, Х₆, Х₇, Х₈являются базисными, а остальные переменные Х₁, Х₂, Х₃, Х₄ - свободными. В связи с этим в первую симплекс-таблицу систему ограничительных урав­нений (2.7) можно записать в виде, разрешенном относительно базиса Х₅, Х₆, Х₇, Х₈(табл. 2.1).

Таблица 2.1

БП		СП
- Х1	- Х2	- Х3	- Х4
Х5=
Х6=
Х7=		15
Х8=
f		-4	-2	-4	-3

Все элементы столбца свободных членов положительны, поэтому со­держащийся в табл. 2.1 план (0; 0; 0; 0; 250; 40; 100; 80), является опорным. Однако этот план не является оптимальным: в f — строке имеются отрицательные элементы. Чтобы получить опорный план, более близкий к оптимальному, выпол­ним симплексное преобразование табл. 2.1. С этой целью выберем перемен­ные, участвующие в преобразовании базиса Х₅, Х₆, Х₇, Х₈в новый базис. Наи­больший по модулю отрицательный элемент (-4) f-строки указывает, что в новый базис следует ввести переменную Х₁ ,т.е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять первый столбец. Что­бы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее из них

min(250/10; 40/0; 100/15; 80/8)= 100/15 = 6,667

Итак, из базиса надо исключить переменную, стоящую в третьей (разре­шающей) строке, т.е. Х₇. На пересечении разрешающих столбца и строки на­ходится разрешающий элемент 15, с которым и выполняется симплексное преобразование (шаг жорданова исключения). В результате приходим к табл. 2.2.

В f-строке табл. 2.2 есть отрицательные элементы, значит, опорный план оптимальным не является.

Таблица 2.2

БП		СП
- Х7	- Х2	- Х3	- Х4
Х5=	183,3	-0,667			4,667
Х6=				8
Х1=	6,667	0,067	1,2	0,8	1,333
Х8=	26,667	-0,533	2,4	4,6	0,667
F	26,667	0,267	2,8	-0,8	2,333

Рассуждая аналогично предыдущему, устанавливаем, что для улучшения этого плана надо выполнить очередное симплексное преобразование с раз­решающим элементом 8. В результате получаем табл. 2.3, в f-строке ко­торой отрицательных элементов нет.

Таблица 2.3

БП		СП
- Х7	- Х2	- Х6	- Х4
Х5=	148,3	-0,667	3,625	-0,875	-1,46
Х3=			0,625	0,125	0,875
Х1=	2,667	0,0667	0,7	-0,1	0,633
Х8=	3,667	-0,5333	-0,475	-0,575	-4,69
F	30,667	0,2667	3,3	0,1	3,033

Следовательно, опорный план (2,667; 0; 5; 0; 148,3; 0; 0; 3,667) является опти­мальным, а соответствующее ему значение 30,667 целевой функции будет макси­мальным.

Итак, по оптимальному плану следует производить 2,667 ед. изделий А; 0 ед. изделий Б; 5 ед. изделий В; 0 ед. изделий С.

При этом предприятие получит максимальную прибыль в размере 30,667 ден. ед. Останут­ся неиспользованными 148,3 ед. ресурса P₁ (сталь, кг.), и 3,667 ед. ресурса Р₄ (фрезерные станки, станко-час), а ресурсы P₂ и Р₃ будут израсходо­ваны полностью.

2.2. Двойственная переменная Y_i. выступает коэффициентом при b_i,следовательно, определяет зависимость целевой функции от изменения ресурсов b_i на единицу.

Чтобы составить модель двойственной задачи, напишем матрицу ис­ходной

задачи (2.1)- (2.6) в следующем виде:

				fmax

Транспонируем матрицу (2.11). В результате получим матрицу (2.12) двойственной задачи:

				φ min

По матрице (2.12) легко написать модель задачи, двойственной к ис­ходной задаче:

φ = 250Y₁ + 40Y₂ +100Y₃+ 80Y₄ (min) (2.13)

10Y₁ + 0Y₂+ 15Y₃+ 8Y₄ ≥4

20Y₁ + 5Y₂ + 18Y₃+ 12Y₄ ≥2

15Y₁ + 8Y₂ +12Y₃+ 11Y₄ ≥4 (2.14)

18Y₁ + 7Y₂+ 20Y₃+ 10Y₄ ≥3

Y_i≥0 (j=1,3) (2.15)

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

В п. 1 мы нашли оптимальный план исходной задачи, его компоненты находятся в табл. 2.3. В f-строке этой же таблицы содержатся и компоненты Y_i* оптимального плана двойственной задачи (2.13) - (2.15). Выписать ком­поненты Y_i* поможет соответствие между переменными двойственных задач. Чтобы установить это соответствие, преобразуем ограничения-неравенства (2.14) в эквивалентные уравнения, вычитая из левых частей до­полнительные неотрицательные переменные Y₁, Y₂ и Y₃ ,Y₄ равные разностям между левыми и правыми частями этих неравенств. Тогда модель (2.13)-- (2.15) запишется в виде

φ = 250Y₁ + 40Y₂ +100Y₃+ 80Y₄ (min)

10Y₁ + 0Y₂+ 15Y₃+ 8Y₄ – Y₅= 4

20Y₁ + 5Y₂ + 18Y₃+ 12Y₄ – Y₆= 2

15Y₁ + 8Y₂ +12Y₃+ 11Y₄ - Y₇= 4

18Y₁ + 7Y₂+ 20Y₃+ 10Y₄ - Y₈= 3

Y_i≥0 (j=1,8)

В этой записи переменные Y₅, Y₆ и Y₇, Y₈ являются базисными, а Y₁, Y₂ и Y₃, Y₄ - свободными. В исходной задаче (2.7) - (2.9) переменные Х₁, Х₂ и Х₃, Х₄ яв­ляются свободными, a Х₅, Х₆ и Х₇, Х₈ - базисными.

Соответствие, о котором шла речь выше, устанавливают, сопоставляя базисным переменным одной задачи свободные переменные двойственной задачи и наоборот, т.е.

Х₅ÛY₁, Х₆ÛY₂, Х₇ÛY₃, Х₈ÛY₄, Х₁ÛY₅, Х₂ÛY₆ , Х₃ÛY₇, Х₄ÛY₈.

(2.16)

Воспользуемся соответствием (2.16) следующим образом. Как видно, переменная Y₁ связана с переменной Х₅ (поэтому их называют двойственными переменными), а в табл.2.3 переменная Х₅ находится в базисе, значит, двой­ственная ей переменная Y₁ на этом этапе расчетов является свободной и, как свободная переменная, равна нулю (в любой двойственной паре всегда одна переменная базисная, а другая свободная). Итак, Y₁* = 0. Далее, Y₂ соответст­вует Х₆, а в табл.2.3 под Х₆ в f- строке находится элемент 0,1, следовательно, Y₂* = 0,1. Точно так же устанавливается, что Y₃* = 0,2667; Y₄* = 0; Y₅* = 0; Y₆* = 3,3; Y₇* = 0; Y₈* =3,033.

Из теорем двойственности следует, что экстремальные значения целе­вых функций разрешимых двойственных задач совпадают, поэтому φ_min = f_max = = 30,667.

2.4. Оценки ресурсов Р₂ и Р₃являются положительными, следовательно эти виды сырья используется постоянно и является дефицитным. Наиболее дефицитным ресурсом будет ресурс Р₃, так он имеет наибольшую оценку. Избыточным ресурсами является ресурсы Р₁и Р₄, так как их оценки равны нулю.

2.5.Чтобы определить изменение максимальной прибыли при изменении ресурсов, необходимо найти интервалы устойчивости двойственных оценок, в пределах которых они точно измеряют влияние ограничений на целевую функцию.Определим интервал устойчивости по отношению к ограничению по ресурсу 1-го вида. Для этого выпишем матрицу из коэффициентов при базисных неизвестных. Базисными переменными в оптимальном решении являются Х₄, Х₆, Х₇, Х₁. Матрица коэффициентов при этих переменных в системе ограничений имеет вид:

Обратная матрица

	-0,875	-0,667
	0,125
	-0,1	0,0667
	-0,575	-0,533

используя формулы ; , находим

min (148,3/1)= 148,3

∞

В соответствии с формулой : , интервал устойчивости оценок по отношению к первому ресурсу примет вид: (250 – 148,3; 250 + ∞) = (101,7; ∞)

Аналогично находим интервал устойчивости для остальных видов ресурсов.

5/0,125 = 40 3,667/0,575 = 6,377

Р₂:(40 – 40; 40 + 3,677) = (0; 43,677)

2,6667/0,06667 = 40 3,667/0,533 = 6,875

Р₃:(100 – 40; 100 + 6,875) = (60; 106,875)

3,667/1 = 3,667 ∞

Р₄:(80 – 3,667; 80 + ∞) = (76,333; +∞)

Величина двойственной оценки численно равна изменению целевой функции при изменении соответствующего ресурса на одну единицу.

При увеличении ресурса Р₂ на одну весовую единицу значение целевой функции оптимального плана увеличится на 0,1 ден. ед. При увеличении ресурса Р₃ на одну весовую единицу значение целевой функции оптимального плана увеличится на 0,2667 ден. ед. Оценки ресурсов Р₁ и Р₄ равны нулю, следовательно данные ресурсы не является дефицитным, при их увеличении значение целевой функции не изменится. Оценка изделий Б и С больше нуля, следовательно производство данных изделий не будет рентабельным и при производстве одной единицы изделия Б значение целевой функции оптимального плана уменьшится на 3,3 ден. ед., а при производстве одной единицы изделия С значение целевой функции оптимального плана уменьшится на 3,033ден. ед.

2.6. Матрица коэффициентов взаимозаменяемости ресурсов:

	-0,875	-0,667
	0,125
	-0,1	0,0667
	-0,575	-0,533

2.7. Оценим целесообразность приобретения Db= 3 единиц ресурса P₃по цене c₃=0,5 заединицу. Определим значение ∆ = y₃ – C₃ = 0,1 – 0,5 = -0,4. Увеличение прибыли при закупке 1 единицы ресурса Р₃ меньше цены данного ресурса, следовательно не имеет смысла закупать данный ресурс.

2.8.Изменение второго вида ресурса не находится в пределах устойчивости оценок, следовательно мы не можем оценить влияние изменения на целевую функцию. Изменения ресурсов 1, 3, 4 находятся в пределах устойчивости оценок, то их раздельное влияние на величину прибыли, Df_imax определяется произведением оценки y_i и величины изменения Db_i.

Df_1max=Db₁·y₁= -20· 0= 0 ден. ед.

Df_3max=Db₃·y₃= -10·0,2667 = -2,667 ден. ед.

Df_4max=Db₄·y₄= 30·0 = 0 ден. ед.

Суммарное влияние Df_max=Df_1max+Df_3max +Df_4max= 0 – 2,667 + 0= -2,667 ден. ед.

2.9. Установим, целесообразно ли выпускать новую продукцию, на единицу которой ресурсы Р₁, Р₂ и Р₃, Р₄ расходуются в количествах 12; 5; 17 и 9 единиц, а цена единицы готовой продукции составляет 5 ед. Для этого вычисляем характеристику:

(12·0+ 5·0,1+ 17·0,2667+ 9) – 5 = 0,0339 > 0

Так как прибыль не превышает затраты то введение в план производства нового изделия не целесообразно.