Курсовик по прикладу вариант № 8

1.3. Решение линейной производственной задачи симплексным методом.

Поскольку правые части всех уравнений системы неотрицательны, а сама система линейных алгебраических уравнений имеет предпочитаемый вид (дополнительный переменные х5, х6, х7 являются базисными), для решения полученной задачи можно применить симплексный метод

			38	12	28	21	0	0	0	Преобразования	Пояснения
Č	Базис	H	х₁	х₂	х₃	х₄	х₅	х₆	х₇	Преобразования	Пояснения
0	Х₅	186	3	0	3	3	1	0	0	I+III(-3/4) → I’ II+III(-1/2) → II’ III : 4 → III’ IV+III*(38/4) → IV’	min(_j<0) = -38 Х₁→ в базис min hi/ai1>0 = min(62,51,49) = 49 => Х7→ из базиса
0	Х₆	102	2	3	1	1	0	1	0
0	Х₇	196	4	3	2	2	0	0	1
	Z₀ – Z	0-Z	-38	-12	-28	-21	0	0	0
										I’ : 3/2 → I’’ II’+I0 → II’’ III’+I(-1/3) → III’’ IV’+I*6 → IV’’	min(_j<0) = -9 Х₃→ в базис min hi/ai1>0 = min(26,98) = 26 => Х5→ из базиса
0	X₅	39	0	- 9/4	3/2	3/2	1	0	- 3/4
0	Х₆	4	0	3/2	0	0	0	1	- 1/2
38	Х₁	49	1	3/4	1/2	1/2	0	0	1/4
	Z₀ – Z	1862-Z	0	33/2	- 9	- 2	0	0	19/2
											Z₀= Č* H ∆j=Č*Gj–cj все ∆j≥0
28	Х₃	26	0	- 3/2	1	1	2/3	0	- 1/2
0	Х₆	4	1	3/2	0	0	0	1	1/2
38	Х₁	36	0	3/2	0	0	- 1/3	0	1/2
	Z₀ – Z	2096-Z	0	3	0	7	6	0	5

Пояснения к решению задачи

Алгоритм решения:

Просматриваем значения 4-й строки симплексной таблицы. Если все _j  0, то решение задачи является оптимальным.
Если какие-либо _j < 0, находим min(_j < 0) =  _к.
Х _к включаем в число базисных переменных.
Отыскиваем разрешающее уравнение и переменную, исключаемую из базиса:

находим min(h_i/а_ik) = h_t/а_tk (для всех а_ik > 0);
Х _t исключаем из числа базисных переменных.

Строим новую симплексную таблицу, преобразуя исходную.
Возвращаемся в пункт 1.

Пояснения к первой симплексной таблице

X = (0, 0, 0, 0, 186, 102, 196)

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

В строке оценочных коэффициентов имеются отрицательные значения, которые показывают, на сколько увеличится прибыль от производства продукции при включении в план производства одной единицы продукции того или иного вида. Например, число –12 означает, что включение в план производства единицы второго вида продукции позволит увеличить прибыль на 12 денежных единиц. Наиболее выгодным в данной задаче будет внедрение в производство первого вида продукции, так как ему соответствует максимальная удельная прибыль, равная 38 денежным единицам. Поэтому x₁становится базисной переменной и запускается производство первого вида продукции. Определяем переменную, которую надо исключить из производства. Ограничивающим фактором будет объем ресурса третьего вида (Х7), поскольку из него можно произвести наименьшее количество продукции первого вида, так как ему соответствует наименьшееhi/ai1, равное 49.

Пояснения ко второй симплексной таблице

X = (49, 0, 0, 0, 39, 4, 0)

Изготавливается 49 единиц первого вида продукции. 39 единиц первого вида ресурса и 4 единицы второго вида ресурса остаются в остатке.

Прибыль от реализации произведенной при таком плане продукции (Z) составляет 1862 денежные единицы.

Наличие отрицательных значений в строке оценочных коэффициентов указывает на то, что данный план производства также не является оптимальным. При этом наиболее выгодным будет внедрение в производство третьего вида продукции, которое принесет наибольший прирост прибыли. При этом при исключении из базиса Х5 неиспользованный первый ресурс полностью уйдет в производство.

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

Пояснения к третьей симплексной таблице

X = (36, 0, 26, 0, 0, 4, 0)

Среди значений в строке оценочных коэффициентов нет ни одного отрицательного. Если из уравнения последней строки данной симплексной таблицы выразить целевую функцию Z через свободные переменные

Z = 2096 - 3х₂- 7х₄- 6х₅- 5х_7,

то становится совершенно очевидным (в силу того, что все ∆j≥ 0), что прибыль будетнаибольшей тогда, когда х_{2 ,}х_4,х_5,х₇= 0.

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

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

Оценочные коэффициенты, соответствующие ресурсам, выражают меру дефицитности ресурсов.

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

Оценка второго ресурса равна 0. Он дан в избытке, увеличение его количества не ведет к увеличению прибыли, поэтому увеличивать его нет смысла.

Содержание