Linear Programming Output summary 7 страница

-2/5+М = у₂-(-М) ^у₂ = -2/5.

4.2. Соотношения между прямой и двойственной задачами

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

Конечно же, ничего не мешает использовать другие переменные при построении уравнений, необходимых для определения значений переменных двойственной за­дачи. Например, ограничения, ассоциируемые с переменными х_х и х₃, порождают следующие уравнения (проверьте!):

у, + 2у₂-5 = 0, у_г + Зу₂ - 4 = |.

Решение этой системы уравнений также приводит к оптимальным значениям двойст­венной задачи у, = 29/5 и у₂ = -2/5. Однако эти уравнения уже не так просты, как уравнения, ассоциируемые с переменными x_t и R. (Убедитесь самостоятельно, что уравнения, ассоциированные с любыми двумя переменными из множествах,, х_г, х₃, x_t, R, дают одни и те же значения переменных двойственной задачи.)

УПРАЖНЕНИЯ 4.2.3

1. С помощью программы TORA решите двойственную к следующей задачу ЛП и затем найдите оптимальное решение прямой задачи.

Минимизировать z = 5х, + 6х₂ + Зх₃

при ограничениях

5х, + Ьх_г + Зх₃ > 50, х, + х₂ - х₃ > 20, 7х, + 6х₂ - 9х₈ > 30, 5х, + 5х₂ + 5х₃>35, 2х, + 4х₂- 15x₈>10,

гг^ + юх^эо,

х₂ - 10*3 > 20, х„ х_г, х₃>0.

2. Дана следующая задача линейного программирования.

Максимизировать z = Ьх_х + 2х_г + Зх,

при ограничениях

х₁ + 5х₂ + 2х₃ = 30, х, - 5х₂ - 6х₃ < 40, Хр х₂, х₃>0.

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

г + 0х, + 23х₂ + 7х₃ + (5 + M)x_t + 0х₅ = 150,

где искусственная переменная х₄ и дополнительная переменная х₆ входили в начальное базисное решение. Запишите соответственную двойственную задачу и найдите ее оптимальное решение, исходя из приведенного уравнения.

Глава 4. Двойственность и анализ чувствительности

3. Дана следующая задача линейного программирования.

Максимизировать z = х_г + Ъх_г + Зх₃

при ограничениях

jc, + 2х₂ + х₃ = 3, 2л:, - х₂ = 4, x„ х₂, х₃>0.

a) Запишите соответствующую двойственную задачу.

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

4. Дана следующая задача линейного программирования.

Максимизировать z = 2лс, + 4х₂ + 4х₃ - 3x_t при ограничениях

х, + 4х₂ + x_t = 8, Хр л:₂, х₃, х₄ ^ 0.

Оптимальное решение этой задачи удовлетворяет уравнению (получено из 2-строки симплекс-таблицы)

2 + 2л:, + 0л:₂ + 0x₃ + Зх₄ = 16.

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

5. С помощью двойственной задачи найдите допустимое решение следующей системы неравенств:

2л:, + 3л:₂<12, -Зл:,+ 2л:₂<-4, Зл:, - 5х₂<2,

х_х — свободная переменная, х₂>0.

(Совет. Добавьте к этой системе неравенств тривиальную целевую функцию максимизировать z — Оде, + 0х₂ и решите двойственную задачу.)

6. Найдите оптимальное значение целевой функции следующей задачи, осно­вываясь только на свойствах ее двойственной задачи (т.е. не применяя сим­плекс-метод к двойственной задаче).

Минимизировать z = 10л:, + 4х₂ + 5х₃

при ограничениях

5л:,- 7x₂ + 3x₃>50, x_v х₂, х₃>0.

4.2.4. Вычисление симплекс-таблиц

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

4.2. Соотношения между прямой и двойственной задачами

1. Вычисление значений в столбцах ограничений симплекс-таблицы (как ле­вой, так и правой частей ограничений).

2. Вычисление значений в 2-строке.

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

'Столбец коэффициентов ограничений на i-й итерации

(Обратная матрица ^ на /'-й итерации)

Столбец исходных ^ коэффициентов ограничений J

Вычисление значений г-строки. На произвольной симплекс-итерации значения коэффициентов в г-строке вычисляются по следующей формуле 2.

'Коэффициент при j-n ^ ^f переменной в z-строке прямой задачи

Значение левой части j-ro неравенства двойственной задачи

Значение правой части у'-го неравенства двойственной задачи

Отметим, что формула 2 такая же, какая используется в методе 2 (раздел 4.2.3) для определения оптимального решения двойственной задачи.

Пример 4.2.2

На основе задачи из примера 4.2.1 покажем, как использовать формулы 1 и 2. Из оптимальной симплекс-таблицы этой задачи получаем

обратная матрица =

2/5 -1/5 1/5 2/5

С помощью формулы 1 вычислим коэффициенты в столбцах ограничений опти­мальной симплекс-таблицы.

Столбец коэффициентов ограничений, соответствующий переменной х,

'Обратная матрица

из оптимальной симплекс-таблицы,

(2/5 -V5W1-1/5 2/5 J [2

Столбец исходных коэффициентов ограничений, ^соответствующий переменной х,

(Г

Аналогично вычисляются другие столбцы коэффициентов ограничений.

Столбец коэффициентов ограничений, соответствующий переменной х₂

Столбец коэффициентов ограничений, соответствующий переменной х₃

< Столбец коэффициентов ограничений, соответствующий переменной x_t

2/5 1/5

2/5 1/5

-1/5 2/5

-1/5^ 2/5

-1/5 7/5

'2/5	-1/51		'2/5'
Ь/5	2/5 J	W

Глава 4. Двойственность и анализ чувствительности

(Столбец коэффициентов ограничений, соответствующий

переменной R

_ (2/5 -1/5

(Столбец коэффициентов ^ _! ^хг ^правых частей ограничений) \х,

1/5 2/5

2/5 -1/5 1/5 2/5

-1/5^1 2/5

1(Л

12/5^ 26/5

Теперь применим формулу 2 для вычисления коэффициентов в г-строке. Опти­мальные значения двойственных переменных (у,, у₂) =(29/5,-2/5) вычислены в примере 4.2.1 двумя различными методами. Эти значения используются для вы­числения коэффициентов в г-строке.

Коэффициент при х_х = у, + 2у₂ - 5 = 29/5 + 2х(-2/5) -5 = 0. Коэффициент при х₂ = 2у, - у₂ - 12 = 2х(29/5) - (-2/5) -12 = 0. Коэффициент при х₃ = у, + Зу₂ - 4 = 29/5 + Зх(-2/5) - 4 = 3/5. Коэффициент при x_t = у, - 0 = 29/5 - 0 = 29/5. Коэффициент при Д = у₂ - (-М) = -2/5 - (-М) = -2/5 + М.

Важно отметить, что формулы 1 и 2 можно применять на любой симплекс-итерации как к прямой, так и к двойственной задаче.

УПРАЖНЕНИЯ 4.2.4

1. В задаче из примера 4.1.2 с помощью программы TORA (выполнив команду Iterations oM-method) определите элементы симплекс-таблицы первой итера­ции. Затем с помощью формул 1 и 2 найдите значения всех элементов опти­мальной симплекс-таблицы.

2. Дана следующая задача ЛП.

Максимизировать г = 4лс₁ + 14х₂

при ограничениях

2х₁ + 7х₂ + х₃ = 21, lx_x + 2x₂ + x_t = 2l,

jc,, х₂, JCg, х₄ ^ 0.

Проверьте оптимальность и допустимость следующих базисных решений.

^f 1/7 0^,-2/7 1,

(0 1/2 1 -7/2 J

а) Базисные переменные (х₂, x_t), обратная матрица^:

Ь) Базисные переменные (х₂, х_г), обратная матрица =

ч * Г⁷/⁴⁵ -2/451

c) Базисные переменные (х₂, XJ, обратная матрица = I

(1/2 0\

d) Базисные переменные (лс,, x_t), обратная матрица =

1^-7/2 \_/

4.2. Соотношения между прямой и двойственной задачами

3. Дана следующая задача ЛП.

Максимизировать z = Зле, + 2х₂ + 5х₃

при ограничениях

х, + 2х_г + х₃ + х₄ = 30,

х, + 4х₂ + х₆ = 20, х,, х₂, х₃, х₄, х₅, х₆ > 0. Проверьте оптимальность и допустимость следующих базисных решений.

(I -1/2 0"|

а) Базисные переменные (х₄, х₃, х₆), обратная матрица =

0 1/2 0 0 0 1

Ь) Базисные переменные (х₂, х₃, х,), обратная матрица =

с) Базисные переменные (х₂, х₃, х₆), обратная матрица = 1/4 -1/8 1/8 ⁴

3/2 -1/4 -3/4

1-1 1/2 1/2,

'1/2 -1/4 0)

0 1/2 0

-2 1 1

4. Дана следующая задача ЛП.

Минимизировать z — 2х, + х₂

при ограничениях

Зх, + х₂ - х₃ = 3, 4х, + Зх₂ - х₄ = 6, х, + 2х₂ + х₆ = 3,

^Х1> ^3' ^Х4> ^ХЪ —

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

'3/5 -1/5 0"|

Базисные переменные (х_р х₂, х₆), обратная матрица = -4/5 3/5 0

I ¹ -11,

5. Дана следующая задача ЛП.

Максимизировать z = 5х, + 12х₂ + 4х₃

при ограничениях

х, + 2х₂ + х₃ + х₄ = 10, 2х,-х₂ + ЗХз = 2, X,, х₂, Х₃, Х₄ ^ 0.

а) Найдите наилучшее решение среди следующих базисных допустимых решений.

⁽\ -1/3' ч° 1/3/ '2/5 -1/51.1/5 2/5 У

i) Базисные переменные (х₄, х₃), обратная матрица = и) Базисные переменные (х₂, х,), обратная матрица =

Глава 4. Двойственность и анализ чувствительности

Ш) Базисные переменные (х₂, х₃), обратная матрица =

Ь) Присутствует ли среди них оптимальное решение? 6. В следующей таблице представлено оптимальное решение задачи максими­зации с тремя ограничениями типа "<" и неотрицательными переменными х_х и х₂. Переменные х₃, x_t и х_й являются дополнительными (остаточными) пе­ременными, соответствующими ограничениям задачи. Двумя различными способами, используя целевые функции прямой и двойственной задач, най­дите оптимальное значение целевой функции исходной задачи.

Базис	Xi	хг	Хз	х4	х5	Решение
z						?
хз					-1
хг
х1				-1

7. Рассмотрите следующую задачу ЛП.

Максимизировать z = 5х_х + 2х₂ + Зх₃

при ограничениях

л:, + Ъх₂ + 2х₃ <Ь„

*i ^{_ 5х}2 ~ ^&хг ^ ^Ь2>

х„ х₂, х₃>0.

Определите значения констант Ь_х и Ь₂, при которых симплекс-таблица с оптимальным решением имеет следующий вид.

Базис	Xi	хг	Хз	Х4	х5	Решение
z		а		d	е
Х1		Ь
х5		с	-8	-1

Константы а'Ь, с, d и е можно найти на основе данных исходной задачи и условий оптимальности и допустимости решения, представленного в симплекс-таблице.

a) Найдите значения правых частей неравенств исходной задачи, т.е. кон­станты Ь, и Ь₂.

b) Найдите значения констант а, Ь, с, d, е.

c) Найдите оптимальное решение двойственной задачи. 8. Дана следующая задача ЛП.

Максимизировать z = 2х_х + 4х₂ + 4х₃ - 3x_t при ограничениях

х, + х₂ + х₃ = 4, х_х + 4х₂ + x_t = 8, x_vx_v х₃, х₄>0.

С помощью двойственной задачи проверьте, что базисное решение (х_х, х₂) не оптимально.

3/7 -\т

1/7 2/7 J *

4.2. Соотношения между прямой и двойственной задачами

4.2.5. Значения целевых функций прямой и обратной задач

В отношениях двойственности задач ЛП, если одна задача является задачей макси­мизации, то вторая обязательно является задачей минимизации. С этой точки зрения существует такое соотношение между значениями целевых функций двух задач.

Для любой пары допустимых решений прямой и двойственной задач

Значение целевой функции^ (Значение целевой функции^ в задаче максимизации) ^ в задаче минимизации)

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

Пример 4.2.3

В примере 4.2.1 прямая и двойственная задачи имеют допустимые решения х, = 0, х₂ = 0, х₃ = 8/3 и у, = 6, у₂ = 0. Для этих решений значения целевых функций соответст­венно равны г =32/3 и w = 60. Для оптимальных решений х, = 26/5, х, = 12/5, х, = 0 и у, = 29/5, у₂ = -2/5 имеем z = w = 54,8. Таким образом, приведенные значения целевых функций подтверждают сформулированное соотношение.

Из соотношения следует, что для всех допустимых решений прямой и двойствен­ной задач значения целевой функции задачи минимизации всегда будут верхним пределом значений целевой функции задачи максимизации. Таким образом, ите­рационное решение задачи максимизации ведет к возрастанию значений целевой функции, а итерационное решение задачи минимизации — к ее убыванию. В итоге, при успешном завершении процессов вычисления прямой и двойственной задач приходим к точке "равновесия", где значения целевых функций задач максимиза­ции и минимизации становятся равными.

УПРАЖНЕНИЯ 4.2.5

1. Определите интервалы изменения значений целевой функции в следующих задачах ЛП.

a) Минимизировать г = 5дс, + 2х₂ при ограничениях

х_г-х₂>3, 2x_t + 3x₂>5, x_v х₂>0.

b) Максимизировать г = х_х + Ьх₂ + Зх₃ при ограничениях

х, + 2х₂ + х₃ = 3, 2х_х - х₂ = 4, x_v х₂, х₃>0.

c) Максимизировать z = 2х_х + х₂ при ограничениях

х,-х₂<10, 2лг,<40, дс₂>0.

Глава 4. Двойственность и анализ чувствительности

d) Максимизировать г = 3jc, + 2х₂ при ограничениях

2jc, + х_г<3, Зх, + 4х₂ > 12, х_г,х₂>0.

2. В упражнении 1, а обозначим через у_х и у₂ переменные двойственной задачи. Определите, какая из следующих пар решений прямой и двойственной задач является оптимальной.

a) дс₁ = 3,лс₂=1;у₁ = 4,у₂=1.

b) *, = 4, *_г=1;у, = 1, у, = 0.

c) jc₁ = 3,jc₂ = 0;j/₁ = 5, i/₂ = 0.

4.3. ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ДВОЙСТВЕННОСТИ

Задачу линейного программирования можно рассматривать как модель распре­деления ограниченных ресурсов, в которой целевая функция, отображающая при­быль или доход от производственной деятельности, подлежит максимизации. Если рассматривать задачу ЛП с этой точки зрения, соответствующая ей двойственная задача получает интересную экономическую интерпретацию.

Чтобы формализовать рассматриваемый вопрос, приведем еще раз общее пред­ставление прямой и двойственной задач, причем прямая задача будет играть роль модели распределения ресурсов.

Исходя из модели распределения ресурсов, прямая задача отображает п видов экономической (производственной) деятельности и возможности получения т ре­сурсов. В прямой задаче коэффициент c_j представляет собой прибыль на единицу продукции у-го вида экономической деятельности, причем на единицу продукции этого вида деятельности расходуется а_ц единиц ресурса I, максимальные запасы ко­торого ограничены величиной b_t.

Прямая задача Двойственная задача

Максимизировать z =	п	Минимизировать w =	т; = 1
при ограничениях		при ограничениях
!>,*,<*>., «= 1, 2,.. м	., т.	I» 2>„у,.£с,, У = 1,2,.. i = l
ху>0,у= 1, 2.....п.		у,-> 0, /'=1,2.....т.

4.3.1. Экономическая интерпретация переменных двойственной задачи

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

Н т

4.3. Экономическая интерпретация двойственности

Строгое равенство здесь достигается только тогда, когда решения прямой и двойст­венной задач оптимальны.

Рассмотрим сначала вариант оптимума, т.е. когда г = и>. Исходя из представления прямой задачи как модели распределения ресурсов, можно считать, что величина z соответствует величине дохода (в долларах³). Поскольку b_t — общее доступное ко­личество ресурса i, равенство z = w можно переписать следующим образом.

Доход (долл.) = ]Г (количество ресурса i) х (доход (долл.) на единицу ресурса i).

Это означает, что переменная y_t двойственной задачи должна представлять стоимость единицы ресурса i. (Данное понятие уже вводилось в разделе 2.3.3, ис­ходя из графического представления задачи ЛП.) В литературе по исследованию операций переменные y_t двойственной задачи часто называют двойственными ценами. Кроме того, иногда их именуют теневыми ценами и симплексными мультипликаторами.

Аналогично для любой пары допустимых решений прямой и двойственной за­дач неравенство z <w можно интерпретировать следующим образом:

доход < общая стоимость ресурсов.

Это соотношение показывает, что до тех пор, пока суммарный доход от всех видов деятельности строго меньше суммарной стоимости всех используемых ре­сурсов, решение как прямой, так и двойственной задачи не может быть опти­мальным. Оптимум (максимальный доход) может быть достигнут только тогда, когда все потребляемые ресурсы использованы полностью. Если модель ЛП рас­сматривать более обще как модель некой системы, имеющую "вход" и "выход", то потребляемые ресурсы характеризуют "вход" этой системы, а получаемый до­ход— ее "выход". Система будет находиться в нестабильном (неоптимальном) состоянии, пока вход превышает выход. Устойчивое состояние системы характе­ризуется равенством входа и выхода.

Пример 4.3.1

Приведем формулировки прямой и двойственной задач, описывающие модель про­изводства компании Reddy Mikks из примера 2.1.1.

Прямая задача

Двойственная задача

Максимизировать z= 5xi + 4хг при ограничениях

6xi + 4X2 i 24 (ресурс 1, сырье М1), Xi + 2X2 < 6 (ресурс 2, сырье М2), -Xi + хг < 1 (ресурс 3), хг < 2 (ресурс 3), Хь х₂ > 0.

Минимизировать w= 24yi + буг + уз + 2у₄

при ограничениях

6yi + уг - Уз S 5,

4yi + 2уг + уз + уд > 4,

У1.У2, Уз, У4>0.

Оптимальное решение: x! =3, х₂ = 1,5, z= 21

Оптимальное решение:

yi = 0,75, уг = 0,5, у₃ = у₄ = 0, w= 21

Читатель вместо долларов может, конечно, подставить любую другую денежную едини­цу — это не принципиально для понимания изложенного материала. — Прим. ред.

Глава 4. Двойственность и анализ чувствительности

Напомним вкратце, что в этой модели описывается производство двух видов краски (для внутренних и наружных работ) на основе двух видов сырья Ml и М2 (ресурсы 1 и 2) с учетом рыночных условий, выражаемых третьим и четвертым ограничениями. Зада­ча состоит в определении объемов производства красок каждого вида (в тоннах), при которых будет получен максимальный доход (в тыс. долл.).

Оптимальное решение двойственной задачи показывает, что стоимость единицы первого ресурса (сырье Ml) составляет у, = 0,75 (или 750 долл. за тонну), а второго (сырье М2) — у₂ = 0,5 (или 500 долл. за тонну). В разделе 2.3.3 мы графически по­казали, что приведенные значения стоимостей справедливы, если значение первого ресурса не выходит из интервала (20, 36), а второго — из интервала (4, 6,67) (эти же результаты алгебраически будут получены в разделе 4.5.1). Таким образом, расход сырья Ml может возрасти с 24 до 36 тонн, что приведет к соответствующему увеличению дохода на величину 12 х 750 = 9000 долл. Аналогично количество вто­рого ресурса (сырье М2) можно увеличить с 6 до 6,67 тонн с увеличением дохода на величину 0,67 х 500 = 335 долл. Но еще раз напомним, что подобные расчеты при­менимы только тогда, когда увеличение числа используемых ресурсов не выходит за приведенные выше интервалы значений. Конечно, это не означает, что количе­ство используемых ресурсов в принципе не может выходить за указанные пределы. Однако приведенные выше стоимости ресурсов определены только для ситуации, когда количество этих ресурсов не выходит за указанные пределы.

Для третьего и четвертого ресурсов двойственные цены (оптимальное решение двойственной задачи) равны нулю. Это указывает на то, что данные ресурсы неде- фицитны. Поэтому их стоимость равна нулю. _

УПРАЖНЕНИЯ 4.3.1

1. В задаче из примера 4.3.1 подсчитайте оптимальный доход при выполнении следующих условий.

a) Ограничение для первого ресурса: &х_г + 4х₂ < 22.

b) Ограничение для второго ресурса: х, + 2х₂ < 4,5.

c) Четвертое ограничение: х₂ < 10.

2. Электротехническая компания NWAC производит четыре типа кабеля для оборонного ведомства. Каждый тип кабеля подвергается четырем последова­тельным операциям: разделка, пайка, оплетка и проверка. В следующей таб­лице приведены данные, характеризующие производство кабелей.

Тип Затраты времени на изделие (в минутах) Доход

кабеля	Разделка	Пайка	Оплетка	Проверка	(долл.)
SC320	10,5	20,4	3,2	5,0	9,40
SC325	9,3	24,6	2,5	5,0	10,80
SC340	11,6	17,7	3,6	5,0	8,75
SC370	8,2	26,5	5,5	5,0	7,80
Ежедневный фонд рабочего	4800,0	9600,0	4700,0	4500,0

времени (в минутах)

Оборонное ведомство гарантирует для компании минимальный уровень про­изводства в 100 единиц каждого типа кабеля.

4.3. Экономическая интерпретация двойственности

a) Сформулируйте задачу линейного программирования и с помощью про­граммы TORA найдите ее оптимальное решение.

b) Основываясь на двойственных ценах, приведенных программой TORA, определите возможное увеличение ежедневного фонда времени по каждой технологической операции.

c) Выгодно ли компании выполнение требования заданного минимального уровня производства? Обоснуйте ответ, основываясь на величинах двой­ственных цен.

d) Возможно ли увеличение на 10% временного фонда операции пайки с со­хранением величины ее вклада в суммарный доход, определяемый теку­щей двойственной ценой?

3. Компания производит кожаные чехлы и сумки. На производство одного чех­ла требуется 8 м² кожи и 12 часов рабочего времени, на производство сум­ки — 2 м² кожи и 5 часов рабочего времени. Текущие еженедельные ресурсы производства ограничены 1200 м² кожи и 1850 часами рабочего времени. Компания продает чехлы и сумки по цене 350 и 120 долл. соответственно. Определите для этой компании схему производства, максимизирующую чис­тую прибыль. Допустим, компания желает расширить свое производство. Какова максимальная цена, по которой компании имеет смысл закупать до­полнительную кожу? А какова допустимая максимальная цена дополни­тельных трудовых ресурсов?

4.3.2. Экономическая интерпретация ограничений двойственной задачи

Для интерпретации ограничений двойственной задачи используем формулу 2 из раздела 4.2.4. В соответствии с этим соотношением на любой итерации решения прямой задачи справедливо равенство

коэффициент при x_t в z-строке = ^а,_ЛУ, - с,.

Условие оптимальности симплекс-метода в задаче максимизации говорит о том, что у'-й вид деятельности (переменная х}, не представленный в текущем базисном ре­шении, можно ввести в базис для увеличения дохода только тогда, когда коэффици­ент при Xj в z-строке (равный ^".а^У; -с_у) будет неотрицательным. В рамках предла­гаемой экономической интерпретации это означает, что у'-й вид деятельности должен быть представлен в базисном решении, если выполняется следующее неравенство.

Стоимость всех ресурсов, используемых' для производства единицы продукции j-то вида деятельности

' Доход от реализации ' единицы продукции 7-го вида деятельности

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

Приведем стандартные определения, используемые в литературе по линейному

программированию. Введем обозначение z, = Х™₁я,уУ,- ■ Величина z^ представляет сум­марную стоимость ресурсов, используемых на производство единицы продукции j-ro вида деятельности. Величина z. - с. равна коэффициенту при x_j в z-строке симплекс-таблицы и часто называется приведенной стоимостью (приведенными издержками)

Глава 4. Двойственность и анализ чувствительности

у'-го вида деятельности. В некоторых случаях разности z_t - c_j = ^Га<,У, - c_f используют-

ся непосредственно для вычисления коэффициентов в г-строке симплекс-таблицы (вместо метода Гаусса-Жордана). Такие вычисления используются в модифициро­ванном симплекс-методе (этот метод описан в главе 7).

Пример 4.3.2

Фабрика игрушек TOYCO собирает три вида игрушек: модели поездов, грузовиков и легковых автомобилей; при сборке каждого вида используется три типа операций. Ежедневный фонд рабочего времени на каждую операцию ограничен предельными ве­личинами 430, 460 и 420 минут. Доход на одну игрушку каждого вида составляет соот­ветственно 3, 2 и 5 долл. На каждой из трех операций для сборки модели поезда тре­буется 1, 2 и 1 минуты рабочего времени. Соответствующее время для сборки моделей грузовиков и легковых автомобилей составляет (2,0, 4) и (1, 2, 0) минут (нуль указы­вает на то, что соответствующая операция не выполняется).

Обозначив через х_р х₂ и х₃ количество собираемых ежедневно моделей трех видов, получаем прямую и двойственную задачи ЛП.

Прямая задача	Двойственная задача
Максимизировать z=3xi + 2хг + 5х3	Минимизировать w= 430yi + 460уг + 420у3
при ограничениях	при ограничениях
xi + 2x2 + хз < 430 (операция 1),	yi + Зу2 + Уз ^ 3,
3xi + 2х3 < 460 (операция 2),	2yi + 4у3 > 2,
xi + 4X2 S 420 (операция 3),	yi + 2у2 > 5,
xi, х2, хз >0.	yi, Уг, Уз^О.
Оптимальное решение xi = 0, х2 = 100, х3 = 230, г= 1350 долл.	Оптимальное решение У1 = 1. Уг = 2, уз = 0, w = 1350 долл.

Оптимальное решение предусматривает производство моделей грузовых (х₂ = 100) и легковых (х₃ = 230) автомобилей и требует отказа от производства моделей поездов (х, = 0). Это означает, что в текущей экономической ситуации производство моделей поездов нерентабельно. Вместе с тем, рынок игрушек требует выпуска этого вида мо­делей. Как сделать их производство доходным? В соответствии с экономической ин­терпретацией задач ЛП, приведенной в этом разделе, производство моделей поездов будет выгодным только тогда, когда будет выполняться неравенство z, < с,. Для вы­полнения этого неравенства нужно либо повысить коэффициент с, (доход от продажи одной модели поезда), например путем увеличения цены модели, либо снизить стои­мость ресурсов z, (= у, + Зу₂ + у₃), необходимых для производства этих игрушек. Уве­личение цены игрушек не желательно, так как это снизит их конкурентоспособность на рынке игрушек. Уменьшение величины коэффициента z, более привлекательно, поскольку для этого надо просто сократить время выполнения операций, необходи­мых для производства моделей поездов. Обозначим через r_v г_г и г₃ величины, пропор­циональные долям сокращения времени соответствующих операций. Эти величины находим из условия, чтобы новая стоимость производственных операций не превы­шала доход от одной модели поезда. Это условие записывается следующим образом.