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

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

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

2х_х + х₂ + х₃ < 2, Зх, + 4х₂ + 2х₃ > 8, x_v х₂, х₃>0.

Используя М-метод в программе TORA, покажите, что оптимальное решение этой задачи содержит искусственную базисную переменную, значение этой переменной равно нулю. Имеет ли задача допустимое оптимальное решение?

ЛИТЕРАТУРА

1. Bazaraa М., Jarvis J., Sherali М. Linear Programming and Network Flows, 2nd ed., Wiley, New York, 1990.

2. Dantzig G. Linear Programming and Extensions, Princeton University Press, Prin­ceton, N.J., 1963. (Русский перевод: Данциг Дж. Линейное программирование, его применение и обобщение. — М.: Прогресс, 1966.)

3. Dantzig G., Thapa М. Linear Programming 1: Introdution, Springer, New York, 1997.

4. Nering E., Tucker A. Linear Programming and Related Problems, Academic Press, Boston, 1992.

5. Schrage L. Optimization Modeling with LINGO, LINGO Systems, Inc., Chicago, 1999.

6. Taha H. Linear Programming, Chapter II—1 in Handbook of Operations Research, J. Moder and S. Elmaghraby (eds.), Van Nostrand Reinhold, New York, 1978. (Русский перевод: Исследование операций: в 2-х томах. Под ред. Дж. Моудера, С. Элмаграби. — М.: Мир, 1981.)

Глава 3. Симплекс-метод

Литература, добавленная при переводе

1. Ашманов С. А. Линейное программирование. — М.: Наука, 1981.

2. Гольштейн Е. Г., Юдин Д. Б. Линейное программирование: Теория, методы и приложения. — М.: Наука, 1969.

3. Мур Дж., Уэдерфорд Л. Экономическое моделирование в Microsoft Excel. — М.: Издательский дом "Вильяме", 2004.

КОМПЛЕКСНЫЕ ЗАДАЧИ

3.1. Небольшой консервный завод производит пять типов консервов на основе трех видов свежих фруктов. Завод имеет два производственных цеха, кото­рые при необходимости могут наращивать выпуск продукции. В настоящее время производственные цеха работают в одну смену, но без труда могут пе­рейти на двух- или трехсменную работу. Реальным ограничением наращи­вания выпуска продукции является только объем поставляемых на перера­ботку свежих фруктов. Поскольку объемы холодильных камер ограничены, желательно, чтобы все фрукты перерабатывались в течение рабочего дня.

Молодой аналитик, специалист по исследованию операций, горит желанием увеличить уровень производства этого завода. После анализа производствен­ной ситуации он сформулировал задачу линейного программирования. Зада­ча включает пять переменных (для пяти видов продукции) и три ограничения (для трех видов сырья). Теория ЛП говорит о том, что в задаче с пятью пере­менными и тремя ограничениями оптимальное решение не может содержать более трех базисных переменных. Следовательно, оптимальное решение предполагает производство не более трех видов продукции. "Ага, — подумал

аналитик, — производство этой компании явно не оптимально."

Он добился встречи с менеджером по производству для обсуждения построен­ной модели ЛП. Менеджер, подробно ознакомившись с задачей, нашел, что модель адекватно отображает сложившуюся производственную ситуацию.

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

Это предложение немного смутило аналитика, так как очевидно, что до­бавление новых ограничений не может улучшить оптимальное решение, однако он смог честно ответить менеджеру, что данное предложение со­гласуется с теорией ЛП.

Как разрешить этот "парадокс"?

3.2. Транспортная компания, специализирующаяся на перевозках грузов, имеет множество терминалов, расположенных в "стратегических" точках по всей

Комплексные задачи

территории США.* Когда грузы поступают на терминал, они сортируются: часть груза, предназначенная местному потребителю, ему же и поступает, ос­тальной груз отправляется к следующему терминалу. Терминальные доки об­служивают как постоянные, так и временные работники, набираемые по най­му. Постоянным работникам гарантирована 40-часовая рабочая неделя. Они работают в одну из трех стандартных смен непрерывно в течение пяти дней, но их рабочая неделя может начаться в любой день недели. Временные работники нанимаются на любое количество рабочих часов при пиковых поступлениях грузов, превышающих возможности их обработки постоянными работниками.

Грузы могут поступать на терминалы в любое время, причем неравномерно в течение суток. Изучение статистических данных показывает, что распре­деление поступления грузов примерно одинаково каждую неделю, и пик по­ступления грузов обычно приходится на конец недели (пятница-воскресение). Политика компании требует, чтобы грузы задерживались на терминалах не более, чем на 16 часов.

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

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

ГЛАВА 4

ДВОЙСТВЕННОСТЬ И АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ

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

Мы уже встречались с анализом чувствительности (на элементарном уровне) в разделе 2.3. В этой главе мы подробнее рассмотрим методы анализа чувствитель­ности, основанные на теории двойственности.

4.1. ОПРЕДЕЛЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ

Исходную задачу линейного программирования будем называть прямой. Двой­ственная задача — это задача, формулируемая с помощью определенных правил непосредственно из прямой задачи. В этом разделе рассмотрены правила построе­ния двойственных задач.

При изложении теории двойственности часто рассматривают формулировки двой­ственной задачи в зависимости от различных видов прямой задачи, которые опреде­ляются типами ограничений, знаками переменных (неотрицательные или свободные, т.е. без ограничения в знаке) и типом оптимизации (максимизация или минимизация целевой функции). Такая "привязка" двойственной задачи к исходной не всегда оп­равдана (см. упражнение 4.1.7). В этой книге приводится единая формулировка двойственной задачи, применимая ко всем видам прямой задачи. В основу такой формулировки положена стандартная форма прямой задачи (см. раздел 3.1). На­помним, что задача ЛП в стандартной форме записывается следующим образом.

Максимизировать или минимизировать целевую функцию г = при ограничениях

д:.>0,; = 1,2.....п.

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

В состав п переменных х_} входят также дополнительные переменные. Стандарт­ная форма задачи ЛП предполагает выполнение следующих условий.

1. Все ограничения записаны в виде равенств с неотрицательной правой частью.

2. Все переменные неотрицательны.

3. Оптимизация определяется как максимизация или минимизация целевой функции.

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

Переменные и ограничения двойственной задачи формируются путем симмет­ричных структурных преобразований прямой задачи по следующим правилам.

1. Каждому из т ограничений прямой задачи соответствует переменная двой­ственной задачи.

2. Каждой из п переменных прямой задачи соответствует ограничение двойст­венной задачи.

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

4. Коэффициенты целевой функции двойственной задачи равны правым частям ограничений прямой задачи.

Графически эти правила представлены в табл. 4.1.

Таблица 4.1.	Формирование двойственной задачи из прямой
Переменные		Переменные прямой задачи
двойственной			X,	Хп
задачи	С1		С,	Сп
У1	an	ai2	... ■ в,;	a-in
У2	a2i	Э22	Оц	Эгл		щшшшш шШШШвШ
Уп	ami			Этл		шШШШШШШШШШФШ Ьт
			j-e ограничение двойственной задачи	Коэффициенты целевой функции двойственной задачи

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

4.1. Определение двойственной задачи 143

Таблица 4.2. Правила определения типа оптимизации и ограничений

Целевая функция		Двойственная задача
прямой задачи	Целевая функция	Тип ограничений	Переменные
Максимизация	Минимизация	>	Свободные
Минимизация	Максимизация	<	Свободные

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

Пример 4.1.1

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

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

Максимизировать z= 5xi + 12х2+4хз

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

Xi + 2X2 +Хз < 10,

2xi - хг + Зхз = 8,

Х1, Х2, Хз > 0.

Максимизировать 2= 5xi + 12x2 + 4хз + Ох»

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

Х1 + 2X2 + Хз + Х4 = 10,

2xi - хг + Зхз + 0x4 = 8,

X1, Х2, Хз, Х4 ^ 0.

У1

У2

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

Минимизировать w = 10у₁ + 8у₂

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

у, + 2у₂>5, 2у,-у₂>12, у₁ + 3у₃>4,

у. + 0у, > 0, 1

} => (у, > 0, у, — свободная переменная). у,,у₂ —свободные]

Пример 4.1.2

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

Минимизировать г = 15xi + 12хг Минимизировать z= 15xi + 12хг + Охз + 0x4 при ограничениях при ограничениях

Х1 + 2X2 ^3, Х1 + 2X2 - Хз + 0X4= 3, /1

2xi - 4x2 < 5, 2xi - 4X2 + Охз + х₄ = 5, уг

X1,X₂>0. X1, Х2, Хз, Х4>0.

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

Максимизировать w = 3y_t + 5у₂

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

у, + 2у₂<15, 2у,-4у₂<12, -у^ОСилиу^О),

у,, у₂ — свободные переменные (избыточное условие).

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

Пример 4.1.3

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

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

Двойственные переменные

Максимизировать г = 5xi + 6x2

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

xi + 2x2 = 5, -Х1 + 5x2 > 3,

4xi + 7x2 < 8,

xi — свободная,

x₂>0.

Подстановка дг, = дг* - х~ приводит к задаче:

максимизировать г = 5x1 - 5л:," + 6х₂ при ограничениях

xl - х^ + 2x2 = 5,

- xl + ДГ," + 5X2 - Хз =3,

4лг* - 4л," + 7хг + Х4 = 8,

л,*, ЛГ,", Х2 > 0.

У1

У2

Уз

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

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

Минимизировать w = 5у, + Зу₂ + 8у₃

у,-у,+4у₃>5 1 -У, + У,-4у₃>-5

2у, + 5у₂+7у₃>6,

-y₂>0^y₂<0,

У₃*0,

у, — свободная переменная,

у₂, Уз — свободные переменные (избыточное условие).

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

УПРАЖНЕНИЯ 4.1

1. Для задачи из примера 4.1.1 запишите двойственную задачу, предполагая, что определяется не максимум целевой функции, а ее минимум.

2. В примере 4.1.2 сформулируйте двойственную задачу, предполагая, что в прямой задаче этого примера добавлено третье ограничение Злг, + х₂ = 4.

3. На основе задачи из примера 4.1.3 покажите, что даже если изменить тип оп­тимизации (с максимизации на минимизацию целевой функции), то все рав­но свободным переменным прямой задачи будут соответствовать в двойст­венной задаче ограничения в виде равенств.

4. Запишите двойственные задачи для следующих прямых задач ЛП.

a) Максимизировать z = -5x, + 2х₂

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

4.1. Определение двойственной задачи

2х₁ + Зх_г < 5, х„ х_г>0.

c) Минимизировать z = 6х, + Зх₂ при ограничениях

6х, - Зх₂ + х₃ > 2, Зх, + 4х₂ + х₃ > 5, х„ х₂, х₃>0.

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

2*, + х₂= 5, Зх, - х₂ = 6,

х,, х₂ — свободные переменные.

5. Вернитесь к задаче из примера 4.1.1. Применение симплекс-метода к прямой задаче ЛП, записанной в стандартной форме, требует введения искусственной переменной во второе ограничение для получения начального базисного реше­ния. Покажите, что введение искусственной переменной не влияет на построе­ние двойственной задачи, поскольку искусственная переменная прямой задачи порождает избыточное ограничение двойственной задачи.

6. Истинны или ложны следующие утверждения?

a) Задача, двойственная к двойственной, совпадает с исходной прямой задачей.

b) Если в прямой задаче есть ограничение в виде равенства, то соответст­вующая переменная двойственной задачи обязательно будет свободной.

c) Если в прямой задаче ограничение имеет вид неравенства типа "<", то со­ответствующая переменная в двойственной задаче будет неотрицательной (неположительной), в зависимости от того, следует в прямой задаче мак­симизировать или минимизировать целевую функцию.

d) Если в прямой задаче ограничение является неравенством типа ">", то со­ответствующая переменная в двойственной задаче будет неотрицательной (неположительной), в зависимости от того, следует в прямой задаче ми­нимизировать или максимизировать целевую функцию.

e) Свободная переменная прямой задачи порождает в двойственной задаче ограничение в виде равенства.

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

Задача максимизации		Задача минимизации
Ограничения		Пеоеменные
>	о	<0
<	о	>0
=	о	Свободная
Пеоеменные		Ограничения
>0	о	>
<0	<=>	<
Свободная	о	=

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

4.2. СООТНОШЕНИЯ МЕЖДУ ПРЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧАМИ

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

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

4.2.1. Обзор простых матричных операций

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

1. Матрица А порядка тхп — это прямоугольный массив элементов с т строками и п столбцами.

2. Вектор-строка V размерности п — матрица порядка 1 х п.

3. Вектор-столбец Р размерности т — матрица порядка mxl.

Эти определения математически можно представить следующим образом.

			ч	а12.			V
V = (i	',,v2,.	••.v„), А =	«2.	а21.	■ а2п	, Р =	Pi
				ат2 ■

Теперь определим три матричные операции умножения.

1. Умножение вектор-строки V на матрицу А: V х А. Эта операция определе­на только тогда, когда количество элементов в вектор-строке V равно числу строк в матрице А.

Например,

'1 2^

(11,22,33) 3 4

_ч5 6)

VxA = Xv^,,£vyi,₂,...,£v,a,,

= (1x11 + 3x22 + 5x33, 2x11+4x22 + 6x33) = (242,308).

2. Умножение матрицы А на вектор-столбец Р: А х Р. Эта операция опреде­лена только тогда, когда количество столбцов матрицы А равно количеству элементов вектор-столбца Р.

¹ В приложении А приведен более полный обзор теории матриц.

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

АхР =

Например,

1 3 5

2 4 6

1П

11x1 + 22x3 + 33x5 11x2 + 22x4 + 33x6 242 308

Умножение скаляра на матрицу. При умножении скаляра (константы) а на матрицу А, осА, получаем матрицу порядка т х п, у которой (i,;')-й элемент равен aa_tj. Например, для а = 10 имеем

Л 2 Ъ\ (10 20 301 (10)'

4 5 6) {40 50 60

В общем случае ссА = Аа. Этим же свойством обладает операция умножения вектора на скаляр: ctV = Va и aP = Pa.

УПРАЖНЕНИЯ 4.2.1

1. Даны следующие матрицы.

fl 4^

2 5

3 6

ГП

3J

V,-(ll,22), V₂ = (-1,-2,-3).

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

a) AV,.

b) АР,.

c) АР₂.

d) V,A.

e) V₂A. О Р,Р₂. g) V.P..

4.2.2. Структура симплекс-таблицы

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

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

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

эффициенты на главной диагонали равны 1, а все внедиагональные — 0). Сохра­няя ту же структуру таблицы, после серии симплекс-преобразований методом Га-усса-Жордана получим то, что называется обратной матрицей. Как будет показано далее в этой главе, обратная матрица играет ключевую роль при вычислении всех элементов симплекс-таблиц.

z-строка целевой функции

Начальные базисные переменные

Столбцы коэффициентов < ограничений

□

	0 •	• 0
	1 •	•• 0
	0 •	• 1

(Начальная таблица)

Единичная матрица

z-строка целевой функции

Начальные базисные переменные

Столбцы коэффициентов < ограничений

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

□

(Общая таблица)

Рис. 4.1. Схематическое представление начальной и общих симплекс-таблиц

УПРАЖНЕНИЯ 4.2.2

1. Вернитесь к таблице с оптимальным решением примера 3.3.1.

a) Определите в этой таблице обратную матрицу.

b) Покажите, что вектор значений в столбце "Решение" (без значения z-строки) равен произведению обратной матрицы на вектор правых частей исход­ных ограничений.

2. Повторите упражнение 1 для последней таблицы примера 3.4.1.

4.2.3. Оптимальное решение двойственной задачи

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

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

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

' Обратная матрица ' в оптимуме прямой задачи

Метод 1

. (Вектор-строка исходных

I Оптимальные значения)

_ч _ коэффициентов целевой функции

двойственных -

при базисных переменных

переменных)

{ в оптимуме прямой задачи Элементы в вектор-строке исходных коэффициентов целевой функции должны быть перечислены в таком порядке, в каком базисные переменные перечислены встолбце "Базис" в симплекс-таблице. Этот метод рассмотрен в примере 4.2.1.

Метод 2

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

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

'Разность между левой и правой⁴ частями j-то неравенства двойственной задачи

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

Пример 4.2.1

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

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

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

х₁ + 2х₂+х₃<10, 2х_х -х₂ + Зх₃ = 8, х_г,х_г, х₃>0.

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

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

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

xi +2x2 + Хз + х4 = 10,

2х1-х₂ + Зх₃ + Я=8,

xiI х2, Хз, Хд, Я> 0.

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

Минимизировать w= 10yi + 8уг при ограничениях У1 + 2у₂ > 5, 2у, -у₂> 12, yi + Зу₂ > 4,

yi > 0, уг > -М (уг — свободная переменная).

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

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

Итерация	Базис	Х1	хг	хз	Xt	Я		Решение
	г	-5-2М	-12 + М	^4-ЗМ				-8М
	х4
	Я		-1				В
	z	-7/3	-40/3			43 + М		32/3
	Х4	1/3	7/3			-1/3	1 |	22/3
	хз	2/3	-1/3			1/3		8/3
	Z	-3/7			40 7	-4'3 + М		368/7
	хг	1/7			3/7	-1/7		22/7
	хз	5/7			1/7	2/7		26/7
	Z			3/5	29'5	-2/5 + М		274/5
	хг			-1/5	2/5	-1/5		12/5
	Х1			7/5	1/5	2/5		26/5

Г2/5 -1/5⁴!

Обратная матрица симплекс-таблицы с оптимальным решением имеет вид I j.

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

Метод 1. Заметим, что базисные переменные в оптимальной симплекс-таблице в столбце "Базис" записаны в таком порядке, что сначала идет х₂, а затем х_х. По­этому в вектор-строке первоначальных коэффициентов целевой функции коэффи­циенты этих двух переменных должны идти в том же порядке:

(вектор коэффициентов) = (коэффициент при х₂, коэффициент при х_г) = (12, 5).

Оптимальное решение двойственной задачи вычисляется так:

(2/5 -\/5\

(у,, у₂) = (вектор коэффициентов) х (обратная матрица) = (12,5) =(29/5,-2/5).

V V' 2/5)

Метод 2. Поскольку двойственная задача имеет две переменные, необходимо два уравнения, чтобы найти их значения. Сначала посмотрим, как ограничения двой­ственной задачи связаны с переменными х₄ и R, составляющими первоначальный базис прямой задачи.

Переменная х₄: у,>0, Переменная R: у₂ > -М. Из симплекс-таблицы с оптимальным решением имеем

коэффициент в z-строке при x_t = 29/5, коэффициент в z-строке при R = -2/5 + М. Теперь, следуя методу 2, получаем систему уравнений 29/5 = у,-0 => у, = 29/5,