9789
.pdfj запланировано перевезти xij единиц груза, то стоимость перевозки соста-
вит cij∙xij. Транспортная задача относится к двух индексным задачам линейного программирования, так как в результате решения задачи необходимо найти матрицу Х с компонентами xij. Стоимость всего плана выразится двойной сум-
m |
n |
мой S cij xij . Систему ограничений получаем из условий задачи: |
|
i 1 |
j 1 |
n
а) все грузы должны быть перевезены, т.е. xij ai , i =1,..., m.
j 1
m
б) все потребности должны быть удовлетворены, т.е. xij bj , j =1,..., n.
i 1
Таким образом, математическая модель транспортной задачи имеет следу-
m |
n |
|
|
|
|
ющий вид: S cij xij |
min |
|
|||
i 1 |
j 1 |
|
|
|
|
|
|
|
n |
ai |
|
|
|
|
xij |
, i = 1,..., m |
|
|
|
j 1 |
|
|
|
|
|
m |
b j |
|
|
|
|
xij |
, j = 1,..., n |
||
|
|
i 1 |
|
|
|
|
|
x 0, i 1,..., m; j = 1,..., n. |
|||
|
|
|
ij |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В рассмотренной модели предполагается, что суммарные запасы равны |
|||||
|
|
|
m |
|
n |
суммарным потребностям, т.е. ai |
bj . Транспортная задача, в которой |
||||
|
|
|
i 1 |
|
j 1 |
суммарные запасы и потребности совпадают, называется закрытой моделью; в
противном случае − открытой. Для открытой модели может быть два случая:
m |
|
n |
а) суммарные запасы превышают суммарные потребности: ai |
bj . |
|
i 1 |
|
j 1 |
m |
|
n |
б) суммарные потребности превышают суммарные запасы: ai |
bj . |
|
i 1 |
|
j 1 |
61 |
|
|
Открытая модель решается приведением к открытой модели. В случае а),
когда суммарные запасы превышают суммарные потребности, вводится фик-
тивный потребитель bn+1, потребность которого описывается формулой:
m |
n |
bn 1 ai |
bj , а для случая б), когда суммарные потребности превыша- |
i 1 |
j 1 |
ют суммарные запасы, вводится фиктивный поставщик am+1, запасы которого
n |
m |
описываются формулой: am 1 bj |
ai . Стоимость перевозки единицы |
j 1 |
i 1 |
груза до фиктивного потребителя и стоимость перевозки груза от фиктивного поставщика полагаются равными нулю, так как груз в обоих случаях не перево-
зится.
Транспортная задача имеет n + m уравнений с m∙n неизвестными. Матрицу перевозок Х = (xij)mn, удовлетворяющую ограничениям, называют планом пере-
возок транспортной задачи, а xij − перевозками. План Х*, при котором целевая функция S достигает минимума, называется оптимальным.
Пример. Четыре предприятия для производства продукции используют не-
которое сырье. Спрос на сырье для каждого из предприятий составляет соот-
ветственно 120, 50, 190 и 110 у.е. Сырье сосредоточено в трех местах. Предло-
жения поставщиков сырья равны 160, 140 и 120 у.е. На каждое предприятие сырье может завозиться от любого поставщика. Тарифы перевозок известны и
7 |
8 |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
задаются матрицей C |
4 |
5 |
9 |
8 |
|
. Требуется составить план перевозок, при |
|
9 |
2 |
3 |
6 |
|
|
|
|
|
котором общая стоимость перевозок будет минимальной.
Решение: Так как суммарные запасы превышают суммарные потребности
(160 + 140 + 200 = 500 > 470 = 120 + 50 + 190 + 110), то вводим фиктивного по-
требителя b5, потребность которого составляет 500 – 470 = 30. Составим эко-
номико-математическую модель задачи:
62
xij − количество единиц груза, запланированных к перевозке от поставщика i к потребителю j, i = 1, 2, 3; j = 1, 2, 3, 4, 5.
S = 7x11 + 8x12 + x13 + 2x14 + 4x21 + 5x22 + 9x23 + 8x24 + 9x31 + 2x32 + 3x33 +
6x34 + 0x15 + 0x25 |
+ 0x35 min |
|||||
x |
x |
|
x |
x |
x |
160 |
11 |
12 |
13 |
14 |
15 |
|
|
x21 |
x22 |
x23 |
x24 |
x25 140 |
||
x |
x |
|
x |
x |
x |
200 |
31 |
|
32 |
33 |
34 |
35 |
|
x11 x21 x31 120 |
|
|||||
|
x22 |
x32 50 |
|
|
||
x12 |
|
|
||||
x |
x |
|
x |
190 |
|
|
13 |
|
23 |
33 |
|
|
|
x14 |
x24 |
x34 |
110 |
|
||
x |
x |
25 |
x |
30 |
|
|
15 |
|
35 |
|
|
|
|
x |
0, i 1,2,3; j 1,2,3,4,5 |
|||||
ij |
|
|
|
|
|
|
Рассмотрим технологию решения транспортной задачи, используя условия примера.
1) выберем адреса ячеек, в которые будет помещен результат ре-
шения (изменяемые ячейки) и оптимальное значение целевой функции;
В нашей задаче оптимальные значения хij будут помещены в ячейках В21:F23 (для удобства ссылок запишем в каждую из них 1), оптимальное зна-
чение целевой функции ‒ в ячейке G18 (см. рис. 1).
2)введем зависимость для целевой функции;
Вячейки B16:F18 вводим тарифы. Далее необходимо произвести следую-
щие действия:
−поместить курсор в ячейку G18 (после решения задачи в данной ячейке будет находиться значение целевой функции);
−запустить Мастер функций (значок fх);
−в окне Категория выбрать Математические;
−в окне Функция выбрать СУММПРОИЗВ;
−нажать кнопку ОК;
63
− в окне СУММПРОИЗВ указать адреса массивов, элементы которых обрабатываются этой функцией. В задаче целевая функция представляет
собой произведение удельных затрат на доставку груза (расположенных в блоке ячеек B16:F18) и объемов поставок для каждого потребителя (содержи-
мое ячеек В21:F23). Для этого надо:
−в поле Массив 1 указать адреса В21:F23;
−в поле Массив 2 указать адреса B16:F18;
−нажать кнопку ОК − подтверждение окончания ввода адресов массивов.
В поле ячейки G18 появится некоторое числовое значение, равное произ-
ведению единичных поставок на удельные коэффициенты затрат по доставке грузов (в данной задаче это число 64).
введем зависимости для ограничений;
−выделим курсором ячейки B21:F21;
−в главном меню выберем знак Σ;
−аналогичные действия выполним с ячейками B22:F22 и B23:F23. В ячей-
ках G21:G23 появятся пятерки;
− в ячейки H21:H23 поместим числа 160, 140, 200.
Таким образом мы описали первые три ограничения в математической мо-
дели. Аналогично поступаем с остальными ограничениями:
−выделим курсором ячейки B21:В23;
−в главном меню выберем знак Σ;
−аналогичные действия выполним с ячейками C21:C23, D21:D23, E21:E23, F21:F23. В ячейках B24:F23 появятся тройки;
−в ячейки B25:F25 поместим числа 120, 50, 190, 110.
64
Рис. 1.
Выберем команду меню Данные → Поиск решения. В отрывшемся окне выполним следующие действия:
а) назначим ячейку для целевой функции (G18), укажем адреса изменяе-
мых ячеек (В21:F23), установим флажок на минимум.
б) введем ограничения;
в) в строке Выберите метод решения выберем вариант «Поиск решения лин. задач симплекс-методом».
Теперь введены все необходимые условия для решения задачи:
Рис. 2.
65
Осталось поместить указатель мыши на кнопку Найти решение:
Рис. 3.
Ответ: от первого поставщика третьему предприятию следует перевезти
50 у.е. груза, четвертому предприятию – 110 у.е. груза;
от второго поставщика первому предприятию следует перевезти 120 у.е.
груза;
от третьего поставщика второму предприятию следует перевезти 50 у.е.
груза, третьему предприятию – 140 у.е. груза;
груз, предназначенный для пятого (фиктивного) потребителя остается у второго поставщика (20 у.е.) и третьего поставщика (10 у.е.).
Общая стоимость перевозок составит 1270 у.е.
Задача 5. Двухэтапная производственно-транспортная задача.
Краткие теоретические сведения
В отличие от классической транспортной задачи в двухэтапной задаче потребитель получает продукцию не от поставщика, а через промежуточное звено, например со склада.
Рассмотрим двухэтапную задачу: поставщик – склад – потребитель. Пусть m поставщиков однородной продукции с мощностями а1, a2,..., am направляют ее p складам с пропускными способностями d1, d2,..., d p , которые, в свою очередь,
66
поставляют эту продукцию потребителям со спросом b1,b2,...,bn. Известны
издержки cik и сkj |
по доставке ед. продукции от i –го поставщика на k –й склад |
||||||
и с k –го склада |
j –му потребителю i |
|
; j |
|
;k |
|
. Найти оптимальный |
1, m |
1, n |
1, p |
план перевозок и прикрепление поставщиков к складам, складов к потребителям, при котором суммарные издержки будут минимальными.
Обычно в таких задачах выполняется условие баланса: аi b j dk , т. е.
i i k
количество груза, отправляемое поставщиками равно суммарной потребности, а
емкость складов превышает эту величину.
В случае аij b j dk задачу можно решать по частям: сначала найти оптимальный план прикрепления складов к поставщикам продукции, за-
тем складов к потребителям. Если аi b j dk , то решение задачи по ча-
стям может привести к несогласованности планов оптимизации первого и вто-
рого этапов.
В этом случае задача решается одновременно в одной таблице.
Математическая модель задачи
z cik ckj xikj min , i k j
1. |
xikj ai i |
|
|
|
, |
||||
1, m |
|||||||||
|
j |
k |
|
|
|
|
|
|
|
2. |
xikj b j |
j |
|
|
, |
||||
1, n |
|||||||||
|
i |
k |
|
|
|
|
|
|
|
|
xikj dk |
|
|
|
|||||
3. |
(k 1, p) , |
ij
4.xikj 0, i 1, m , j 1, n , k 1, p .
1-я группа ограничений показывает, что вся продукция вывозится с пред-
приятий на склады, 2-я – что спрос потребителей должен быть удовлетворен, 3-
я – что пропускная способность складов превышает суммарную мощность по-
67
ставщиков и суммарный спрос потребителей. Такая задача решается методом фиктивной диагонали.
Пример решения задачи
Покажем реализацию этого метода на условном примере. Пусть предприя-
тие имеет три цеха по производству продукции и два склада, где хранится изго-
товленная продукция перед отправкой ее потребителю. Со складов продукция доставляется трем потребителям. Известны мощности цехов по производству продукции ai 240,260,300 , пропускные способности складов dk 400,600 , по-
требности |
потребителей |
в продукции |
b j (270;330;200) , стоимость перевозки |
|||||||
|
|
|
|
|
|
3 |
4 |
|
||
|
|
|
|
|
на склад cik |
|
|
|
|
|
единицы |
|
груза с цеха |
|
5 |
6 |
|
и со склада до потребителя |
|||
|
|
|
|
|
|
|
2 |
4 |
|
|
|
|
|
|
|
|
|
|
|
||
c |
4 |
3 |
5 |
. Прямые поставки продукции из цеха потребителю запрещены, |
||||||
|
|
|
||||||||
kj |
|
3 |
|
|
|
|
|
|
|
|
|
6 |
4 |
|
|
|
|
|
|
|
потребитель получает готовую продукцию со складов. Определить оптималь-
ный план перевозок, минимизирующий суммарные затраты. Склады на первом этапе являются потребителями продукции, на втором – поставщиками, поэтому им в таблице отводятся столбцы как потребителям и строки как поставщикам.
Так как потребители получают продукцию со складов, запретим прямые по-
ставки тарифами M , что обеспечивает условие оптимальности для клеток
с cij M , так как для этих клеток характеристики
ij cij ki v j M ki v j 0 на всех этапах решения.
Перевозки со склада на склад также запрещены, они блокируются запрети-
тельными тарифами М. Разрешается поставка склада самому себе, что означает размер неиспользованной мощности склада.
Заполним по методу минимального элемента сначала блок таблицы, в ко-
тором отражаются перевозки продукции со складов потребителям, затем фик-
тивную диагональ, затем перевозки от поставщиков на склады. Получим сле-
дующую таблицу.
68
План х1
|
|
d1=400 |
|
d2=600 |
|
b1=270 |
|
b2=330 |
|
b3=200 |
u1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
а1 |
240 |
0 |
3 |
240 |
4 |
|
M |
|
|
M |
M |
4 |
|
|
|
|
|
|
|
|
|
|
|
||
а2 |
260 |
100 |
5 |
160 |
6 |
|
M |
|
|
M |
M |
6 |
|
|
|
|
|
|
|
|
|
|
|
||
а3 |
300 |
300 |
2 |
1 |
4 |
|
M |
|
|
M |
M |
3 |
|
|
|
|
|
|
|
|
|
|
|
||
d1 |
400 |
|
0 |
|
M |
+ |
4 |
- |
3 |
5 |
-2 |
|
|
|
3 |
|
|
|
70 |
|
|
330 |
|
3 |
|
d2 600 |
|
M |
|
0 |
- |
6 |
|
+ |
3 |
4 |
0 |
|
|
|
|
|
|||||||||
|
|
|
|
200 |
|
200 |
|
-2 |
|
|
200 |
|
|
v j |
-1 |
|
0 |
|
6 |
|
5 |
|
4 |
|
Для этого плана общие издержки составят: Z1=6290. Число занятых клеток в таблице m+n-1=5+5-1=9. Далее решаем задачу методом потенциалов.
Рассчитав потенциалы и характеристики для этого плана по аналогии с предыдущим, видим, что полученный план х1 неоптимальный, так как E54 2 .
Строим для клетки (5,4) контур (5,4)-(5,3)-(4,3)-(4,4)-(5,4) и перемешаем по нему поставку min(200,300) = 200. Получим план х2. При этом z уменьшится на величину z E54 2 200 400 , в соответствии с экономическим смыс-
лом характеристики План х2 оптимальный, так как все характеристики свободных клеток неот-
рицательны, и не единственный, Е11 0 . zmin 6290 400 5890.
Поставка в фиктивную диагональ х52=200 означает размер неиспользован-
ной мощности второго склада.
План х2
|
400 |
600 |
270 |
330 |
200 |
ui |
240 |
3 |
4 |
М |
М |
М |
4 |
|
0 |
240 |
|
|
|
|
260 |
5 |
6 |
М |
М |
М |
6 |
|
100 |
160 |
|
|
|
|
300 |
2 |
4 |
М |
М |
М |
3 |
|
300 |
1 |
|
|
|
|
400 |
0 |
|
4 |
3 |
5 |
0 |
|
1 |
М |
270 |
130 |
1 |
|
600 |
М |
0 |
6 |
3 |
4 |
0 |
|
|
|
69 |
|
|
|
|
|
200 |
2 |
200 |
200 |
|
v j |
-1 |
0 |
4 |
3 |
4 |
|
Задача 6. Задача о назначениях
Задача о назначениях − это распределительная задача, в которой для выполне-
ния каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), и каждый ресурс может быть использован на одной и толь-
ко одной работе. То есть ресурсы неделимы между работами, а работы недели-
мы между ресурсами. Таким образом, задача о назначениях является частным случаем транспортной задачи. Задача о назначениях имеет место при распреде-
лении людей на должности или работы, автомашин на маршруты, водителей на машины, групп по аудиториям, научных тем по научно-исследовательским ла-
бораториям и т.п. Модель назначений можно построить в виде транспортной модели, в которой предложение в каждой исходной точке и спрос в каждом ко-
нечном пункте равны 1.
Пример Президент компании Auto Power решил, что в рамках ревизии каждый из четырех вице-президентов должен посетить с проверкой один из сборочных заводов компании. Сборочные заводы расположены в Лейпциге, Нанси, Льеже и Тилбурге. Президент решил начать с оценки затрат на командировки.
Специализация Затраты на командировку, тыс. $ вице-президентов
|
Лейпциг |
Нанси |
Льеж |
Тилбург |
|
|
|
|
|
|
|
Финансы |
24 |
10 |
21 |
11 |
|
|
|
|
|
|
|
Маркетинг |
14 |
22 |
10 |
15 |
|
|
|
|
|
|
|
Производство |
15 |
17 |
20 |
19 |
|
|
|
|
|
|
|
Персонал |
11 |
19 |
14 |
13 |
|
|
|
|
|
|
|
Необходимо назначить вице-президентов таким образом, чтобы суммар-
ные затраты на командировку были бы минимальны.
Решение: Составим экономико-математическую модель задачи.
70