Интерпретация оптимального решения

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

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

а). Экстремальное значение целевой функции - основной показатель достигаемого в результате оптимизации эффекта:

Z_max = 240538 тыс.руб.

б). Основные переменные, попавшие в базис:

площадь зерновых культур X₁ = 842 га;

поголовье коров Х₂ = 60 гол;

поголовье свиней Х₃ = 30 гол;

площадь кормовых культур Х₄ = 58 rа;

денежные расходы хозяйства X₅ = 86879 рублей.

в). Основные переменные, не попавшие в базис:

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

г). Дополнительные переменные, попавшие в базис:

недоиспользованные трудовые ресурсы Х₈ = 28620 чел.-ч.;

недоиспользованные денежные ресурсы Х₉ = 9121 тыс.руб.;

остаток кормов, соответствующий

объему балансовому уравнению по

свиньям Х₁₂ = 3812 ц.к.е.

недоиспользованные места для

содержания коров Х₁₃ = 50 гол.

д). Дополнительные переменные, не попавшие в базис:

Х₇ - остаток площади пашни;

Х₁₀ - остаток кормов (соответствующийвсем видамкормов и всем видам животных);

Х₁₁ - остаток концентрированных кормов (соответствующий всем видам животных).

Дадим более полную интерпретацию дополнительных переменных.

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

Х₇ = 0, то есть вся пашня используется: и действительно, сумма площадей пашни под зерновые и кормовые культуры равна общей площади пашни Х₁ + Х₄ = 900 га.

Остаточные переменные, попавшие в базис, характеризуют не полностью используемый ресурс. Например, остаются неиспользованными 50 мест для содержания коров. Соответственно, поголовье коров равно 60 голов вместо 110 максимально возможных.

В то же время интерпретация остатков кормов требует определенной осторожности. Например, остаток кормов “по свиньям” (переменная Х₁₂) равен 3812 ц.к.е. Однако это не означает потери кормов. Поскольку общий остаток кормов (переменная Х₁₂) равен нулю, то Х₁₂ = 3812 ц.к.е., следует интерпретировать как часть кормов с пашни, идущую на корм коровам.

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

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

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

Двойственные задачи линейного программирования. Экономическая интерпретация значений двойственных переменных (двойственных сценок).

Каждой задаче линейного программирования можно поставить в соответствие двойственную задачу. Анализ решений двойственных задач позволяет четче понять экономическое содержание оптимального решения исходной (прямой) задачи.

Итак, пусть дана задача линейного программирования (внеканоническом представлении):

Х₁ + +Х₄ 900 (1)

5*Х₁ + 50*Х₂ + 100*Х₃ + 50*Х₄ 40000 (2)

Х₅ 90000 (3)

-2,5*Х₁ + 80*Х₂ + 40*Х₃ - 50*Х₄ 1000 (4)

-2,5*Х₁ + 30*Х₂ + 10*Х₃ 0 (5)

-2,5*Х₁ + + 40*Х₃ – 50*Х₄ 0 (6)

Х₂ 110 (7)

100*Х₃ 3000 (8)

70*Х₁ + 25*Х₂ + 100*Х₃ + 300*Х₄ = 0 (9)

Х_j 0, j = 1, …,5. (10)

Общее структурное представление этой же задачи имеет вид:

;

Z = ;

Соответствие между символами A_ij, B_i, С_j и числовыми коэффициентами в соотношениях (1),...,(9) достаточно очевидно.

При постановке двойственной задачи вводят двойственные переменные - Y₁,...,Y₉,. Каждая переменная сопоставляется одному ограничению прямой задачи. Структурный вид обратной задачи таков:

Z^’ =

Y

Соответствующая развернутая запись имеет вид:

Y₁ + 5*Y₂ – 2.5*Y₄ – 2.5*Y₅ – 2.5*Y₆ + 70*Y₉ 225; (1)

50*Y₂ + 80*Y₄ + 30*Y₅ + Y₇ + 25*Y₉ 800; (2)

100*Y₂ + 40*Y₄ + 10*Y₅ +40*Y₆ + 100*Y₈ + 100*Y₉ 100; (3)

Y₁ + 50*Y₂ – 50*Y₄ – 50*Y₆ + 300*Y₉ 0; (4)

Y₃ – Y₉ = 0. (5)

Z^’ = 900*Y₁ + 40000*Y₂ + 90000*Y₃ + 1000*Y₄ + 110*Y₇ + 3000*Y₉ min (6)

Y_i 0, i = 1,…,9. (7)

Обратите внимание на то, что по сравнению с прямой задачей поменялись знаки ограничений – вместо “ ” используется “ ” и целевая функция Z' подвергается минимизации, а не максимизации. (Отметим, что для прямых задач других видов - с ограничениями типа “ ”, на минимизацию целевой функции - правила построения обратных задач отличаются от рассмотренных).

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

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

1) оптимальное (максимальное) значение целевой функции Z прямой задачи совпадает с оптимальным (минимальным) значением целевой функции Z' обратной задачи;

2) значения основных переменных обратной задачи Y₁,...,Y₉ совпадают с элементами индексной строки, соответствующими остаточным переменным ХЗ,...,Х6 в последней симплексной таблице прямой задачи.

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

Z_max = Z^’_min =

Преобразование оптимального решения с помощью коэффициентов замещения последней симплекс-таблицы

Рассмотрим следующую задачу (близкую к задаче ДЗ). Демонстрационная задача Дз-1:

В хозяйстве сложились пять основных отраслей: производство товарного зерна (X₁,га), молочное скотоводство (X₂,гол), свиноводство (Х₃,гол), кормопроизводство (Х₄,га) и производство сахарной свеклы (Х₅,га). Урожайность свеклы - 240 ц/га, трудозатраты при ее выращивания - 400 чел.-ч/га, денежные затраты - 500 тыс.руб./га, чистый доход - 0.5 тыс.руб./ц. Другие исходные данные аналогичны данным задачи ДЗ. Цель оптимизации: найти оптимальное сочетание отраслей хозяйства (включая возможное производство сахарной свеклы), обеспечивающее максимум чистого дохода.

Обозначим через Х₆ общие денежные расходы хозяйства. Система ограничений и выражение для целевой функции задачи имеет вид:

Ограничение по площади пашни:

Х₁ + Х₄ + Х₅ 900 (1)

Ограничение по трудовым ресурсам:

5*Х₁ + 50*Х₂ + 100*Х₃ + 50*Х₄ + 400*Х₅ 40000 (2)

Ограничение по денежным ресурсам:

Х₆ 90000 (3)

Баланс всех кормов по всем видам животных:

-2,5*X₁ + 80*Х₂ + 40*Х₃ – 50*Х₄ 1000 (4)

Баланс концентратов по всем видам животных:

-2.5*Х₁ + 30*Х₂ + 10*Х₃ 0 (5)

Баланс всех кормов по свиньям:

-2.5*Х₁ + 40*Х₃ +50*X₄ 0 (6)

Ограничение по поголовью коров:

Х₂ 110 (7)

Ограничение по гарантированному производству свинины:

100*Х₃ 3000 (8)

Уравнение для расчета общих денежных затрат:

70*Х₁ + 25*Х₂ + 100*Х₃ +300*Х₄ + 500*Х₅ = Х₆ (9)

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

Z = 225*Х₁ + 800*Х₂ + 100*Х₃ + 120*Х₅ max, (10)

Условие неотрицательности основных переменных:

Х_j 0, j =1,…,6. (11)

Оптимальное решение задачи представлено в таблице 4.

Таблица 4

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

(Zmах = 240538)

Номер строки	Базисные переменные	Ном.огр. для допол. переменных	Аiо	III. Коэффициенты замещения
Х5 основн.	Х7 изб.огр.8	Х8 ост.огр.1	Х11 ост.огр4	Х12 ост. огр.5
	Х13(ОСТ.)			6.2	0.2831	6.15	-0.877	2.338
	Х9 (ОСТ.)				0.86	-10	0.2	-2.2
	Х10 (ОСТ)				1.478	-89.62	4.208	-12.05
	Х2 (ОСН.)	-	60.15	0.08	0.0035	0.0769	0.0015	0.029
	Х3 (ОСН.)	-			-0.01
	Х1 (ОСН.)	-	841.8	0.92	0.0025	0.923	0.0184	-0.049
	Х14(ОСТ.)		49.85	-0.08	-0.0035	-0.077	-0.015	-0.029
	Х6 (ОСН.)	-		-410	-1.478	89.62	-4.2	12.05
	Х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 (ост)		6.2
Х9 (ост)
Х10 (ост)
Х2 (осн)		0.08	1.6	58.4
Х3 (осн)
Х1 (осн)		0.92	18.4	823.6
Х14 (ост)	49.8	-0.08	-1.6	51.4
Х6 (осн)		-410	-8200
Х4 (осн)		0.08	1.6	56.4
Х5			-20
Z

Подчеркнем, что новый план также можно рассматривать как оптимальный, но для задачи ДЗ-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 (ост)		6.15	-615
Х9 (ост)		-10
Х10 (ост)		-89.62
Х2 (осн)	60.15	0.0769	-7.69	67.84
Х3 (осн)
Х1 (осн)	841.8	0.923	-92.3	934.1
Х14 (ост)	49.85	-0.077	7.7	42.15
Х6 (осн)		89.62	-8962
Х4 (осн)	53.15	0.0769	-7.69	60.84
Х8		-1		-100
Z		269.2	-26920

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

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