Симплекс метод

Прибыль на продукцию также принимается  как известная величина и обозначается символами c₁, c₂, с₃.

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

Поскольку решение задачи заключается в  поиске такого плана производства, который обеспечивал бы в принятых условиях наибольший доход, принимаются те величины, которые являются неизвестными и обозначающими количества каждой группы конфет, включаемых в план производства: x₁ для M₁; х₂ для М₂; х₃ для М₃.

Экономико-математическая модель в  символическом виде.

Система ограничений

Целевая функция /суммарный доход/ F = с₁х₁ + с₂х₂ + с₃х₃ = мах

Условия неотрицательности неизвестных х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0

Символическая модель, наполненная численной информацией, будет иметь следующий вид:

2x₁ + 4x₂ + 3x₃ ≤ 266

1x₁ + 3x₂ + 4x₃ ≤ 200

3x₁ + 2x₂ + 1x₃ ≤ 303

Прибыль от реализации выпускаемой продукции  должна быть максимальной, то есть F = 20х₁ + 24х₂ + 28х₃ = max;

 

Решение задачи.

Для решения  задачи симплексным методом неравенства  преобразуются в эквивалентные  равенства путем добавления в  каждое неравенство по одному дополнительному неизвестному с коэффициентом + 1 и нулевым уравнением прибыли. Для удобства расчетов левые и правые части уравнений меняются местами. В этом случае исходные неравенства примут вид симплексных уравнений:

266 = 2x₁ + 4x₂ + 3x₃ + 1x₄

200 = 1x₁ + 3x₂ + 4x₃ + 1x₅

303 = 3x₁ + 2х₂ + 1x₃ + 1x₆

F = 20х₁ + 24х₂ + 28х₃ + 0x₄ + 0x₅ + 0x₆

 

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

 

Исходная  таблица

cj	p0	x0	20	24	28	0	0	0
			x1	х2	х3	х4	х5	х6
0	х4	266	2	4	3	1	0	0
0	х5	200	1	3	4	0	1	0
0	х6	303	3	2	1	0	0	1
Zj - Cj		0	-20	-24	-28	0	0	0

 

В столбцах таблицы записывают: в первом (C_j) – прибыль единицы продукции, которая вводится в план выпуска; во втором (Р₀) – неизвестные, включаемые в план; в третьем (Х₀) – свободные величины; в остальных – коэффициенты при неизвестных уравнений. В верхней части этих столбцов отражаются коэффициенты при неизвестных целевой функции.

В нижней строке (целевой) записываются получаемые расчетным путем показатели: в  столбце х₀ – суммарная прибыль планового выпуска, в остальных столбцах – прибыль единицы продукции с отрицательным знаком.

В последних  трех столбцах коэффициенты при дополнительных неизвестных, равные единице, расположены по диагонали. Эта часть таблицы, называемая единичной подматрицей, необходима для вычислительных и аналитических целей.

При решении  задач на максимум целевой функции  наличие в целевой строке отрицательных  чисел указывает на возможность  начала или продолжения решения  задачи. Порядок решения таков: из отрицательных чисел целевой  строки выбирается наибольшее по модулю. Столбец, в котором оно находится, принимается за ключевой (или разрешающий) и для удобства расчетов выделяется. В нашем примере таким столбцом будет Х₃, имеющий в целевой строке наибольшую по модулю величину -28.

 

1-ая итерация

cj	p1	x0	x1	х2	х3	х4	х5	х6
0	х4	116	1.3	1.75	0	1	-1	0
28	х3	50	0.3	0.75	1	0	0.3	0
0	х6	253	2.8	1.25	0	0	-0	1
Zj - Cj		1400	-13	-3	0	0	7	0

 

Затем элементы столбца Х₀ (свободные величины) делят на соответствующие коэффициенты ключевого столбца и полученные результаты сопоставляют между собой. Строка с наименьшим отношением принимается за ключевую и также для удобства выделяется. В нашем случае 266/3 = 88,7; 200/4 = 50; 303/1 = 303. Наименьшее отношение 50 имеет срока х₅, она и будет ключевой. Ключевой элемент 4.

Далее элементы таблицы преобразуются и записываются в новую таблицу. Первоначально  преобразуют элементы ключевой строки путем деления их на ключевой элемент. Преобразованные элементы записывают в том же самом месте.

В столбцах Р_о и C_j занимают место вводимая в план неизвестная х₃ с прибылью 28 (итерация 1-я). Остальные элементы преобразуются по следующему правилу:

- для  преобразуемого элемента в его  столбце находят элемент ключевой  строки, а в его строке - элемент  ключевого столбца;

- соответствующие  элементы ключевой строки и  ключевого столбца перемножаются и полученное произведение делят на ключевой момент;

- частное  от деления вычитают из значения  элемента, которое он имел до  преобразования, и полученный результат  будет преобразованным элементом,  который записывается в новую таблицу в том же самом месте. Следуя этому правилу, преобразование элементов столбца х₀ будет:

Включение на первой итерации в план неизвестной  х₃  обеспечит сумму прибыли 1400 руб.

Решение задачи продолжается, так как в  целевой строке два отрицательных элемента. Наибольший по модулю элемент -13. Он находится в столбце х₁, который принимается за ключевой, а ключевой строкой будет х₆ (116:1,3=92,8; 50:0,3=200; 253:2,8=92), ключевым элементом 2,8. Элементы таблицы преобразуются в том же порядке по изложенному правилу и записываются в новую таблицу.

 

2-я итерация

cj	p2	x0	x1	х2	х3	х4	х5	х6
0	х4	1	0	1.18	0	1	-1	-0.5
28	х3	27	0	0.64	1	0	0.3	-0.1
13	х1	92	1	0	0	0	0	0
Zj - Cj		2596	0	2.91	0	0	5.8	4.7

 

В последней  таблице целевая строка имеет  только положительные элементы. Это значит, что составленный план оптимален и дальнейшее улучшение его невозможно.

Как видно  из таблицы, оптимальный план предусматривает  выпуск продукции П₁ 27 ед. (х₁ = 27), П₃ 92 ед. (х₃ = 92), дополнительного неизвестного П₄ 1 ед. (х₄ = 1). П₂ и дополнительные неизвестные в план не вошли, следовательно, х₂ = 0, х₅ = 0 х₆ = 0. Подставив значения неизвестных в уравнения, получим:

2 * 92 + 4 * 0 + 3 * 27 + 1 = 266

1 * 92 + 3 * 0 + 4 * 27 + 0 = 200

3 * 92 + 2 * 0 + 1 * 27 + 0 = 303

F = 20 * 92 + 24 * 0 + 27 * 28 = 2596

 

Анализ оптимального плана.

а) Запасы сырья трех видов используются не полностью, так как х₄ = 1, а х₅ = х₆ = 0.

б) Рассмотрим элементы матрицы.

От выпуска  продукции II следует отказаться.

Элементы  столбца х₅ показывают, что увеличение запасов сахара на I ед. (х₅ = 1) позволит увеличить выпуск продукции III вида на 0,3 ед. Сумма прибыли увеличится на 5,8 руб.

Элементы  столбца х₆ показывают, что увеличение запасов жира на I ед. (х₆ = 1) позволит уменьшить выпуск только продукции III вида на 0,1 ед. (27 - 0.1) Сумма прибыли увеличится на 4,7 руб.

Снижение  запасов сырья приводит к изменениям выпуска продукции и суммы  прибыли в обратном порядке.

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

 

ЗАДАЧА 2

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

Питательные вещества	Виды сырья			Минимальное содержание (единиц) питательных веществ  в готовом  продукте
	M1	М2	М3
П1	1	1	0	50
П2	4	1	3	140
П3	1	4	1	127
П4	0	3	2	80
Цена за единицу сырья, руб.	8	12	10

 

Виды  используемого сырья условно  обозначены через М₁, М₂, М₃; содержание питательных веществ в сырье и готовом продукте обозначены П₁, П₂, П₃, П₃.

Исходные  условия задачи выражаются неравенствами:

1х₁ + 1х₂ + 0х₃ ≥ 50

4х₁ + 1х₂ + 3х₃ ≥ 140

1х₁ + 4х₂ + 1х₃ ≥ 127

0х₁ + 3х₂ + 2х₃ ≥ 80

F = 8х₁ + 12х₂ + 10х₃ = min

Умножив обе части неравенств на -1, получим  систему с другим направлением знака неравенств:

-1х₁ - 1х₂ - 0х₃ ≥ -50

-4х₁ - 1х₂ - 3х₃ ≥ -140

-1х₁ - 4х₂ - 1х₃ ≥ -127

0х₁ - 3х₂ - 2х₃ ≥ -80

F = 8х₁ + 12х₂ + 10х₃ = min

Преобразуем неравенства в эквивалентные  равенства с помощью дополнительных неизвестных. Симплексные уравнения будут следующими:

-50 = -1х₁ - 1х₂ - 0х₃ + 1х₄ + 0х₅ + 0х₆ + 0х₇

-140 = -4х₁ - 1х₂ - 3х₃ + 0х₄ + 1х₅ + 0х₆ + 0х₇

-127 = -1х₁ - 4х₂ - 1х₃ + 0х₄ + 0х₅ + 1х₆ + 0х₇

-80 = 0х₁ - 3х₂ - 2х₃ + 0х₄ + 0х₅ + 0х₆ + 1х₇

F = 8х₁ + 12х₂ + 10х₃ + 0х₄ + 0х₅ + 0х₆ + 0х₇ = min

Записанные  уравнения отличаются от тех, которые  нами рассматривались выше, тем, что  коэффициенты при основных неизвестных  и свободные члены имеют отрицательные  знаки.

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

 

cj	p0	x0	8	12	10	0	0	0	0
			x1	х2	х3	х4	х5	х6	х7
0	х4	-50	-1	-1	0	1	0	0	0
0	х5	-140	-4	-1	-3	0	1	0	0
0	х6	-127	-1	-4	-1	0	0	1	0
0	х7	-80	0	-3	-2	0	0	0	1
Zj - Cj		0	-8	-12	-10	0	0	0	0