Последняя симплекс-таблица задачи дз-1

(Zmах = 240538)

Номер строки	Базисные переменные	Ном.огр. для допол. переменных	Аiо	Коэффициенты замещения
				Х5 основн.	Х7 изб.огр.8	Х8 ост.огр.1	Х11 ост.огр4	Х12 ост. огр.5
1	Х13(ОСТ.)	6	3812	6.2	0.2831	6.15	-0.877	2.338
2	Х9 (ОСТ.)	2	28620	390	0.86	-10	0.2	-2.2
3	Х10 (ОСТ)	3	9121	410	1.478	-89.62	4.208	-12.05
4	Х2 (ОСН.)	-	60.15	0.08	0.0035	0.0769	0.0015	0.029
5	Х3 (ОСН.)	-	30	0	-0.01	0	0	0
6	Х1 (ОСН.)	-	841.8	0.92	0.0025	0.923	0.0184	-0.049
7	Х14(ОСТ.)	7	49.85	-0.08	-0.0035	-0.077	-0.015	-0.029
8	Х6 (ОСН.)	-	80880	-410	-1.478	89.62	-4.2	12.05
9	Х4 (ОСН.)	-	53.15	0.08	-0.0025	0.0769	-0.018	0.049

Анализ табл. 4 показывает, что производство сахарной свеклы хозяйству невыгодно: соответствующая основная переменная Х5 не попала в базис, то есть в оптимальном сочетании отраслей площадь пашни под свеклу X₅ = 0.

Предположим теперь, что по каким-либо внешним причинам хозяйство вынуждено выращивать сахарную свеклу в определенном объеме. Пусть такой заданный объем равен 4800 га. Такое задание эквивалентно ограничению:

240*Х₅ = 4800 ,

что соответствует требованию отвести под свеклу

Х₅ = 4800/240 = 20 га.

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

Введение в базис основной переменной, не вошедшей в него в последней симплекс-таблице, приведет к уменьшению значения целевой функции (задача на максимизацию).

Количественно уменьшение будет определяться значением элемента индексной строки, соответствующего вводимой переменной. Для рассматриваемой задачи это означает, что отведение под свеклу каждого гектара пашни будет приводить к уменьшению чистого дохода хозяйства (целевой функции) на 149 тыс.руб. Следовательно, при отведении под свеклу 20 га целевая функция примет значение:

Z = Z_max - 149*20 = 240538 - 2980 = 237558 тыс.руб.

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

Новое значение любой базисной переменной из последней симплекс-таблицы (табл.4) может быть определено по формуле:

Х'_jб = X_jб - К*Х₅

где К - коэффициент замещения, стоящий на пересечении столбца, соответствующего вводимой переменной, и строки, соответствующей рассматриваемой базисной переменной. Таким образом, если коэффициент замещения К, соответствующий данной базисной переменной, отрицателен, то при введении в план переменной Х₅ базисная переменная будет увеличиваться, в противном случае - уменьшаться. Указанное обстоятельство позволяет установить правило определения допустимого предела увеличения переменной X₅: увеличение значения переменной Х₅ не должно приводить к отрицательным значениям базисных переменных. Иначе говоря, если рассмотреть базисную переменную, которой соответствует положительный коэффициент замещения, и новое значение базисной переменной Х'_jб принять равным нулю, то есть минимальному допустимому значению, то на последнего соотношения получим следующее ограничение на величину Х₅:

Х_jб – К*Х₅ = 0

или

Х_5max = Х_jб/К.

Резюмируя изложенное, придем к следующему алгоритму введения в план основной переменной, не вошедшей в оптимальный базис:

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

Х₁₃: 3810/6.2 = 614

X₉: 28600/390 = 73

X₁₀: 9120/410 = 22

X₂: 60.2/0.08 = 753

X₁: 842/0.92 = 915

X_14: 581/0.08 = 7262

Сравнить все полученные числа и выбрать наименьшее. Это и будет максимально возможное значение вводимой переменной. Для рассматриваемого примера такое значение равно Х_5max = 22.

Для понимания влияния полученного ограничения на допустимое значение вводимой переменной необходимо учесть следующее. Именно не превышение ограничения Х_5max = 22 обеспечивает возможность построения нового оптимального плана из старого (табл.4) без полного решения задачи симплекс-методом. В принципе допустимо задать требование, нарушающее указанное ограничение, например, положить Х₅ = 30, но в этом случае придется решать новую задачу (с ограничением Х₅ = 30) самостоятельно.

(Терминология: иногда отношение, породившее ограничение на допустимые значения вводимой переменной, называет "узким местом").

2.Расчет новых значений целевой функции и базисных переменных (далее положим, что необходимо ввести в план Х₅ = 20):

Z^’ = Z_max – (Z₅ – C₅)* X₅ (12)

Х^’_jб = K_jб – К*Х₅ (13)

где (Z₅-C₅) - элемент индексной строки, соответствующей переменной Х₅;

К - коэффициент замещения, расположенный в столбце, соответствующем небазисной переменной Х₅, и в строке, соответствующей базисной переменной X_j6.

Результаты расчета заносят в таблицу следующего вида:

Таблица 5

Введение в оптимальный план задачи ДЗ-1 основной переменной Х₅ = 20

Базисные Переменные	Значение базисной переменной в оптимальном плане	Коэффициенты замещения при Х5	Произведение к-в замещения на вводимую переменную (К*20)	Новый план при Х5 = 20
Х13 (ост)	3810	6.2	124	3686
Х9 (ост)	2860	390	7800	20800
Х10 (ост)	9120	410	8200	920
Х2 (осн)	60	0.08	1.6	58.4
Х3 (осн)	30	0	0	30
Х1 (осн)	842	0.92	18.4	823.6
Х14 (ост)	49.8	-0.08	-1.6	51.4
Х6 (осн)	80900	-410	-8200	89100
Х4 (осн)	58	0.08	1.6	56.4
Х5	0	1	-20	20
Z	241000	149	2980	23758

Подчеркнем, что новый план также можно рассматривать как оптимальный, но для задачи ДЗ-1 с дополнительным условием Х₅ = 20га.

Сравнивая таблицы 4 и 5, придем к выводу, что требование занять 20 гектаров пашни под сахарную свеклу привело к уменьшению:

- площади зерновых культур (X₁) - на 18.4 гa;

- площади кормовых культур (Х₄) - на 1.6 гa;

- поголовья коров (Х₂) - на 2 головы.

При этом поголовье свиней сохранялось, что и должно быть, поскольку в условиях задачи сформулировано жесткое плановое задание по свинине. Общие денежные расходы хозяйства (X₅) увеличились на 82тыс. руб., а чистый доход хозяйства (целевая функция) уменьшилась на 2980 тыс.руб.

Введение в план дополнительной переменной.

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

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

Аналитический алгоритм преобразования оптимального плана при введении в план остаточной переменной заключается в следующем (на примере задачи ДЗ - см. Ta6n.3):

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

Для рассматриваемого примера получим (числа округлены):

X₁₃ : 3812/6.15 = 620

X₉ : 28620/-10 = -2862

X₁₀ : 9121/-89.62 = -102

X₂ : 60.15/0.0769 = 782

X₃ : 30/0 = --

X₁ : 841.8/0.923 = 912

X₁₄ : 49.85/-0.077 = -647

X₆ : 80880/89.62 = 902

X₄ : 53.15/0.0769 = 691

Из найденных чисел выбрать наименьшее положительное и наименьшее (по модулю) отрицательное. Тем самым будут установлены пределы, в которых можно изменять значение остаточной переменной без изменения структуры оптимального решения. Для рассматриваемого примера допустимые пределы изменения переменной Х₈ составляют (-102, +620).

Рассмотрим далее случай введения в план переменной Х₈ = -100.

2. Расчет новых значений целевой функции и базисных переменных по формулам аналогичным (12) и (13):

Z^’ = Z_max – (Z₈ – C₈)*X₈;

X^’_jб = X_jб – K*X₈,

где (Z₈-C₈) – элемент индексной строки, соответствующий переменной Х3₈.|

К - коэффициент замещения, расположенный в столбце, соответствующем небазисной переменной Х₈, и в строке, соответствующей базисной переменной Х_jб.

Результаты расчетов заносят в таблицу 6.

Таблица 6

Введение в оптимальный план задачи ДЗ-1 остаточной переменной Х₈ = -100

Базисные Переменные	Значение базисной переменной в оптимальном плане	Коэффициенты замещения при Х8	Произведение к-в замещения на вводимую переменную (К* (-100))	Новый план при Х8 = -100
Х13 (ост)	3812	6.15	-615	4427
Х9 (ост)	28620	-10	1000	27620
Х10 (ост)	9121	-89.62	8962	159
Х2 (осн)	60.15	0.0769	-7.69	67.84
Х3 (осн)	30	0	0	30
Х1 (осн)	841.8	0.923	-92.3	934.1
Х14 (ост)	49.85	-0.077	7.7	42.15
Х6 (осн)	80880	89.62	-8962	89842
Х4 (осн)	53.15	0.0769	-7.69	60.84
Х8	0	-1	100	-100
Z	240538	269.2	-26920	267458

Таким образом, в рассмотренном пример введение в план остаточной переменной Х₈ =-100, то есть увеличение ресурса пашни на 100 гектаров, приводит к увеличению площади посевов зерна до 934 гектаров (X₁) и к увеличению поголовья коров - 50 голов (Х₂).

В случае введения в план избыточной переменной алгоритм вычислений идентичен рассмотренному.