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

Рис. 12.2. Блок — схема моделирования (рассчитанного на 700 дней).

С1 – ежедневные затраты на одного постоянного гида. С2 – ежедневные затраты на одного дополнительного гида. С3 – убытки от необслуженных экскурсантов. S – число постоянных имеющихся гидов. dj – спрос в день j. Oj – предложение в день j. Символ : означает «сравнить с», ® символизирует введение последовательностей случайных чисел.

Таблицы 12.8 и 12.9 дают пример моделирования той же искусственной недели, что и на таблице 12.7, но при S = 9 и S=11.

Рассматривая каждый раз по 100 искусственных недель и вычисляя балансы для S = 8, 9, 10, 11, 12, 13, 14 и 15, мы найдем, что минимум суммарных затрат достигается при[61] S = 12; этому соответствует значение еженедельных затрат, равное 4860 песо.

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

Теперь было бы интересно посмотреть, как решить эту задачу аналитическим способом.

Моделирование и аналитические методы

Обозначим через X случайную величину, представляющую собой ежедневный спрос, через p(х) — вероятность спроса х, которая задается с помощью таблицы 12.1 для х = 4, 5, 6, ... 16; для остальных значений х вероятность р(х) равна нулю. Через Y обозначим случайную величину, представляющую собой ежедневное предложение, через q1 (у) — вероятность предложения у (в будний день), где у = 0, 1, 2, . . ., 7, q2(y) — вероятность предложения у (в воскресные дни), где y = 0, 1, 2, Распределения вероятностей q1(y) и q2(y) заданы соответственно таблицами 12.2 и 12.3; для остальных значений у вероятности равны нулю.

Для конкретных значений х из X и у из Y издержки одного дня в предположении, что число постоянных гидов, находящихся в распоряжении ежедневно, равно S, устанавливаются следующим образом:

Г(S) = C1S, если 0 ≤ x ≤ S (дополнительных гидов не нужно)

Г(S) = C1S + C2(x - S), если 0 < x - S ≤ y (нужны дополнительные гиды, но нет необслуженных экскурсий)

Г(S) = C1S + C2y + C3(x – S – y), если y < x – S (нужны дополнительные гиды и имеются необслуженные экскурсии.)

Таким образом, множество всех значений X и Y можно разбить на три области (рис. 12.3), где все возможные значения изображены точками. Чтобы получить среднее значение или математическое ожидание Г(S), которое мы обозначим через , нужно вычислить издержки для каждой из точек,

умножить эти издержки на соответствующую вероятность

p(x) ∙ q1(y) или p(х) ∙ q2(y)

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

Например, издержки, соответствующие точке х = 12, y = 4, при S = 10 (см. рис. 12.3) равны

,

где вероятность точки (х, у)

р (12)∙ q1(4) = 0,10 ∙ 0,22 = 0,022,

а произведение равно

0,022(10С1 + 2С2).

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

Рис. 12.3

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

. (1)

Это выражение имеет место для буднего дня; для воскресений мы получаем величину , заменяя в (1) q1(y) на q2(y).

Поясним эту формулу для читателя, недостаточно искушенного в математике. С1S — это затраты, соответствующие S постоянным гидам, производящиеся с вероятностью 1. Выражение

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

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

Средние еженедельные затраты равны окончательно

.

Для некоторых читателей вычисление по формуле типа (1) заслуживает отдельного показа; предположим, что

S = 12, С1 = 52, С2 = 70, С3 = 400

и, кроме того, 1 ≤ y ≤ 7, x ≤ 16. Мы имеем

Вычислим

учитывая, что p(х) для х > 16 равно нулю.

Мы имеем:

1 ∙ p(13) ∙ q1(1) + [1 ∙ p(13) + 2 ∙ p(14)] + q1(2) +

+ [1 ∙ p(13) + 2 ∙ p(14) + 3p(15)] ∙ q1(3) +

+ [1 ∙ p(13) + 2 ∙ p(14) + 3p(15) + 4 ∙ p(16)] ´

´ [q1(4) + q1(5) + q1(6) + q1(7)] =

= 1 ∙ 0,10 ∙ 0,09 +

+ [1 ∙ 0,10 + 2 ∙ 0,08] ∙ 0,15 +

+ [1 ∙ 0,10 + 2 ∙ 0,08 + 3 ∙ 0,06] ∙ 0,20 +

+ [1 ∙ 0,10 + 2 ∙ 0,08 + 3 ∙ 0,06 + 4 ∙ 0,02] ´

´[0,22 + 0,14 + 0,10 + 0,07] = 0,4116.

Переходим к вычислению суммы:

= 1 ∙ q1(1) ∙ p(14)+

+ [1 ∙ q1(1) + 2 ∙ q1(2)] ∙ p(15) +

+ [1 ∙ q1(1) + 2 ∙ q1(2) + 3 ∙ q1(3)] ∙ p(16) =

= 1 ∙ 0,0 9 ∙ 0,08 + [1 ∙ 0,09 + 2 ∙ 0,15] ∙ 0,06 +

+ [1 ∙ 0,09 + 2 ∙ 0,15 + 3 ∙ 0,20] ∙ 0,02 = 0,0504.

Наконец

= 1 ∙ p(13)q1(0) + 2 ∙ p(14) ∙ [q1(0) + q1(1)] +

+ 3 ∙ p(15) ∙ [q1(0) + q1(1) + q1(2)] +

+ 4 ∙ p(16) ∙ [q1(0) + q1(1) + q1(2) + q1(3)] =

= 1 ∙ 0,10 ∙ 0,03 + 2 ∙ 0,08 ∙ 0,12 + 3 ∙ 0,06 ∙ 0,27 +

+ 4 ∙ 0,02 ∙ 0,47 = 0,1084.

Таким образом,

= 624 + 70 ·0,4116 — 330 · 0,0504 + 400 ·0,1084 = 679,540.

Такое же вычисление, проведенное при замене q1(y) на q2(y), дает

= 784,512 песо,

и, следовательно.

=4861,752 песо.

Чтобы найти оптимальное значение , вычислим эту величину для

S = 8, 9, 10, ..., 14, 15;

окажется, что минимум достигается при S=12. Однако, как мы видим, вычисления, к которым приводит аналитический метод, довольно значительны.

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

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

а) постоянных гидов достаточно для удовлетворения спроса; вероятность этого равна 1 — P(S+1),где

P(S+1) = ;

6) постоянных гидов не хватает, но имеется достаточное число предложений дополнительных гидов:

вероятность =

где

(u — число требующихся дополнительных гидов);

в) постоянных гидов не хватает и число имеющихся в распоряжении дополнительных гидов недостаточно, откуда имеем убыток от нехватки по крайней мере одного гида-переводчика:

вероятность =

Если теперь увеличить на единицу число постоянных гидов, которых станет теперь S + 1, изменение затрат будет равно:

1)  + C1 в любой ситуации;

2)  - С2 в том и только в том случае, если имеет место ситуация б); действительно имеется необходимость по крайней мере в одном дополнительном гиде;

3)  - С3 в том и только в том случае, если имеет место ситуация в); действительно, если общее число постоянных и дополнительных гидов увеличивается на единицу, убыток от несостоявшихся экскурсий уменьшается на 1.

Среднее изменение затрат тогда будет равно

Чтобы найти оптимум, заметим, что

1) P(S+1)

является убывающей функцией S;

2)

является функцией, вариация которой зависит от вида p(х) и q1(y). Отсюда следует, что не обязательно выпукла[62].

S	7	8	9	10
P(S+1)	0,82	0,72	0,60	0,48
	0,4074	0,4114	0,3844	0,3418
	-141,5	-100,2	-61	-27,2

S	11	12	13	14	15	16
P(S+1)	0,36	0,26	0,16	0,08	0,02	0
	0,2778	0,2218	0,1500	…	…	…
	-0,4	+21,1	+37,5	…	…	…

Для S = 11, < 0, следовательно < .

Для S = 12, >0, следовательно < .

Тогда оптимум равен S = 12 для будних дней.

Для воскресных дней аналогичное вычисление дает

= - 32,2; = - 0,5; = 24,7;

так что оптимум достигается при S = 13.

Можно также вычислить

;

получается, что

= 6 ∙ (- 0,4) + (- 32,2) = - 34,6,

= 6 ∙ 21,1 + (- 0,5) = 126,1,

= 6 ∙ 37,5 + 24,7 = 249,7;

отсюда следует, что с учетом воскресений оптимум действительно имеет место для S =12.

Как легко видеть, метод маргинального анализа хотя и является более простым, но все же приводит к достаточно громоздким вычислениям.

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

И теперь, если вы отправитесь в Мексику, посетите величественные памятники Теотиуакана — эти обломки блестящей древней цивилизации. Но не ищите там автобусов компании «Три звездочки»: ведь эта организация является плодом чистейшего вымысла. К счастью, существующие туристические компании носят не менее очаровательные названия!

Глава 13. Триумф Дени-Папена (Введение в линейное программирование)

Триумф энергии — это скорее всего триумф атома; триумф путешествий — это, быть может, триумф ракеты; для автомобильного движения — это, вероятнее всего, триумф сапожника. Но бесспорный триумф — это триумф Дени-Папена перед французскими домашними хозяйками. В самом деле, котел и кофеварка стали необходимыми в каждом доме, ибо каждая семья вечно спешит. Несмотря на упреки доктора Эдуарда де Помиана, этого короля научной кухни, мы отмечаем популярность знаменитых котлов[63].

Общество «Дени-Папен[64], сыновья, внуки и К°» производит автоклавные кухни А и автоматические кофеварки В. Для обоих видов продукции основные производственные операции (штамповка, отделка и сборка), к несчастью, являются объектами ограничений. Так, на ближайшую неделю производственные возможности для того или для другого вида продукции устанавливаются следующим образом:

Производительность (в штуках)

	Кухни A	Кофеварки B
Штамповка…..	25 000	35 000
Отделка………	33 333	16 667
Сборка A…….	22 500	—
Сборка B…….	—	15 000

Спрос практически неограничен; книги заказов полны (мы сказали бы даже переполнены). Прибыль[65], получаемая от одной кухни, составляет 15 франков, а от одного кофейника — 12,5 франка. Пусть х1 и х2 соответственно — количества кухонь и кофеварок, которые должны быть произведены на следующей неделе.

Доли[66] общих производственных мощностей, используемых для производства единицы продукции каждого вида, следующие:

	Кухни A	Кофеварки B
Штамповка…	0,004	0,00286
Отделка…….	0,003	0,006
Сборка A……	0,00444	0
Сборка B……	0	0,00667

Их легко найти согласно таблице производственных мощностей.

В каком количестве должны производиться кухни и кофеварки при этих условиях, чтобы суммарная прибыль была максимальной?

Уравнения, которые представляют ограничения по производительности, легко записываются:

Штамповка	0,004x1+0,00286x2£100
Отделка	0,003x1 + 0,006x2£100
Сборка A	0,00444x1£100
Сборка B	0,00667x2£100

Нужно, таким образом, удовлетворить этим соотношениям[67] и максимизировать функцию прибыли

F = 15x1 + 12,5x2.

Как решить эту маленькую производственную задачу?

На графике (рис. 13.1) с прямоугольными координатами начертим прямые:

0,004x1+0,00286x2 =100	(1),
0,003x1 + 0,006x2 =100	(2),
0,00444x1 =100	(3),
0,00667x2 =100	(4).

Очевидно, что значения переменных должны находиться всегда под прямыми (1), (2) и (4) и слева от прямой (3); с другой стороны, эти переменные не могут быть отрицательными — это было бы бессмысленным с экономической точки зрения. Таким образом, каждая точка, представляющая решение поставленной задачи, должна находиться внутри незаштрихованной области или на ее границе.

Рис. 13.1.Ограничения, изображенные на координатной плоскости (оси проградуированы в тысячах единиц).

Рассмотрим теперь семейство прямых

F = 15x1 + 12,5x2.

Хорошо известно (элементарный факт аналитической геометрии), что F пропорционально расстоянию d прямой от начала координат. Перемещаем прямую F параллельно самой себе (рис. 13.1) до крайней точки P, являющейся последней общей точкой прямой и области OMNPQR; именно этой точке соответствуют величины x1 и х2, дающие максимум F. Итак, максимум F, равный ,5 франка, достигается при x1 =и x2 = 6 481.

Эти значения x1 и х2 соответствуют пересечению прямых, относящихся к штамповке и отделке, причем предельные мощности сборки A и B не достигаются. Мы имеем:

0,004 ∙ 20370 + 0,00286 ∙ 6481 = 100 (насыщение),

0,003 · 20370 + 0,006·6481 = 100 (насыщение),

0,00444 · 20370 = 90,45 (ненасыщение),

0,00667 ∙ 6481 =43,23 (ненасыщение).

Итак, произведя на следующей неделекухонь и 6481 кофеварку, общество получит максимальную прибыль; производительности по штамповке и отделке будут исчерпаны, тогда как производительности по сборке таковыми не будут. Использование производительности по сборке кофеварок будет значительно ниже 100%: таким образом, разумно сократить, если это возможно, производительность по сборке кофеварок, результатом чего будет снижение себестоимости производства и, следовательно, увеличение прибыли. Из рис. 13.1 ясно, что пока прямая F имеет больший наклон, чем прямая, относящаяся к отделке (наклон прямой F может изменяться с изменением прибыли на единицу каждого из изделий), можно существенно сокращать производительность по сборке кофеварок до тех пор, пока она не достигнет 6 481 вместоСледовательно, исходя из рис. 13.1, может быть предпринята интересная с экономической точки зрения дискуссия; читатель не преминет ее себе вообразить.

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

Возможные производственные мощности для каждого рассмотренного товара составляют теперь в среднем:

Производственные мощности (в штуках)

	Кухни	Кофеварки	Самовары
Штамповка………	20 000	30 000	12 000
Отделка………….	30 000	10 000	10 000
Сборка кухонь…..	20 000	-	-
Сборка кофеварок	-	12 000	-
Сборка самоваров	-	-	8 000

Итак, соответствующие еженедельные объемы производства x1, x2, x3 должны удовлетворять следующим неравенствам: