Чейз, Ричард, Б., Эквилайн, Николас, Дж., Якобе, Роберт, Ф. Производственный и операционный менеджмент

Подождите немного. Документ загружается.

Дополнение

главе

Линейное

программирование

261

нием

различных стратегий поиска, отличных от сим-

плексного метода.

После введения информации в это диалоговое окно

можно нажать кнопку

Solve

(Выполнить) и решить

задачу.

При

этом мы получим несколько разных отчетов. Наиболее

интересными отчетами для нашей задачи являются

Answer

Report (Отчет по результатам) и

Sensitivity

Report (Отчет по

устойчивости), примеры которых приведены на рис. 7д.4.

Answer

Report (Отчет по результатам) включает оконча-

тельные ответы по общей прибыли (64 долл.) и по количе-

ствам производимой продукции (24 хоккейные клюшки и 4

шахматных набора). В разделе Constraints (Ограничения)

этого отчета отображено состояние каждого ресурса, из ко-

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

будут

загружены все станки

участков А и В, а станки участка С простоят 6 часов.

Sensitivity

Report (Отчет по устойчивости) делится на две

части. Первая часть озаглавлена "Изменяемые ячейки" и

соответствует коэффициентам целевой функции. При-

быль на единицу продукции для клюшек может увели-

читься либо уменьшиться на 0,67 долл. (т.е. может нахо-

диться

между

2,67 и 1,33 долл.), не оказывая при этом

влияния

на решение. Точно так же прибыль на единицу

шахматных наборов может быть

между

6 и 3 долл., и ре-

Отчет

по

результатам

Целевая

ячейка

(максимум)

шение при этом также не изменится. В

случае

с участком

ограничение увеличится до 144 (120 + 24) или умень-

шится до 84 единиц, что даст в результате повышение ли-

бо снижение целевой функции на 0,33 долл. соответст-

венно.

Ограничение для участка В увеличится до 90 еди-

ниц

или уменьшится до 60 с тем же изменением целевой

функции

в 0,33 долл.

Что касается участка С, то ограничение может увели-

чиваться до бесконечности (IE+ 30 — это на рис. 7д.4

мудреная запись очень большого числа, принятая в Excel)

или

уменьшиться на 4 единицы, не изменяя при этом це-

левую

функцию.

Транспортный

метод

Транспортный метод (Transportation Method) представ-

ляет собой упрощенный специфический вариант сим-

плексного метода. Он получил такое название потому, что

широко

применяется для решения задач, связанных с

транспортировкой продукции из разных источников в не-

сколько пунктов назначения. Задачи такого типа обычно

преследуют одну из

двух

возможных целей: минимизация

Ячейка

Имя

Исходно

SDS5

Общая

прибыль

$64

Изменяемые ячейки

Ячейка

Имя

Исходно

$В$4

Решение по хоккейным клюшкам

SCS4

Решение по шахматным наборам

Результат

$64

Результат

Ограничения

Ячейка

Имя

Значение

5DS9

SD$10

$D$11

$В$4

$CS4

Использование участка А

Использование участка В

Использование участка С

Решение по хоккейным клюшкам

Решение по шахматным наборам

120

Формула

$DS9<=$F$9

$DS10<=$F$10

$D$1K=$F$11

SB$4>=0

$C$4>=0

Статус

Binding

Not Binding

Разница

Отчет по устойчивости

Изменяемые

ячейки

Ячейка

Имя

Результат

Сокращение

Целевой

издержек коэффициент

$В$4

Решение по хоккейным клюшкам

24 0

$С$4

Решение по шахматным наборам

Ограничения

Ячейка

Имя

Результат

$D$9 Использование участка А

120

$D$10 Использование участка В

$D$11 Использование участка С

Теневая

цена

0.333333333

Правая

сторона

ограничения

120

Допустимое

повышение

0.666666667

Допустимое

повышение

1Е+30

Допустимое

понижение

0.666666667

Допустимое

понижение

Рис. 7д,4.

Отчеты

Microsoft

Excel

Solver

262

Часть

III. Проектирование производственных мощностей и трудового процесса

затрат по доставке я-го количества единиц продукции в

ш-е число пунктов назначения и максимизация прибыли

от транспортировки /z-ro количества единиц продукции в

т пунктов назначения. Решение транспортных задач, как

правило, выполняется в три стадии, которые мы обсудим

на

простом примере.

Предположим, компания

Риск

and

Pawn

владеет

че-

тырьмя фабриками, продукция с которых поступает на

четыре склада, и управленческий персонал

хочет

соста-

вить график доставки шахматных наборов с минималь-

ными

затратами на основе показателей ежемесячного

объема выпускаемой продукции. Объем поставок фабрик,

потребности складов и издержки по транспортировке ка-

ждой упаковки шахмат отображены в табл.

7д.1О.

Стадия

Построение транспортной

матрицы

Транспортная матрица для нашего примера изображе-

на

на рис. 7д.5.

В крайнем правом столбце отображаются объемы по-

ставок каждой фабрики, а в нижней строке — потребно-

сти каждого склада. Затраты на транспортировку единицы

продукции указаны в маленьких прямоугольниках в каж-

дой ячейке. На этом этапе важно убедиться, что общие

объемы поставок совпадают с общими потребностями. В

нашем примере оба этих показателя равны 46 единицам,

однако нередки ситуации, когда один из них превышает

другой. В таких

случаях

для того, чтобы применить

транспортный метод, в

задачу

включают фиктивный склад

или

фабрику. Эта процедура заключается во вставке до-

полнительной строки (для добавления фабрики) или еще

одного столбца (для добавления склада). Объем поставок

или

потребности дополнительного фиктивного склада или

фабрики

— это разница

между

суммарными показателями

строк и столбцов.

Так,

например, изменим условия рассматриваемой на-

ми

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

размере 36 единиц. В этом

случае

нам придется добавить

таблицу новый столбец, в котором указывается потреб-

ность фиктивного склада в размере 10 единиц, что в ре-

зультате

даст

необходимые 46 наборов. Показатели затрат

каждой ячейке фиктивной строки

будут

в этом

случае

нулевыми, т.е. отправленные

сюда

единицы не

дают

ни-

каких издержек на транспортировку. Теоретически данная

корректировка является эквивалентом симплексной про-

цедуры вставки в неравенства ограничений свободной пе-

ременной с тем, чтобы преобразовать его в уравнение, и,

так же как при симплексном методе, затраты фиктивного

подразделения представляются в целевой функции с ну-

левым значением.

Данную

задачу

также можно решить с помощью ком-

пьютерной программы Microsoft

Excel.

На рис. 7д.6 пока-

зано,

как нужно поставить

задачу

в MS

Excel.

Строки 1—6

используются для указания затрат, поставок фабрик и по-

требностей складов. Решение (Changing

cells,

Изменяемые

ячейки)

выводится в диапазоне ячеек В8—Е11. Затраты

вычисляются в строках

15—19.

Общие затраты указаны в

ячейке F19. В следующем разделе мы продолжим описа-

ние

способа решения данной задачи без применения

компьютерной техники.

Стадия II. Исходное распределение

Исходное распределение осуществляется размещением

данных по ячейкам матрицы в соответствии с ограниче-

ниями

на поставки и потребности в продукции. Мы

обсу-

дим несколько методов выполнения этой операции: метод

северо-западной ячейки, метод наименьших затрат и ме-

тод приближений Фогеля.

Из

^-^^

Потребности

складов

j^w,*

| 40

USL

-^•tj

} 30

•г !-»-

140

тГ*

•

| 60

| 38

Ц5_

| 27

Поставки

фабрики

^"--—^^

Рис. 7д.5.

Транспортная

матрица

для

задачи

транспортировки

шахмат-

ных

наборов

Таблица

7д.1О.

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

наборов

Затраты

на

транспортировку

единицы

продукции (в долл.)

Фабрика

Объем

поставок

Склад

Потребность

С фабрики На склад

На склад

Дополнение к главе

Линейное программирование 263

ia^ajaj^y

&j&в<*'«•

с•

a.^[i.»»ii.iuLe^|,]rrf,>ia

yfii~l-l"ii

^УЕ

И» j

it % , у; йI g g

-•

-~s>

д":

1 "

ТГ

Fromn'o

D "Г™

Destination

Requirements

Cost

~ t~"

A i

Total

Cost

I* I

HfiTraiSpof

tafionPr

SUm/

"eo

1(1

25П

.35

-S

№

'VA

•=

~ 2?

(

.'4-?

F»ct«rv

Supply

—^

;

=-.,—--—.

I.,

- ——-,

JXTTT

Get

Tstgj;

Cell:

ЩЕЭИЗ

EqjalTcr

Рис. 7д.6.

Решение

транспортной

задачи

помощью

программы

Excel

Распределение методом северо-западной

ячейки

Метод северо-западной ячейки, как

следует

из его на-

звания,

состоит в том, что распределение начинается с

верхнего левого

угла

матрицы и в ячейках первой строки

указываются как можно большие значения

. Затем данная

процедура повторяется для второй, третьей строки и т.д.,

пока

все потребности не

будут

распределены по строкам и

столбцам. На рис. 7д.7 показан пример такого распреде-

ления.

(Первой заполняется ячейка с координатами А-Е,

второй — A-F, третьей — B-F и т.д.)

Анализируя распределение потребностей на рис. 7д.7,

можно

увидеть, что при использовании этого метода не-

которые ячейки с высокими издержками оказываются за-

полненными,

другие

ячейки с низкими затратами оста-

ются пустыми. Этого и следовало ожидать, поскольку

данный

метод не учитывает издержки транспортировки, в

результате чего и упрощается алгоритм распределения.

В каждой ячейке указывается наибольшее возможное количе-

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

т +

заполненных ячеек, где т

—

количество строк, аи-

количество столбцов.

Распределение методом

наименьших

затрат

В соответствии с данным методом как можно большее

значение

проставляется в ячейке с наименьшими затрата-

ми.

Связи при этом

могут

нарушаться произвольно Строки

столбцы, распределенные полностью, во внимание не

принимаются,

и процесс распределения продолжается За-

канчивается

данная процедура после того, как все потреб-

ности

будут

распределены по строкам и столбцам Распре-

деление по данному методу иллюстрируется на рис 7д 8

(Первыми

указываются значения в ячейке с координатами

А~Е, затем в C-G, далее в D-H, в В-Ги т.д.)

Распределение методом

приближений

Фогеля

Метод приближений Фогеля

(Vogel's

Approximation

Method

— VAM) также основан на распредепении по-

требностей с учетом затрат на транспортировку Процесс

распределения осуществляется в пять следующих этапов

Этап 1. В каждой строке и в каждом столбце, включая

фиктивные,

определите разницу

между

двумя наимень-

шими

значениями затрат на транспортировку в ячейках

каждой строю! и каждого столбца.

Этап 2. Определите столбец или строку с наибольшей

разницей.

264

Часть

III. Проектирование производственных мощностей и трудового процесса

Этап 3. Вставьте наибольшее возможное значение еди-

ниц

в ячейке с наименьшими затратами в строке или

столбце с самой большой разницей, выбранной на этапе 2.

Этап 4. Прекратите процесс, если удовлетворены все

потребности строк и столбцов. В противном

случае

пере-

ходите

к следующему этапу.

Этап 5. Пересчитайте разницу

между

оставшимися не-

заполненными

двумя ячейками с наименьшими затратами

каждой строке и в каждом столбце. При вычислении

дальнейшей разницы не

следует

учитывать строки и

столбцы с нулевыми показателями потребности или по-

ставок. Вернитесь к этапу 2.

Метод приближений Фогеля обычно позволяет полу-

чить оптимальное или близкое к оптимальному исходное

решение. Одно из исследований показало, что данный

метод

дает

оптимальное решение для 80% задач. (Наши

студенты

утверждают,

что остальные 20% — это как раз те

задачи, которые попадаются им на экзаменах.) На

рис.

7д.9 проиллюстрировано применение метода Фогеля

для решения рассматриваемой нами задачи. (Первыми

указаны значения в ячейке А-Е, затем в C-G, далее в D-H,

D-Fn т.д.)

Обратите внимание, что это исходное решение совпа-

дает

с оптимальным, которое получено в

результате

всех

возможных улучшений исходного размещения, выпол-

ненного методом верхней левой ячейки (сравните дальше

с рис. 7д.12).

Стадия

III. Получение оптимального решения

ПОИСК

оптимального решения в транспортной задаче

заключается в оценке каждой неиспользованной ячейки и

определении, не

будет

ли перемещение в нее выгодным с

точки зрения уменьшения общих затрат. Если это так,

перемещение выполняется и процесс повторяется. Задача

считается решенной после того, как все ячейки оценены

проведены все соответствующие перемещения.

Метод

последовательных шагов

ОДНИМ

ИЗ распространенных методов оценки ячеек

является метод последовательных шагов, или метод

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

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

сравнивались с водой, а заполненные — с камнями, по

аналогии с переходом через ручей с камня на камень. Мы

применим

этот метод к поиску решения для исходного

размещения, выполненного методом северо-западной

ячейки

и приведенного для нашей задачи на рис. 7д.8.

Этап

1. Выберите

любую

пустую

ячейку и укажите

замкнутый путь, ведущий к ней. Этот путь состоит из гори-

зонтальных и вертикальных линий, которые

ведут

от пус-

Потребности складов

Ц5_

| 40

LiL

Поставки фабрики

Общие

затраты

10($25)

5($35)

6($30)

+1($50)

13(Й6)

2($66)

9($27)

$1,368

Рис.

7d. 7.

Распределение

методом

северо-западной

ячейки

Потребности складов

| 25

| 55

|_М_

L«L

| 40

|66

lid

Поставки фабрики

^^--^^

Общие

затраты

10($25)

14($26)

9(527)

6($30)

5($35)

1($40)

+1($66)

$1,318

Рис. 7д.8.

Распределение

методом

наименьших

затрат

Дополнение к

главе

7. Линейное программирование

265

Из

""--—^

Потребности

складов

| 25

\ 55

[

I 60

| 35

и?_

| 40

| 36

| 26

| 66

| 60

за

Поставки

фабрики

Разница

Итерации

РФ

Итеоаиии

Total

cost

10($25)

14($26)

9($27)

2{$40)

1($36)

4($35)

6($30)

$1,293

Рис. 7д.9.

Распределение

методом

приближений

Фогеля

той ячейки через

другие

обратно к ней же

. В замкнутом

пути может быть только одна пустая ячейка, которую мы и

рассматриваем. Повороты пути на 90°

могут

производиться

только в ближайших (к пустой) заполненных ячейках. На

рис.

7д.1О показаны два замкнутых пути. Замкнутый путь а

необходим для оценки пустой ячейки В-Е; замкнутый путь

нужен для оценки пустой ячейки А-Н.

Этап

2. Переместите одну единицу из заполненной

ячейки

угле

замкнутого пути в

пустую

ячейку и измени-

те оставшиеся заполненные ячейки в

других

углах

в соот-

ветствии с выполненным перемещением

. Изменение за-

ключается в добавлении и вычитании единиц из запол-

ненных ячеек способом, при котором не нарушаются

указанные общие ограничения в отношении поставок и

потребностей. Для этого необходимо, чтобы из каждой

строки или столбца, в ячейки которых была добавлена

или

вычтена единица, обязательно вычиталась или добав-

лялась одна единица, но из

других

ячеек, лежащих на пу-

ти.

Таким образом, для пути а потребуются следующие

добавления и вычитания.

Прибавьте одну единицу в ячейке В-Е (пустая ячейка).

Вычтите одну единицу из ячейки B-F.

Прибавьте одну единицу в ячейке A-F.

Вычтите одну единицу из ячейки А-Е.

Для более длинного пути

потребуется следующее.

Прибавьте одну единицу в ячейке А-Н (пустая ячейка).

Если распределение было сделано правильно, в матрице со-

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

Для проверки возможности перемещения можно добавить не

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

ми

задача носит линейный характер, если возможно смещение

на

одну единицу, то

будет

возможным смещение и на большее

число единиц, и наоборот.

Вычтите одну единицу из ячейки D-H.

Прибавьте одну единицу в ячейке D-G.

Вычтите одну единицу из ячейки C-G.

Прибавьте одну единицу в ячейке C-F.

Вычтите одну единицу из ячейки A-F.

Этап

3. Определите, желательно ли данное перемеще-

ние.

Это легко выполняется с помощью

• суммирования значений затрат в ячейке, к которой

была добавлена единица;

• суммирования значений затрат в ячейке, из которой

была вычтена единица;

• получения разницы

между

этими двумя суммами,

благодаря чему можно определить, сократились ли

как-нибудь затраты.

Если затраты в результате перемещений сократились,

следует

переместить как можно больше единиц из оце-

ненной

заполненной ячейки в пустую. Если же затраты

повысились, никаких перемещений делать не стоит, а

пустую

ячейку надо перечеркнуть или пометить каким-

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

вали. (Обычно для обозначения ячейки, которая прошла

оценку в

ходе

решения задач минимизации затрат и была

признана

нежелательной для перемещения, пользуются

большим знаком "плюс". В этих же случаях при решении

задач максимизации прибыли используют большой знак

"минус".) Для ячейки В-Е такие плюсы и минусы

будут

расположены следующим образом:

$55 (В-Е) $30

(B-F)

(A-F)

$90

$55

266

Часть

III. Проектирование производственных мощностей

трудового процесса

Для ячейки A-F эти знаки

будут

расставлены так:

$60

(А-Н)

(D-G)

(C-F)

$176

$27

(D-H)

(C-G)

(A-F)

Таким

образом, в обоих случаях очевидно, что пере-

мещений в

любую

пустую

ячейку делать не

следует,

так

как

получаемые разности положительны.

Этап

4. Повторяйте этапы 1-3 до тех пор, пока не бу-

дут оценены все пустые ячейки. Чтобы проиллюстриро-

вать технику выполнения перемещения, рассмотрите

ячейку D-F и короткий замкнутый путь, ведущий к ней:

C-F,

C-GVL

D-G. Плюсы и минусы в данном

случае

будут

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

$40

(D-F) $50

(C-F)

26 (C-G) 66

(D-G)

$66

$116

Поскольку в данном

случае

вы имеем экономию в

размере 50 долл. при доставке по пути D-F, в эту ячейку

следует

переместить как можно больше единиц. При

этом,

однако, в данном конкретном

случае

максимально

можно переместить только одну единицу, поскольку мак-

симальное количество единиц, которое можно добавить к

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

ячейке с наименьшим значением, из которого

будет

про-

водиться вычитание. Невыполнение этого правила приве-

дет к нарушению ограничений относительно поставок и

потребностей задачи. В нашем

случае

очевидно, что огра-

ничивающей ячейкой является C-F, поскольку она содер-

жит всего одну единицу.

Измененная

матрица, отображающая эффект данного

перемещения и описанных выше оценок, изображена на

рис.

7д.11.

результате

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

шагов к остальным незаполненным ячейкам и выполне-

ния

указанных перемещений мы приходим к оптималь-

ному решению.

В частности, незаполненная ячейка A-G на рис. 7д.П

имеет замкнутый путь D-G, D-F и A-F. Плюсы и минусы

будут

расставлены так:

$36

(A-G)

$35

(A-F)

40 (D-F)

66 (D-G)

$76

$101

Поскольку имеется экономия, равная 101 — 76 = 25

долл., мы перемещаем одну единицу в ячейку A-G. На

рис.

7д.12 изображена оптимальная матрица для мини-

мальных транспортных затрат в размере 1293 долл.

Чтобы удостовериться, что полученное распределение

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

следует

оценить каждую

пустую

ячейку и рассмотреть, желатель-

Потребности складов

1 25

10 „а..

,1*0

•UL

„_

I 30

Ж.

[26

{13

ии

[65

Поставки фабрики

Рис.

7д.

10.

Метод

последовательных

шагов

—

определение

замкнутого

пути

Потребности складов

| 40

[36

[

1 66

[60

I 65

Поставки фабрики

Общие затраты =

10($25)

5($35)

6($30)

+14($26) +

1($40)

+1($66) +

9($27)

= $1,318

Рис.

7д.П.

Измененная

транспортная матрица

Дополнение к

главе

7. Линейное программирование

267

Потребности

складов

| 40

| 60

5-1=4

[

. 6

Ц0_

1+1=2

L36.

0+1=1

[45_

| 66

1-1=0

| 38

I 65

| 27

Поставки

фабрики

Общие

затраты

10($25)

4($35)

+1($36)

6($30)

+14($26)

2($40)

9(827)

$1,293

Рис.

7д. 12.

Оптимальное

решение

транспортной

задачи

Потребности

складов

' ,3- .с

LL.

LJL

Поставки

фабрики

+ n -1 = 5

заполненных

ячеек

Фактическое

распределение

—

заполненные

ячейки

Рис.

7д. 13.

Транспортная

задача

явлением

вырождения

но

ли перемещение в нее. Если в каждой из проверенных

ячеек окажется знак "плюс", то задача решена и распре-

деление оптимально.

Явление вырождения (Degeneracy) возникает в транс-

портных

задачах,

когда количество заполненных ячеек

меньше суммы количества строк и столбцов минус 1 (т.е.

т + п

—

1). Вырождение может наблюдаться во время ис-

ходного распределения, когда первое значение в строке или

столбце

удовлетворяет

ограничениям как по строке, так и

по столбцу. Для оценки полученного решения в матрице

необходимо определенным образом скорректировать выро-

ждение. Такая корректировка заключается во вставке неко-

торого количества единиц в в пустые ячейки так, чтобы

можно было составить замкнутый

путь

для оценки

других

пустых

ячеек. Значение в может быть бесконечно малым

числом и не оказывать влияния на решение. При этом

обычная процедура предусматривает, что некое значение О

используется точно так же, как реальное число, но может

быть размещено в

любую

пустую

ячейку без соблюдения

требований к ограничениям по строкам и столбцам.

Оптимальное по минимальным затратам на транспор-

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

ждения показано на рис. 7д.

13.

На этом рисунке видно,

что, если бы в матрицу не было включено значение 0, не-

которые из ячеек оценить было бы невозможно (включая

ту, к которой это значение было добавлено).

После того, как 0 вводится в решение, это значение

остается в нем до тех пор, пока либо оно не исчезнет при

вычитании, либо до получения окончательного решения.

Выбор ячейки, в которую

следует

вводить в, принима-

ется произвольно, но можно сэкономить немало времени,

если вставить это значение в ту ячейку, в которой его

можно использовать для оценки как можно большего ко-

личества ячеек, не перемещая его. Вы можете убедиться,

что на рис. 7д. 13 значение в расположено именно в таком

наиболее выгодном месте.

Альтернативные

оптимальные решения

ЕСЛИ

оценка пустой ячейки

дает

результате

то же зна-

чение затрат, что и имеющееся распределение, значит су-

ществует

равноценное альтернативное оптимальное реше-

ние

В таких

случаях

управленческий персонал приобрета-

ет дополнительную возможность составлять гибкий

окончательный график поставок продукции, используя два

равноценных оптимальных размещения. (Обычно

пустую

ячейку, определенную как альтернативный оптимальный

маршрут, помечают, например большой цифрой 0.)

Резюме

Данное дополнение было в основном посвящено раз-

личным процедурам решения задач линейного программи-

рования.

Задачи такого типа, решаемые без применения

вычислительной техники, встречаются крайне редко. Кроме

Учитывая, что все остальные ячейки распределены оптимально.

268

Часть

III. Проектирование производственных мощностей и трудового процесса

того, сегодня в нашем распоряжении столько компьютеров

компьютерных программ, что решение их "вручную" бы-

ло бы просто неоправданной тратой времени

Задачи

с решениями

Задача

ходе

производства два вида продукции X и У прохо-

дят обработку на станках I и II. У станка I есть 200 часов

доступного времени, а у станка II — 400. Для обработки

одной единицы продукции X необходим один час работы

на

станке I и четыре часа на станке II. Обработка продук-

ции

требует

одного часа на станке I и одного — на

станке II. Единица продукции Л

дает

прибыль в размере

10 долл., а единица продукции У— 5 долл. Все эти усло-

вия

выражаются следующими уравнениями:

Х+ У й 200 (станок I).

4Х+

Y<•

400 (станок II).

Максимизировать $10A"+

$5 Y.

Решите графическим методом задачу определения оп-

тимального использования машинного времени.

Решение

Оптимальная точка, как показано ниже на графике,

имеет координаты: ^=67,

У =

133.

Прибыль в этой точке составит

($10x67)+

($5x33)

= $1335.

Чтобы построить первую линию равной прибыли,

предположим:

@X=Q,Y=

100;

@Y=0,X=50.

100

300

400

Х-

Продолжая параллельно перемещать эту линию равной

прибыли дальше, до тех пор, пока она не достигнет наи-

более удаленной точки допустимой области, получим оп-

тимальное решение с приблизительными координатами:

*=67,

У= 133.

Существуют также программы, помогающие строить сами

мо-

дели линейного программирования. Самая известная

из них, по

всей вероятности, GAMS— General

Algebraic

Modeling System

(GAMS

—

General,

San Francisco, CA).

Задача

Решите задачу 1 с использованием симплексного метода.

Решение

Симплексное решение задачи 1:

$10

200

400

Первая

итерация

Вторая

итерация

3/4

1/4

2,50

4/3

-1/3

$ -3,33

-1/4

1/4

-2,50

-1/3

1/3

$-1,66

100

133

При

X— 67, a У= 133 значение целевой функции бу-

дет Z= ($10 х 67) + ($5 х 133) = $1335.

Вопросы

для контроля и обсуждения

1. Какие требования предъявляются к задаче, чтобы ре-

шать ее методами линейного программирования?

2. Какую дополнительную информацию можно получить

из

решения задачи симплексным методом?

3. Какая информация содержится в теневых ценах?

4. Что представляют собой свободные переменные? Поче-

му они необходимы при применении симплексного ме-

тода?

В каких случаях они используются при примене-

нии

транспортного метода?

5. В данном дополнении утверждается, что оптимальное

решение симплексной задачи всегда находится на гра-

фике

в угловой точке. При каком условии можно найти

равноценное оптимальное решение в другой точке?

6. Что представляет собой выпуклый многоугольник в гра-

фическом решении? Как выпуклость многоугольника

графического решения проявляется в симплексном ме-

тоде?

7. Как определить, не присутствует ли в транспортной за-

даче

явление вырождения? Что

следует

делать при необ-

ходимости протестировать на оптимальность решение

такой задачи?

Задачи

1. Решите графически

следующую

задачу:

14У* 84;

ЗХ+2Уй 18;

У*4.

Максимизируйте

2Х+ Y.

Дополнение

главе 7. Линейное программирование

269

2. Решите

следующую

задачу графическим методом ли-

нейного

программирования.

44 + 65

120;

24 + 6В

72;

В>10.

Минимизируйте

2А + 4В.

3. Компания

Bindley

заключила контракт на один год на

поставку моторов для всех видов стиральных машин,

выпускаемых компанией

Rinso

Ltd.

Rinso

Ltd производит

машины

на четырех заводах, расположенных в разных

концах

страны: в Нью-Йорке, в Форт-Уэрте, в Сан-

Диего и в Миннеаполисе со следующими объемами:

Нью-Йорк

— 50 000;

Форт-Уэрт — 70 000;

Сан

Диего — 60 000;

Миннеаполис

— 80 000.

Bindley

имеет три завода, выпускающие моторы, со сле-

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

Boulder-

100 000;

Масоп

— 100 000;

Со/у-150

000.

Вследствие варьирования производственных и транс-

портных издержек прибыль, которую получает

Bindley

от

каждых ста единиц продукции, зависит от того, в каком

именно

месте она были выпущена и от способа ее дос-

тавки.

В следующей таблице приведены данные, пре-

доставленные бухгалтерией компании, о прибыли на

единицу продукции (в долл.).

Произведено

Boulder

Macon

Gary

Доставка

продукции

Нью-

Йорк

Форт-

Уэрт

Сан-

Диего

Миннеаполис

Выбрав в качестве критерия максимум прибыли, ком-

пания

хотела

бы определить, сколько моторов необхо-

димо производить на каждом заводе и сколько моторов

следует

поставлять с каждого завода каждому из

трех

за-

водов-заказчиков.

a) Составьте транспортную матрицу для этой задачи.

b) Найдите оптимальное решение.

4. Решите

следующую

задачу с использованием графиче-

ского метода линейного программирования.

16^+ 10Г<; 160;

12^+ 14У£ 168;

К>2.

Максимизируйте 2*+ 10

5. Производственная компания прекратила выпуск став-

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

тате

чего освободились значительные производственные

мощности.

Управленческий персонал фирмы рассмат-

ривает возможность использования этих дополнитель-

ных мощностей для выпуска одного или

двух

из

трех

выпускаемых ею изделий: X

viX

Машинное

время в часах, необходимое для выпуска

единицы

каждого вида продукции, следующее:

Тип

станка

Фрезерные

станки

Токарные станки

Шлифовальные станки

Доступное время

Фрезерные

станки

Токарные станки

Шлифовальные станки

Продукция

неделю:

Количество

800

480

320

Хз

часов

неделю

По

предварительным оценкам торгового персонала,

компания

может продавать всю выпущенную продук-

цию

X, и Х

однако, что касается продукции Х

, макси-

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

80 единиц в неделю.

Прибыль

на единицу продукции по каждому виду изде-

лий

составляет:

Прибыль

на

единицу

продукции

Х1

Х2

ХЗ

$20

a) Составьте уравнения, решив которые, можно макси-

мизировать недельную прибыль.

b) Решите эти уравнения симплексным методом.

c) Каким

будет

оптимальное решение? Какое количество

каждого вида продукции

следует

выпускать фирме, и

какова

будет

полученная в

результате

прибыль?

d) Как данная ситуация отразится на работе каждой

группы станков?

Будут

ли они работать на полную

мощность

или

будет

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

машинное

время? Будет ли продукция Х

выпускать-

ся

в количестве, достаточном для обеспечения мак-

симальных объемов продаж?

e) Предположим, что вследствие сверхурочной эксплуа-

тации

фрезерных станков можно увеличить доступ-

ное

машинное время на 200 часов в неделю.

Реко-

мендовали бы вы это

сделать?

Объясните, что приве-

ло вас к такому выводу.

6. Rent'R

Cars

— это компания по аренде автомобилей,

имеющая несколько точек обслуживания по всему горо-

ду. Для повышения качества обслуживания фирма нача-

ла реализовывать новую политику "возврат машины по

адресу,

самому удобному для клиента". Однако это оз-

начает, что компании приходится постоянно переме-

щать машины по всему городу с тем, чтобы обеспечить

270

Часть

III.

Проектирование производственных мощностей

трудового процесса

необходимое количество транспорта. В приведенной

ниже

матрице содержатся данные относительно необхо-

димого количества и потребности в автомобилях

эконо-

мичного класса, а также общая стоимость на перемеще-

ние

этих машин из одной точки в

другую.

Известно

также следующее: топливо А имеет октановое

число 90 и стоит 1,20 долл. за галлон; топливо В имеет

октановое число 75 и стоит 0,90 долл. за галлон,

а) Составьте уравнения, отображающие эти исходные

данные.

Спрос

|$9

[

|$8

и_

Поставки

165

^^--^_^

a) Найдите решение, которое позволило бы минимизи-

ровать стоимость перемещения транспорта.

b) Что вам пришлось бы сделать, если частью опти-

мального решения станет обязательное перемещение

автомобилей из точки А в точку Ш

7. Для столовых общежитий Аризонского университета раз-

рабатывается новая диета. Основная цель заключается в

том, чтобы питание обходилось студентам как можно де-

шевле, но рацион должен содержать от 1800 до

3600

ка-

лорий.

При этом не более чем 1400 калорий должны быть

из

углеводов и не менее 400 из белков. Диета должна со-

стоять из

двух

продуктов: А и В. Продукт А стоит 0,75

долл. за фунт и содержит 600 калорий, 400 из которых

белки,

а 200 углеводы. Каждый

студент

должен потреб-

лять не больше

двух

фунтов продукта А. Продукт В стоит

0,15 долл. за фунт и содержит 900 калорий, из которых

700 углеводы, 100 — белки и 100 — жиры.

a) Составьте уравнения, которые отображали бы все

исходные данные.

b) Решите задачу графически для каждого вида продук-

тов, которые должны получать студенты.

8. Сформулируйте и решите задачу 7, добавив дополни-

тельное ограничение, которое заключается в том, что не

более чем 150 калорий должно поступать в организм из

жиров,

а цена при этом повышается до 1,75 долл. за

фунт продукта А и 2,50 долл. за фунт продукта В.

9. Компания

Logan

Manufacturing

хочет

смешать два вида

топлива (А и В) для своих грузовиков, чтобы минимизи-

ровать их стоимость. Для нормальной эксплуатации

машин

на протяжении следующего месяца компании

понадобится не менее чем

3000

галлонов топлива. Мак-

симальная

емкость для хранения топлива фирмы со-

ставляет

4000

галлонов. В наличии есть

2000

галлонов

топлива А и 400 галлонов топлива В. Смешанное топли-

во должно иметь октановое число не меньше 80.

При

смешивании топлива объем полученной смеси ра-

вен

сумме смешиваемых объемов. Октановое число

представляет собой среднее взвешенное отдельных ок-

тановых чисел, взятых в пропорциональном отношении

от соответствующих объемов.

Ь)

Решите задачу графически, учитывая объемы каж-

дого используемого вида топлива. Назовите все до-

пущения,

которые необходимо сделать для решения

данной

задачи.

10. Внимательно проанализируйте информацию в ниже-

приведенном

симплексном решении:

-3

-7

-2

-4

-2

-3

Ответьте на следующие вопросы.

a) Что представляют собой значения X, Y, Z, S,, S

и SP

b) Правильны ли ответы, приведенные ниже?

Стоит

ли

покупать

данную

продукцию?

Да

Стоит

ли

продавать

данную

продукцию?

Да

По

какой

цене?

По

какой

цене?

Сколько?

со

Сколько?

П.

Предположим, вы

хотите

составить

бюджет,

позволяю-

щий

оптимизировать некоторую часть вашего

дохода

после уплаты налогов. При этом вы можете выделить

максимум 1500 долл. в месяц на питание, жилье и раз-

влечения.

Общая сумма, выделенная на питание и жи-

лье, не должна превышать 700 долл., а на развлечения

вы можете позволить себе вьщелить не больше 300 долл.

месяц. Каждый доллар, потраченный на еду,

дает

удовлетворение, оцениваемое в 2 балла; один доллар,