А. Кофман и Р. Фор. Займемся исследованием операций (стр. 29 )

Таким образом, получают столбцы от Р1 до Р6 и Р0. Теперь изменяют таблицу Сi, Pi, стоящую слева, принимая во внимание выполненное замещение столбца. Под ценами Cj записывают также новое решение и вычисляют новое значение целевой функции F = 40/3.

4) Затем снова проделываются описанные итерации.

Пример. 1) Δ1 = — 1/3, Δ3 = 4 и т. д. Имеем е = 3.

Отметим, что новые Δj можно получить, вычитая из Δj предыдущей таблицы произведения элементов новой строки s на Δе.

2) Вычисляют частные , наименьшее положительное из

которых есть 14/15, откуда s = 5.

Читатель может выполнить вычисления, которые содержат еще две итерации, чтобы прийти к таблице

Цена	Базисный столбец
Сi	Pi		P1	P2	P3	P4	P5	P6		P0
5	P2		0	1	0	15/41	8/41	-10/41		50/41
4	P3		0	0	1	-6/41	5/41	4/41		62/41
3	P1		1	0	0	-2/41	-12/41	15/41		89/41
	Cj		3	5	4	0	0	0
Решение						0	0	0	F=

Заметим, что, если бы речь шла о минимизации функции F, было бы достаточно записать, что нужно максимизировать — F и переписать ограничения

в виде

.

Понятие двойственности.

Рассмотрим следующую исходную задачу линейного программирования:

с целевой функцией, подлежащей минимизации, F = 20x1 + 40x2, и, само собой разумеется, условиями неотрицательности переменных.

Рис. 13.3.

Резюмируем это в форме таблицы; показано, что этой прямой задаче соответствует двойственная задача, которая немедленно считывается с таблицы и записывается в виде

y1 + y2 ≤ 20,

y2 + 3y3 ≤ 40

с экономической функцией, подлежащей максимизации,

Ф = 2y1 + 3y2 + 2y3.

	x1	x2	≥
y1	1	0		2
y2	1	1		3
y3	0	3		2
≥
	20	40		OP

Можно решить графически обе эти задачи.

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

Мы можем иметь в качестве решения только координаты A или B; направление целевой функции показывает, что речь идет о точке A, для которой:

х1 = 7/3, х2 = 2/3.

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

Направление плоскости D показывает, что решением является точка P:

y1 = 0, y2 = 20, y3 = 20/3.

Мы констатируем на основании рис. 13.3,а и 13.3,б, что решение первой задачи дает в качестве значения целевой функции

F = 20 ∙ (7/3) + 40 ∙ (2/3) = 220/3,

тогда как решение второй таково, что

Ф = 2 ∙ 0 + 3 ∙ 20 + 2∙(20/3) = 220/3.

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

Более того, если бы мы записали дополненные задачи с их свободными переменными

x1 - x3 = 2. y1 + y2 + y4 = 20,

. y2 + 3y3+ y5 = 40,

x1 + x2 - x4 = 3.

3x2 - x5 = 2.

то для первой имели бы:

Значения переменных х1 = 7/3, х2 = 2/3, х3 = 1/3, x4 = 0, х5 = 0,

Маргинальные цены Δ1 =0, Δ2 = 0, Δ3 = 0, Δ4 = 20, Δ5 = ,

а для второй:

Значения переменных y1 =0, y2 = 20, у3 = 20/3, y4 = 0, y5 = 0.

Маргинальные цены 1/3, 0, 0, 7/3, 2/3.

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

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

ГЛАВА 14. Нет ли свободных мест? (Выбор критерия в условиях неопределенности)

Сегодня на больших туристских дорогах Мексики можно найти такие же мотели, как и в США; хотя их еще мало, но они уже пользуются большим успехом. Поэтому когда вы подъезжаете к столице, начинайте искать на фронтонах этих заведений надпись «места есть» или «мест нет». Как легко догадаться, повсюду мотели наводнены гринго. Но теперь в свою очередь и мексиканцы оценили эти мотели. Вот почему наш друг Сальвадор Арнольдо решает вложить свои сбережения в эксплуатацию мотеля у въезда в Мехико. Сальвадор располагает несколькими миллионами песо; он купил за песо прекрасную площадку на обочине дороги. Он предполагает построить на этой площадке мотель, но не знает еще, сколько комнат нужно там оборудовать: 20, 30, 40 или 50.

Смета необходимых затрат следующая:

1°. Ежегодные затраты, не зависящие от числа построенных комнат S

Благоустройство территории 100000 песо. Допускается, что постройка и благоустройство будут длиться в течение 10 лет, указанные затраты будут также погашаться десять лет. Отсюда годовая часть затрат на первичное благоустройство составляет …....................................................................................	10000 песо
Затраты на ремонт и содержание. Допускается, что затраты составляют фиксированную величину, не зависящую от числа комнат и пропорциональную важности здания. Эта фиксированная часть затрат в год равна …………………………………….	1 500 песо
Один ночной дежурный (15 песо в день). Пусть вместе с различными премиями это составляет в год ……………………………...	6000 песо
Один служащий, для уборки (20 песо в день). Пусть вместе с дополнительной оплатой в год ………………………………………..	8000 песо
Стоимость покупки площадки не учитывается, так как стоимость этой недвижимости полагается примерно равной капиталу, который она собой представляет, вложенному в банк с обычными процентами ……………………………………	—
Итого, общие фиксированные ежегодные затраты ……………….	25500 песо

2°. Ежегодные затраты, пропорциональные числу построенных комнат

(в песо)

S =	20	30	40	50
Постройка, благоустройство, меблировка комнат. Одна комната стоит 4000 песо, и практически амортизация длится 10 лет, что дает при различных предположениях ……….	80 000
На 10 комнат полагается одна горничная; ежегодные затраты, включая дополнительные расходы, составляют 6000 песо на одну горничную. Получаем ………………….	12 000	18 000	24 000	30 000
Содержание и ремонт (пропорциональная часть) 150 песо в год на одну комнату. Всего …………………..	3 000	4 500	6 000	7 500
Страхование на случай пожара (25 песо за комнату в год), откуда …….	500	750	1 000	1 250
Итого ……	95 500

3°. Ежегодные затраты, пропорциональные среднему числу R занятых комнат [72]

R =	0	10	20	30	40	50
Стирка, уборка: 5 песо в день на комнату ………….	0	18 000	36 000	54 000	72 000	90 000
Электричество, газ и вода: 5 песо в день на комнату	0	18000	36000	54 000	72 000	90 000
Итого ……	0	36 000	72 000

С другой стороны, смета доходов может быть составлена следующим образом: