Материал: 5462
31
7.Решить -задачу при следующих данных: ai = (65; 60; 50; 100) (час);
b j = (300; 400; 500; 600; 200) (шт); 5 5 10 20 15
|
5 |
2 |
5 |
10 |
10 |
(шт./час); |
|
|
1 |
10 |
20 |
20 |
20 |
||
|
|
||||||
|
5 |
20 |
10 |
20 |
10 |
|
|
|
7 |
10 |
16 |
10 |
10 |
|
|
C |
5 |
6 |
10 |
12 |
4 |
. |
|
10 |
20 |
12 |
15 |
5 |
|||
|
|
||||||
|
10 |
7 |
6 |
10 |
20 |
|
8. Решить -задачу при следующих данных: ai = (30; 50; 20);
b j = (500; 200; 400).
2 |
2,5 |
3 |
|
12 |
16 |
16 |
2,4 |
3 |
3,2 |
; |
C 10 |
12 |
20 . |
1,8 |
2 |
2,5 |
|
15 |
16 |
24 |
9.Найти оптимальную программу обработки трех изделий (А,Б,В) на двух взаимозаменяемых станках при следующих исходных данных
Станки |
Нормы времени час/шт. |
Фонд рабочего |
Себестоимость |
||||
|
|
|
|
времени (час) |
|
(руб./час) |
|
|
А |
Б |
В |
|
А |
Б |
В |
I |
2 |
5 |
3 |
200 |
3 |
2 |
4 |
II |
4 |
7 |
5 |
350 |
2,5 |
2 |
3 |
План |
80 |
30 |
10 |
Прибыль |
20 |
40 |
30 |
(шт.) |
|
|
|
(руб./шт.) |
|
|
|
Вкачестве критерия оптимальности выбрать
1)минимум себестоимости (производительность 1 );
2) |
минимум затрат времени работы станков |
ai |
; |
|
|||
3) |
максимум прибыли. |
|
|
32
10. Решить -задачу при следующих данных: ai = (150; 200; 300) (час);
b j = (300; 170; 250) (шт.);
4 |
2 |
3 |
|
|
2 |
8 |
5 |
5 |
3 |
2,5 |
(час/шт.); |
C |
3 |
7 |
6 |
3 |
2,4 |
4,2 |
|
|
2,5 |
9 |
7 |
Глава 3. Транспортная задача с запретами
При формулировании транспортных задач могут возникнуть дополнительные ограничения из-за состояния дорог, наличия транспортных средств, при перевозках неоднородного груза, при исследовании открытых моделей и при других обстоятельствах. Задача с запретами не всегда разрешима. Если для задачи можно найти первоначальный опорный план, то оптимальный план можно определить по методу потенциалов. Значение целевой функции в задаче с запретами увеличивается (при решении задачи на минимум) по сравнению с задачей без дополнительных условий.
Рассмотрим порядок решения задачи при выполнении следующих условий:
1) если по какому-то маршруту груз перевозить нельзя, то в соответствующей клетке таблицы тариф считаем бесконечно большим Сij M 
. Тогда характеристика этой клетки Eij Cij 
ui v j 0
всегда, условие оптимальности на всех этапах решения будет выполнено, и клетка до конца решения останется свободной;
2)если по заданному маршруту должно быть перевезено строго определенное количество груза, записываем его в клетку и во всех дальнейших расчетах считаем эту клетку свободной с бесконечно большим тарифом М. В контур она не включается, и зафиксированная в ней поставка остается до конца решения;
3)если по некоторому маршруту необходимо перевезти не менее указанного количества груза, то планируем минимальную перевозку отдельно и соответственно уменьшаем запасы и потребности пунктов, связанных данным маршрутом. Получившуюся новую задачу решаем обычным образом. Окончательная перевозка по рассматриваемому маршруту равна сумме перевозок, предварительно назначенной (минимальной) и полученной в результате решения.
Пример. Имеется четыре поставщика однородного груза с мощностями ai = (30; 17; 45; 40), шесть потребителей с потребностями b j = (40; 35; 15;
33
25; 55; 10) и матрица удельных транспортных затрат по перевозке единицы
3 7 5 4 1 9
груза С |
7 |
5 |
6 |
3 |
8 |
4 |
. Найти оптимальный план перевозок по |
|
6 |
4 |
3 |
2 |
8 |
5 |
|
|
3 |
1 |
4 |
2 |
7 |
3 |
|
данным задачи и при условиях:
1)по маршруту (2,4) груз перевозить нельзя;
2)по маршруту (3,5) перевезти не менее 25 ед. груза;
3)по маршруту (4,1) должно быть перевезено 13 ед. груза;
4)обязательно удовлетворить потребности четвертого и шестого потребителей.
Результаты решений сравнить.
Решение. Проверим условие баланса |
ai 132 ; |
b j 180 . Задача |
i |
|
j |
открытого типа. Для приведения задачи к закрытой введем фиктивного поставщика с мощностью a5 180 132 48. Сформируем таблицу
транспортной задачи, учитывая дополнительные условия для решения на компьютере. Запретительный тариф М заменяется заведомо большим положительным числом 100.
1.Так как по маршруту (2,4) груз перевозить нельзя, блокируем его запретительным тарифом М = 100.
2. |
Положим |
x35 |
25 и уменьшим на эту величину ресурсы третьего |
|||
|
поставщика |
a3 |
45 25 |
20 |
и потребности пятого потребителя |
|
|
b5 55 |
25 |
30 . Затраты |
по |
перевозке этого количества груза |
|
|
составят 25 8 |
200 (усл. ед.). |
|
|||
3. |
Положим |
x41 |
13. Уменьшим на эту величину запасы четвертого |
|||
|
поставщика и потребности первого потребителя и блокируем |
|||||
|
маршрут (4,1). Затраты по перевозке этого груза равны 13 5 65 |
|||||
|
(усл.ед.). |
|
|
|
|
|
4.Реального груза в задаче 132 ед., а потребность в нем составляет 180 ед. Для удовлетворения четвертого и шестого потребителей груза достаточно. Заблокируем перевозки фиктивного груза по маршрутам (5,4) и (5,6), остальные тарифы по перевозкам фиктивного груза принимаем равными нулю. В остальных клетках проставляем данные тарифы и получаем таблицу транспортной задачи
|
|
|
|
34 |
|
|
|
27 |
35 |
15 |
25 |
30 |
10 |
|
3 |
7 |
5 |
4 |
1 |
9 |
30 |
|
|
|
|
|
|
17 |
7 |
5 |
6 |
100 |
8 |
4 |
|
|
|
|
|
|
|
20 |
6 |
4 |
3 |
2 |
8 |
5 |
|
|
|
|
|
|
|
27 |
100 |
1 |
4 |
2 |
7 |
3 |
|
|
|
|
|
|
|
48 |
0 |
0 |
0 |
100 |
0 |
100 |
|
|
|
|
|
|
Решаем задачу. Получаем оптимальное решение с дополнительными условиями.
|
27 |
35 |
15 |
25 |
30 |
10 |
|
|
3 |
7 |
5 |
4 |
1 |
9 |
|
30 |
|
|
|
0 |
30 |
|
u1=0 |
|
|
|
|
|
|
|
|
17 |
7 |
5 |
6 |
100 |
8 |
4 |
u2=2 |
|
7 |
|
|
|
10 |
||
|
|
|
|
|
|
||
20 |
6 |
4 |
3 |
2 |
8 |
5 |
|
|
|
|
20 |
|
|
u3=-2 |
|
|
|
|
|
|
|
||
27 |
100 |
1 |
4 |
2 |
7 |
3 |
u4=-2 |
|
22 |
|
5 |
|
|
||
|
|
|
|
|
|
||
48 |
0 |
0 |
0 |
100 |
0 |
100 |
u5=-3 |
27 |
6 |
15 |
|
|
|
||
|
|
|
|
|
|||
|
v1=3 |
v2=3 |
v3= |
v4=4 |
v5=1 |
v6=2 |
|
Zmin = 177. С учетом необходимых перевозок x35 25 и x13 13 минимальные затраты составят Zmin1 177 200 65 442 .
35
Оптимальное решение задачи без дополнительных условий
|
27 |
35 |
15 |
25 |
30 |
10 |
|
|
|
3 |
7 |
5 |
4 |
1 |
|
9 |
|
30 |
0 |
|
|
|
30 |
|
|
u1=3 |
17 |
7 |
5 |
6 |
3 |
8 |
|
4 |
u2=4 |
|
|
|
7 |
|
10 |
|
||
|
|
|
|
|
|
|
||
20 |
6 |
4 |
3 |
2 |
8 |
|
5 |
|
|
|
2 |
18 |
|
|
|
u3=3 |
|
|
|
|
|
|
|
|||
27 |
3 |
1 |
4 |
2 |
7 |
|
3 |
u4=1 |
|
27 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
48 |
0 |
0 |
0 |
0 |
0 |
|
0 |
u5=0 |
27 |
8 |
13 |
|
|
|
|
||
|
|
|
|
|
|
|||
|
v1=0 |
v2=0 |
v3=0 |
v4=-1 |
v5=-2 |
v6=0 |
|
|
Zmin = 160
Минимальные затраты для задачи с дополнительными условиями выше на 282, что составляет 176,25%.
Вопросы для самопроверки
1.В каких случаях возникают задачи с запретами?
2.Почему клетка с запретительным тарифом до конца решения остается свободной?
3.Что происходит со значениями целевой функции Z при различных дополнительных условиях задачи?
4.Как реализуются условия, что по некоторому маршруту необходимо провезти строго определенное количество груза или не менее указанного количества при решении задачи вручную и на компьютере?
5.В каких случаях при решении открытых моделей могут возникнуть запреты на перевозки и как они реализуются?