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

 

Рассмотрим на конкретном примере.Для изготовления изделий 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

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