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


Транспортный метод (Transportation Method) представляет собой упрощенный специфический вариант симплексного метода. Он получил такое название потому, что широко применяется для решения задач, связанных с транспортировкой продукции из разных источников в несколько пунктов назначения.
Задачи такого типа обычно преследуют одну из двух возможных целей: минимизация затрат по доставке n-го количества единиц продукции в m-е число пунктов назначения и максимизация прибыли от транспортировки n-ro количества единиц продукции в т пунктов назначения. Решение транспортных задач, как правило, выполняется в три стадии, которые мы обсудим на простом примере.

Отчет по результатам
Целевая ячейка (максимум)




Ячейка Имя

Исходно

Результат


$D$5 Общая прибыль

$64

$64


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




Ячейка Имя

Исходно

Результат


$В$4 Решение по хоккейным клюшкам 24

24


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

4






Ограничения

Ячейка Имя

Значение

Формула Статус Разница

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

120

$D$9lt;=$F$9 Binding

0

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

72

$D$10lt;=$F$10 Binding

0

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

4

$D$1K=$F$11 Not Binding

6

$В$4 Решение по хоккейным клюшкам 24

SB$4gt;=0 Not Binding

24

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

$C$4gt;=0 Not Binding

4

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




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




Ячейка Имя

Результат

Сокращение Целевой Допустимое Допустимое



издержек коэффициент повышение

понижение

$В$4 Решение по хоккейным клюшкам 24

0 2 0.666666667

0.666666667

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

0 4 2

1

Ограничения

Ячейка Имя

Результат

Теневая Правая сторона Допустимое Допустимое



цена ограничения повышение

понижение

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

120 0.333333333 120 24

36

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

72 0.333333333 72 18

12

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

4

0 10 1Е+30

6

Рис. 7д.4. Отчеты Microsoft Excel Solver

Предположим, компания Риск and Pawn владеет четырьмя фабриками, продукция с которых поступает на четыре склада, и управленческий персонал хочет составить график доставки шахматных наборов с минимальными затратами на основе показателей ежемесячного объема выпускаемой продукции. Объем поставок фабрик, потребности складов и издержки по транспортировке каждой упаковки шахмат отображены в табл.
7д.10.
Стадия I. Построение транспортной матрицы
Транспортная матрица для нашего примера изображена на рис. 7д.5.
В крайнем правом столбце отображаются объемы поставок каждой фабрики, а в нижней строке — потребности каждого склада. Затраты на транспортировку единицы продукции указаны в маленьких прямоугольниках в каждой ячейке. На этом этапе важно убедиться, что общие объемы поставок совпадают с общими потребностями. В нашем примере оба этих показателя равны 46 единицам, однако нередки ситуации, когда один из них превышает другой. В таких случаях для того, чтобы применить транспортный метод, в задачу включают фиктивный склад или фабрику. Эта процедура заключается во вставке дополнительной строки (для добавления фабрики) или еще одного столбца (для добавления склада). Объем поставок или потребности дополнительного фиктивного склада или фабрики — это разница между суммарными показателями строк и столбцов.
Так, например, изменим условия рассматриваемой нами задачи и укажем общую потребность в продукции в размере 36 единиц. В этом случае нам придется добавить в таблицу новый столбец, в котором указывается потребность фиктивного склада в размере 10 единиц, что в результате даст необходимые 46 наборов. Показатели затрат в каждой ячейке фиктивной строки будут в этом случае нулевыми, т.е. отправленные сюда единицы не дают никаких издержек на транспортировку. Теоретически данная корректировка является эквивалентом симплексной процедуры вставки в неравенства ограничений свободной переменной с тем, чтобы преобразовать его в уравнение, и, так же как при симплексном методе, затраты фиктивного подразделения представляются в целевой функции с нулевым значением.
Данную задачу также можно решить с помощью компьютерной программы Microsoft Excel. На рис. 7д.6 показано, как нужно поставить задачу в MS Excel. Строки 1—6 используются для указания затрат, поставок фабрик и потребностей складов. Решение (Changing cells, Изменяемые ячейки) выводится в диапазоне ячеек В8—Е11. Затраты вычисляются в строках 15—19. Общие затраты указаны в ячейке F19. В следующем разделе мы продолжим описание способа решения данной задачи без применения компьютерной техники.
Стадия II. Исходное распределение
Исходное распределение осуществляется размещением данных по ячейкам матрицы в соответствии с ограничениями на поставки и потребности в продукции. Мы обсудим несколько методов выполнения этой операции: метод северо-западной ячейки, метод наименьших затрат и метод приближений Фогеля.

Рис. 7д.5. Транспортная матрица для задачи транспортировки шахматных наборов


Таблица 7д.10. Данные для задачи транспортировки шахматных наборов

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

Фабрика

Объем
поставок

Склад

Потребность

С фабрики

На склад Е

На склад F

На склад G

На склад Н

А

15

E

10

А

25

35

36

60

В

6

F"

12

В

55

30

45

38

С

14

G

15

С

40

50

26

65

D

11

Н

9

D

60

40

66

27





Рис. 7д. 6. Решение транспортной задачи с помощью программы MS Excel


Распределение методом северо-западной ячейки
Метод северо-западной ячейки, как следует из его названия, состоит в том, что распределение начинается с верхнего левого угла матрицы и в ячейках первой строки указываются как можно большие значения[23]. Затем данная процедура повторяется для второй, третьей строки и т.д., пока все потребности не будут распределены по строкам и столбцам. На рис. 7д.7 показан пример такого распределения. (Первой заполняется ячейка с координатами А-Е, второй — A-F, третьей — B-F и т.д.)
Анализируя распределение потребностей на рис. 7д.7, можно увидеть, что при использовании этого метода некоторые ячейки с высокими издержками оказываются заполненными, а другие ячейки с низкими затратами остаются пустыми. Этого и следовало ожидать, поскольку данный метод не учитывает издержки транспортировки, в результате чего и упрощается алгоритм распределения.
Распределение методом наименьших затрат
В соответствии с данным методом как можно большее значение проставляется в ячейке с наименьшими затратами. Связи при этом могут нарушаться произвольно. Строки и столбцы, распределенные полностью, во внимание не принимаются, и процесс распределения продолжается. Заканчивается данная процедура после того, как все потребности будут распределены по строкам и столбцам. Распределение по данному методу иллюстрируется на рис. 7д.8. (Первыми указываются значения в ячейке с координатами А-Е, затем в C-G, далее в D-H, в В-F и т.д.)
Распределение методом приближений Фогеля
Метод приближений Фогеля (Vogel's Approximation Method — VAM) также основан на распределении потребностей с учетом затрат на транспортировку. Процесс распределения осуществляется в пять следующих этапов.
Этап 1. В каждой строке и в каждом столбце, включая фиктивные, определите разницу между двумя наименьшими значениями затрат на транспортировку в ячейках каждой строки и каждого столбца.
Этап 2. Определите столбец или строку с наибольшей разницей.
Этап 3. Вставьте наибольшее возможное значение единиц в ячейке с наименьшими затратами в строке или столбце с самой большой разницей, выбранной на этапе 2.
Этап 4. Прекратите процесс, если удовлетворены все потребности строк и столбцов. В противном случае переходите к следующему этапу.
Этап 5. Пересчитайте разницу между оставшимися незаполненными двумя ячейками с наименьшими затратами в каждой строке и в каждом столбце. При вычислении дальнейшей разницы не следует учитывать строки и столбцы с нулевыми показателями потребности или поставок. Вернитесь к этапу 2.
Метод приближений Фогеля обычно позволяет получить оптимальное или близкое к оптимальному исходное решение. Одно из исследований показало, что данный метод дает оптимальное решение для 80% задач. (Наши студенты утверждают, что остальные 20% — это как раз те задачи, которые попадаются им на экзаменах.) На рис. 7д.9 проиллюстрировано применение метода Фогеля для решения рассматриваемой нами задачи. (Первыми указаны значения в ячейке А-Е, затем в C-G, далее в D-H, в D-F И Т.Д.)
Обратите внимание, что это исходное решение совпадает с оптимальным, которое получено в результате всех возможных улучшений исходного размещения, выполненного методом верхней левой ячейки (сравните дальше с рис. 7д.12).
Стадия III. Получение оптимального решения
Поиск оптимального решения в транспортной задаче заключается в оценке каждой неиспользованной ячейки и определении, не будет ли перемещение в нее выгодным с точки зрения уменьшения общих затрат. Если это так, перемещение выполняется и процесс повторяется. Задача считается решенной после того, как все ячейки оценены и проведены все соответствующие перемещения.
Метод последовательных шагов
Одним из распространенных методов оценки ячеек является метод последовательных шагов, или метод "подводных камней". Это название появилось в первых описаниях метода, в которых незаполненные ячейки сравнивались с водой, а заполненные — с камнями, по аналогии с переходом через ручей с камня на камень. Мы применим этот метод к поиску решения для исходного размещения, выполненного методом северо-западной ячейки и приведенного для нашей задачи на рис. 7д,8.
Этап 1. Выберите любую пустую ячейку и укажите замкнутый путь, ведущий к ней. Этот путь состоит из горизонтальных и вертикальных линий, которые ведут от пус той ячейки через другие обратно к ней же5. В замкнутом пути может быть только одна пустая ячейка, которую мы и рассматриваем. Повороты пути на 90° могут производиться только в ближайших (к пустой) заполненных ячейках. На рис. 7д. 10 показаны два замкнутых пути. Замкнутый путь а необходим для оценки пустой ячейки В-Е; замкнутый путь b нужен для оценки пустой ячейки А-Н.
5 Если распределение было сделано правильно, в матрице содержится только один замкнутый путь для каждой ячейки.

Общие затраты = 10($25) + 5($35) + 6($30) + 1($50) + 13(526) + 2($66) + 9($27) = $1,368


Рис. 7д. 7. Распределение методом северо-западной ячейки

Общие затраты = 10($25) + 14($26) + 9(S27) + 6($30) + 5($35) + 1($40) + 1 ($66) = $1,318 Рис. 7д.8. Распределение методом наименьших затрат





Total cost = 10($25) + 14($26) + 9($27) + 2($40) + 1($36) + 4($35) + 6($30) = $1,293 Рис. 7д. 9. Распределение методом приближений Фогеля
Этап 2. Переместите одну единицу из заполненной ячейки в угле замкнутого пути в пустую ячейку и измените оставшиеся заполненные ячейки в других углах в соответствии с выполненным перемещением6. Изменение заключается в добавлении и вычитании единиц из заполненных ячеек способом, при котором не нарушаются указанные общие ограничения в отношении поставок и потребностей. Для этого необходимо, чтобы из каждой строки или столбца, в ячейки которых была добавлена или вычтена единица, обязательно вычиталась или добавлялась одна единица, но из других ячеек, лежащих на пути. Таким образом, для пути а потребуются следующие добавления и вычитания. Для проверки возможности перемещения можно добавить не одну, а больше единиц. Однако, поскольку рассматриваемая нами задача носит линейный характер, если возможно смещение на одну единицу, то будет возможным смещение и на большее число единиц, и наоборот.
Прибавьте одну единицу в ячейке В-Е (пустая ячейка).
Вычтите одну единицу из ячейки B-F.
Прибавьте одну единицу в ячейке A-F.
Вычтите одну единицу из ячейки А-Е.
Для более длинного пути b потребуется следующее.
Прибавьте одну единицу в ячейке А-Н (пустая ячейка).
Вычтите одну единицу из ячейки D-H. Прибавьте одну единицу в ячейке D-G. Вычтите одну единицу из ячейки C-G. Прибавьте одну единицу в ячейке C-F. Вычтите одну единицу из ячейки A-F.
Этап 3. Определите, желательно ли данное перемещение. Это легко выполняется с помощью суммирования значений затрат в ячейке, к которой была добавлена единица; суммирования значений затрат в ячейке, из которой была вычтена единица; получения разницы между этими двумя суммами, благодаря чему можно определить, сократились ли как-нибудь затраты.
Если затраты в результате перемещений сократились, следует переместить как можно больше единиц из оцененной заполненной ячейки в пустую. Если же затраты повысились, никаких перемещений делать не стоит, а пустую ячейку надо перечеркнуть или пометить каким-либо иным способом, чтобы показать, что ее уже оценивали. (Обычно для обозначения ячейки, которая прошла оценку в ходе решения задач минимизации затрат и была признана нежелательной для перемещения, пользуются большим знаком "плюс". В этих же случаях при решении задач максимизации прибыли используют большой знак "минус".) Для ячейки В-Е такие плюсы и минусы будут

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

+

-

$55 (В-Е)

$30 (B-F)

35 (A-F)

25 (A-F)

$90

$55

Для ячейки A-F эти знаки будут расставлены так:

+

-

$60(А-Н)

$27(D-H)

66 (D-G)

26 (C-G)

50 (C-F)

35 (A-F)

$176

$88

Таким образом, в обоих случаях очевидно, что перемещений в любую пустую ячейку делать не следует, так как получаемые разности положительны.
Этап 4. Повторяйте этапы 1—3 до тех пор, пока не будут оценены все пустые ячейки. Чтобы проиллюстрировать технику выполнения перемещения, рассмотрите ячейку D-F и короткий замкнутый путь, ведущий к ней: C-F, C-G и 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д.11 имеет замкнутый путь 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 долл.



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



Рис. 7д. 12. Оптимальное решение транспортной задачи
W X у Поставки фабрики
т 'LL.
ШШШт
Li_
ШШшш
Li_
0
11
и .Li- и_ и_
вШиМ
9
V и_
'3.
ц_ UL 3
Потребности складов 6 8 9

m + n - 1 = 5 заполненных ячеек
Фактическое распределение —
4 заполненные ячейки

Рис. 7д. 13. Транспортная задача с явлением вырождения


Вырождение
Явление вырождения (Degeneracy) возникает в транспортных задачах, когда количество заполненных ячеек меньше суммы количества строк и столбцов минус 1 (т.е. т + п — 1). Вырождение может наблюдаться во время исходного распределения, когда первое значение в строке или столбце удовлетворяет ограничениям как по строке, так и по столбцу. Для оценки полученного решения в матрице необходимо определенным образом скорректировать вырождение. Такая корректировка заключается во вставке некоторого количества единиц в в пустые ячейки так, чтобы можно было составить замкнутый путь для оценки других пустых ячеек. Значение в может быть бесконечно малым числом и не оказывать влияния на решение. При этом обычная процедура предусматривает, что некое значение в используется точно так же, как реальное число, но может быть размешено в любую пустую ячейку без соблюдения требований к ограничениям по строкам и столбцам.
Оптимальное по минимальным затратам на транспортировку решение транспортной задачи с явлением вырождения показано на рис. 7д.13. На этом рисунке видно, что, если бы в матрицу не было включено значение в, некоторые из ячеек оценить было бы невозможно (включая ту, к которой это значение было добавлено).
После того, как в вводится в решение, это значение остается в нем до тех пор, пока либо оно не исчезнет при вычитании, либо до получения окончательного решения.
Выбор ячейки, в которую следует вводить в, принимается произвольно, но можно сэкономить немало времени, если вставить это значение в ту ячейку, в которой его можно использовать для оценки как можно большего количества ячеек, не перемещая его. Вы можете убедиться, что на рис. 7д.13 значение в расположено именно в таком наиболее выгодном месте.
Альтернативные оптимальные решения
Если оценка пустой ячейки дает в результате то же значение затрат, что и имеющееся распределение, значит существует равноценное альтернативное оптимальное решение7. В таких случаях управленческий персонал приобретает дополнительную возможность составлять гибкий окончательный график поставок продукции, используя два равноценных оптимальных размещения. (Обычно пустую ячейку, определенную как альтернативный оптимальный маршрут, помечают, например большой цифрой 0.) Учитывая, что все остальные ячейки распределены оптимально.
Резюме
Данное дополнение было в основном посвящено различным процедурам решения задач линейного программирования. Задачи такого типа, решаемые без применения вычислительной техники, встречаются крайне редко. Кроме того, сегодня в нашем распоряжении столько компьютеров и компьютерных программ, что решение их "вручную" было бы просто неоправданной тратой времени8. Существуют также программы, помогающие строить сами модели линейного программирования. Самая известная из них, по всей вероятности, GAMS— General Aigebraic Modeling System (GAMS — General, San Francisco, CA).
Задачи с решениями Задача 1
В ходе производства два вида продукции X и Y проходят обработку на станках I и II. У станка I есть 200 часов доступного времени, а у станка II — 400. Для обработки одной единицы продукции X необходим один час работы на станке I и четыре часа на станке II. Обработка продукции Y требует одного часа на станке I и одного — на станке II. Единица продукции X дает прибыль в размере 10 долл., а единица продукции Y — 5 долл. Все эти условия выражаются следующими уравнениями:
Х+ Ylt; 200 (станок I).
4Х+ Ylt;400 (станок II).
Максимизировать $10Х + $5Y.
Решите графическим методом задачу определения оптимального использования машинного времени.
Решение
Оптимальная точка, как показано ниже на графике, имеет координаты: Х= 67, Y=
133.
Прибыль в этой точке составит ($10x67) + ($5x33) = $1335.
Чтобы построить первую линию равной прибыли, предположим:
10X-+ 5Y= 500;
@Х=0, Y= 100; @Y= 0, Х= 50.



Продолжая параллельно перемещать эту линию равной прибыли дальше, до тех пор, пока она не достигнет наиболее удаленной точки допустимой области, получим оптимальное решение с приблизительными координатами: Х=67, Y= 133.
Задача 2
Решите задачу 1 с использованием симплексного метода. Решение
Симплексное решение задачи 1:



$10

$5

0

0




X

Y

Si

S2



S1

1

1

1

0

200


S2

4

1

0

1

400



$10

$5

0

0


Первая итерация

S1

0

3/4

1

-1/4

100








X

1

1/4

0

1/4

100



0

2,50

0

-2,50


Вторая итерация

Y

0

1

4/3

-1/3

133








X

1

0

-1/3

1/3

67





$-3,33

$-1,66


При Х= 67, а Y= 133 значение целевой функции будет Z= ($10 х 67) + ($5 х 133) = $1335.
Вопросы для контроля и обсуждения Какие требования предъявляются к задаче, чтобы решать ее методами линейного программирования? Какую дополнительную информацию можно получить из решения задачи симплексным методом? Какая информация содержится в теневых ценах? Что представляют собой свободные переменные? Почему они необходимы при применении симплексного метода? В каких случаях они используются при применении транспортного метода? В данном дополнении утверждается, что оптимальное решение симплексной задачи всегда находится на фа-фике в угловой точке. При каком условии можно найти равноценное оптимальное решение в другой точке? Что представляет собой выпуклый многоугольник в графическом решении? Как выпуклость многоугольника графического решения проявляется в симплексном методе? Как определить, не присутствует ли в транспортной задаче явление вырождения? Что следует делать при необходимости протестировать на оптимальность решение такой задачи?
Задачи Решите графически следующую задачу: 12X+14Ylt;84;
3X+2Ylt;18;
Хlt;4.
Максимизируйте ЗХ + Y. Решите следующую задачу графическим методом линейного программирования.
4А + 6Вgt;120;
2А + 6Вgt;72;
Вgt;10.
Минимизируйте 2А + 4В. Компания Bindley заключила контракт на один год на поставку моторов для всех видов стиральных машин, выпускаемых компанией Rinso Ltd. Rinso Ltd производит машины на четырех заводах, расположенных в разных концах страны: в Нью-Йорке, в Форт-Уэрте, в Сан-Диего и в Миннеаполисе со следующими объемами:
Нью-Йорк — 50 000;
Форт-Уэрт — 70 000;
Сан Диего — 60 000;
Миннеаполис — 80 000.
Bindley имеет три завода, выпускающие              моторы,              со следующими
производственными мощностями:
Boulder — 100 000;
Macon — 100 000;
Gary- 150 000.
Вследствие варьирования производственных и транспортных издержек прибыль, которую получает Bindley от каждых ста единиц продукции, зависит от того, в каком именно месте она была выпущена и от способа ее доставки. В следующей таблице приведены данные, предоставленные бухгалтерией компании? о прибыли на единицу продукции (в долл.).

Доставка продукции в

Произведено в

Нью-Йорк

Форт-Уэрт

Сан-Диего

Миннеаполис

Boulder

7

11

8

13

Macon

20

17

12

10

Gary

8

18

13

16

Выбрав в качестве критерия максимум прибыли, компания хотела бы определить, сколько моторов необходимо производить на каждом заводе и сколько моторов следует поставлять с каждого завода каждому из трех заводов-заказчиков. Составьте транспортную матрицу для этой задачи. Найдите оптимальное решение. Решите следующую задачу с использованием графического метода линейного программирования.
16Х + 10Ylt;160;
12X+ 14Ylt;168;
Ygt;2.
Максимизируйте 2Х + 10Y. Производственная компания прекратила выпуск ставшего неприбыльным ассортимента продукции, в результате чего освободились значительные производственные мощности. Управленческий персонал фирмы рассматривает возможность использования этих дополнительных мощностей для выпуска одного или двух из трех выпускаемых ею изделий: Х1} Х2 и Х3.
Машинное время в часах, необходимое для выпуска единицы каждого вида продукции, следующее:

Тип станка

Продукция

Xj


*5

Фрезерные станки

8

2

3

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

4

3

0

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

2

0

1

Доступное время в неделю:


Количество часов в неделю

Фрезерные станки

800

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

480

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

320

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

Прибыль на единицу продукции

Х1

$20

Х2

6

ХЗ

8
Составьте уравнения, решив которые, можно максимизировать недельную прибыль. Решите эти уравнения симплексным методом. Каким будет оптимальное решение? Какое количество каждого вида продукции следует выпускать фирме, и какова будет полученная в результате прибыль? Как данная ситуация отразится на работе каждой группы станков? Будут ли они работать на полную мощность или будет оставаться неиспользованное машинное время? Будет ли продукция Х3 выпускаться в количестве, достаточном для обеспечения максимальных объемов продаж? Предположим, что вследствие сверхурочной эксплуатации фрезерных станков можно увеличить доступное машинное время на 200 часов в неделю. Рекомендовали бы вы это сделать? Объясните, что привело вас к такому выводу. Rent'R Cars— это компания по аренде автомобилей, имеющая несколько точек обслуживания по всему городу. Для повышения качества обслуживания фирма начала реализовывать новую политику "возврат машины по адресу, самому удобному для клиента". Однако это означает, что компании приходится постоянно перемещать машины по всему городу с тем, чтобы обеспечить необходимое количество транспорта. В приведенной ниже матрице содержатся данные относительно необходимого количества и потребности в автомобилях экономичного класса, а также общая стоимость на перемещение этих машин из одной точки в другую.


Найдите решение, которое позволило бы минимизировать стоимость перемещения транспорта. Что вам пришлось бы сделать, если частью оптимального решения станет обязательное перемещение автомобилей из точки А в точку D? Для столовых общежитий Аризонского университета разрабатывается новая диета. Основная цель заключается в том, чтобы питание обходилось студентам как можно дешевле, но рацион должен содержать от 1800 до 3600 калорий. При этом не более чем 1400 калорий должны быть из углеводов и не менее 400 из белков. Диета должна состоять из двух продуктов: А и В. Продукт А стоит 0,75 долл. за фунт и содержит 600 калорий, 400 из которых белки, а 200 углеводы. Каждый студент должен потреблять не больше двух фунтов продукта А. Продукт В стоит 0,15 долл. за фунт и содержит 900 калорий, из которых 700 углеводы, 100 — белки и 100 — жиры. Составьте уравнения, которые отображали бы все исходные данные. Решите задачу графически для каждого вида продуктов, которые должны получать студенты. Сформулируйте и решите задачу 7, добавив дополнительное ограничение, которое заключается в том, что не более чем 150 калорий должно поступать в организм из
жиров, а цена при этом повышается до 1,75 долл. за фунт продукта А и 2,50 долл. за фунт продукта В. Компания Logan Manufacturing хочет смешать два вида топлива (А и В) для своих грузовиков, чтобы минимизировать их стоимость. Для нормальной эксплуатации машин на протяжении следующего месяца компании понадобится не менее чем 3000 галлонов топлива. Максимальная емкость для хранения топлива фирмы составляет 4000 галлонов. В наличии есть 2000 галлонов топлива А и 400 галлонов топлива В. Смешанное топливо должно иметь октановое число не меньше 80.
При смешивании топлива объем полученной смеси равен сумме смешиваемых объемов. Октановое число представляет собой среднее взвешенное отдельных октановых чисел, взятых в пропорциональном отношении от соответствующих объемов. Известно также следующее: топливо А имеет октановое число 90 и стоит 1,20 долл. за галлон; топливо В имеет октановое число 75 и стоит 0,90 долл. за галлон, а) Составьте уравнения, отображающие эти исходные данные. Решите задачу графически, учитывая объемы каждого используемого вида топлива. Назовите все допущения, которые необходимо сделать для решения данной задачи. 10. Внимательно проанализируйте информацию в нижеприведенном симплексном решении:

X

Y

Z

S1

S2

S3


0

5

0

-2

1

1

40

0

-3

1

3

-2

0

90

1

4

0

-4

3

0

60

0

-7

0

-2

-3

0


Ответьте на следующие вопросы. Что представляют собой значения X, Y, Z, S1, S2 и S3? Правильны ли ответы, приведенные ниже?


Стоит ли покупать данную продукцию?

По какой цене?

Сколько?

S1

Да

lt;2

15

S2

Да

lt;3

45

S3

Да

lt;0



Стоит ли продавать данную продукцию?

По какой цене?

Сколько?

S1

Да

gt;2

30

S2

Да

gt;3

20

S3

Да

gt;0

40
Предположим, вы хотите составить бюджет, позволяющий оптимизировать некоторую часть вашего дохода после уплаты налогов. При этом вы можете выделить максимум 1500 долл. в месяц на питание, жилье и развлечения. Общая сумма, выделенная на питание и жилье, не должна превышать 700 долл., а на развлечения вы можете позволить себе выделить не больше 300 долл. в месяц. Каждый доллар, потраченный на еду, дает удовлетворение, оцениваемое в 2 балла; один доллар, потраченный на жилье, — 3 балла; а каждый доллар, потраченный на развлечения, — 5 баллов.
Предполагая линейность взаимосвязей, воспользуйтесь симплексным методом линейного программирования и определите оптимальное распределение своих средств.
12. Решите следующие неравенства с применением симплексного метода:
3Xi + 2Х2+4Хзlt;32;
Xi+ ЗХ2+4Хзlt;36;
Х + Х2lt; 13. Максимизируйте 10Х1 + 12Х2+ 16Х3
Основная библиография D. Eppen and F.J. Gould, Introductory Management Science, 4th ed. (Englewood Cliffs, NJ: Prentice Hall, 1993). J.Greeberg, "How to analyze the Results of Linear Programs — Part 2: Price Interpretation", Interfaces, September-October 1993, p. 97-114.
John Llewellyn and Ramesh Sharda, "Linear Programming Software for Personal Computers: 1990 Survey". OR/MS Today, October 1990, p. 35-47.
R. Sharda, "Mathematical Programming on Microcomputers: Directions in Performance and User Interfaces". In Mathematical Models for Decision Support, ed. G. Mitra (New York: Springer-Verlag), 1988, p. 279-293.
R. Sharda, "Mathematical Programming Software for the Microcomputer: recent Advance". In Decision-Aiding Software and Decision Analysis, ed. S. Nagel (Cambridge, England: Cambridge University Press, 1990).
Hamdy A. Taha, Operations Research (New York: Mac-millan, 1992).
Wayne L. Winston and S. Christian Albright, Practical Management Science: Spreadsheet Modeling and Application (Belmont, CA: Duxbury Press, 1997).
<< | >>
Источник: Ричард Чейз, Николас Дж. Эквилайн, Роберт Ф. Якобс. Производственный и операционный менеджмент. 8-е издание. 2004

Еще по теме Транспортный метод:

  1. Цель занятия - изучение метода определения срока (точки) замены транспортного средства, основанного на точном учете затрат на ремонт в процессе его эксплуатации, а также на маркетинговых исследованиях рынка транспортных средств, бывших в употреблении.
  2. Глава 4 ОСНОВНЫЕ ПОДХОДЫ И МЕТОДЫ ОЦЕНКИ СТОИМОСТИ МАШИН, ОБОРУДОВАНИЯ И ТРАНСПОРТНЫХ СРЕДСТВ
  3. 5.1. Статистические методы в оценке машин, оборудования и транспортных средств
  4. Задание Определить срок замены транспортного средства методом минимума общих затрат.
  5. Глава 5 ТРАНСПОРТНОЕ ХОЗЯЙСТВО, ИЛИ ТРАНСПОРТНАЯ ЛОГИСТИКА
  6. Процедура изменения регистрационных данных транспортных средств закреплена в ст.ст.36–39Правил регистрации транспортных средств.
  7. Процедура снятия с регистрационного учета транспортных средств закреплена в ст.ст. 40 - 45 Правил регистрации транспортных средств.
  8. § 3. Транспортное право и транспортное законодательство
  9. § 6. Ответственность перевозчика за неподачу транспортных средств и отправителя - за неиспользование поданных транспортных средств
  10. Транспортная логистика Сущность и задачи транспортной логистики
  11. § г. Транспортный налог
  12. Транспортный налог
  13. Транспортный налог
  14. Транспортный налог
  15. Транспортное право
  16. 6.3.7. Транспортный налог
  17. 5. Транспортная документация
  18. ТРАНСПОРТНЫЙ НАЛОГ
- Cвязи с общественностью - PR - Бренд-маркетинг - Деловая коммуникация - Деловое общение и этикет - Делопроизводство - Интернет - маркетинг - Информационные технологии - Консалтинг - Контроллинг - Корпоративное управление - Культура организации - Лидерство - Литература по маркетингу - Логистика - Маркетинг в бизнесе - Маркетинг в отраслях - Маркетинг на предприятии - Маркетинговые коммуникации - Международный маркетинг - Менеджмент - Менеджмент организации - Менеджмент руководителей - Моделирование бизнес-процессов - Мотивация - Организационное поведение - Основы маркетинга - Производственный менеджмент - Реклама - Сбалансированная система показателей - Сетевой маркетинг - Стратегический менеджмент - Тайм-менеджмент - Телекоммуникации - Теория организации - Товароведение и экспертиза товаров - Управление бизнес-процессами - Управление знаниями - Управление инновационными проектами - Управление качеством товара - Управление персоналом - Управление продажами - Управление проектами - Управленческие решения -