5463
.pdf41
|
|
|
|
План Х2 |
|
|
|
|
|
Таблица 4 |
||
|
63 |
34 |
43 |
|
50 |
65 |
|
70 |
||||
|
|
|
1,5 |
|
3 |
2,5 |
1 |
+ |
|
2 |
1,8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
75 |
|
|
|
|
|
|
|
50 |
|
|
|
25 |
|
|
|
|
|
|
|
|
|
|
|||
100 |
|
|
1 |
|
3,5 |
2 |
3 |
|
|
4 |
1 |
|
55 |
|
|
|
|
|
|
|
|
|
|
45 |
|
|
|
|
|
|
|
|
|
|
|
|
||
150 |
|
|
1,2 |
|
2 |
2,2 |
2,5 |
|
|
2,5 |
3 |
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
+ |
34 |
43 |
|
|
65 |
|
|
|||
|
|
|
|
|
|
|||||||
Для плана Х2 T2 |
max tij |
t35 |
2,5. |
|
|
|
|
Для нового плана Х2 проводим аналогичную итерацию, т.е. повторяем действия 2,3,4.
По маршруту (3,5)-(3,1)-(2,1)-(2,6)-(1,6)-(1,5) перемещаем поставку min 25;65;55 25 (план Х3, табл. 5), что не оказывает влияния на общую продолжительность реализации плана перевозок. Все другие маршруты, исходящие из 3-й клетки (3,5), имеют пустую клетку со знаком «минус», поэтому полная разгрузка клетки (3,5) невозможна. Следовательно, T minTk min 3;2,5 2,5 (час).
Легко видеть, что планов со временем реализации Т = 2,5 можно построить несколько. Для этого не нужно вычеркивать клетки с tij 2,5 . Рассмотрим
план Х3 (табл. 5) и план Х4 (табл. 6), который используем в следующей задаче.
|
|
|
План Х3 |
|
|
|
|
Таблица 5 |
|
63 |
34 |
43 |
50 |
65 |
70 |
||
|
1,5 |
|
2,5 |
1 |
2 |
1,8 |
||
75 |
|
|
|
50 |
25 |
|
||
100 |
1 |
|
2 |
|
|
|
|
1 |
30 |
|
|
|
|
|
|
70 |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
150 |
1,2 |
2 |
2,2 |
|
2,5 |
|
2,5 |
|
33 |
34 |
43 |
|
|
40 |
|
||
|
|
|
|
42
|
План Х4 |
|
|
|
Таблица 6 |
|
|
63 |
34 |
43 |
50 |
65 |
70 |
|
1,5 |
|
2,5 |
1 |
2 |
1,8 |
75 |
|
|
|
10 |
65 |
|
100 |
1 |
|
2 |
|
|
1 |
30 |
|
|
|
|
70 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
150 |
1,2 |
2 |
2,2 |
2,5 |
2,5 |
|
33 |
34 |
43 |
40 |
|
|
|
|
|
|
Вопросы для самопроверки
1.В чем смысл транспортной задачи по критерию минимума времени?
2.Чем отличается маршрут от контура?
3.Как определяется время реализации полученного плана перевозок?
4.Считают ли в этой задаче число занятых клеток в таблице и почему?
5. Почему в таблице зачеркивают клетки, для которых tij tплан ?
6.Чем отличается опорный план от допустимого, и какой план находится в задаче по критерию минимума времени?
Задачи для самостоятельного решения
Найти два плана, для которых выполняется минимальное время реализации при следующих данных:
|
|
|
3 |
1 |
2 |
1,8 |
2,5 |
1,5 |
1. ai |
(85; 105; 155); |
T |
3,5 |
3 |
4 |
1 |
2 |
1 |
|
|
|
2 |
2,5 |
2,5 |
3 |
2,2 |
1,2 |
b j |
(75; 80; 35; 48; 52; 55). |
|
|
|
|
|
|
|
|
|
|
1 |
2 |
1,8 |
1,5 |
3 |
1,5 |
2. ai |
(47; 63; 120); |
T |
3 |
4 |
1 |
1 |
3,5 |
2 |
|
|
|
2,5 |
2,5 |
3 |
1,2 |
2 |
2,2 |
b j |
(60; 54; 26; 40; 28; 22). |
|
|
|
|
|
|
|
|
|
|
43 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1,5 |
1,8 |
|
3 |
2,5 |
1 |
|
2 |
||
3. |
ai |
(87; 53; 60); |
T |
1 |
|
1 |
3,5 |
2 |
|
3 |
|
4 |
|
|
|
|
|
1,2 |
|
3 |
|
2 |
2,2 |
2,5 |
|
2,5 |
|
|
b j |
(54; 46; 32; 28; 19; 21). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
2,5 |
|
1 |
1,5 |
1,8 |
|
2 |
||
4. |
ai |
(125; 75; 50); |
T |
3,5 |
|
2 |
|
3 |
1 |
|
1 |
|
1 |
|
|
|
|
2 |
2,2 |
2,5 |
1,2 |
|
3 |
2,5 |
|||
|
b j |
(70; 55; 40; 45; 25; 15). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1,8 |
|
2 |
|
1 |
2,5 |
3 |
|
1,5 |
|
5. |
ai |
(62; 37; 91); |
T |
1 |
|
4 |
|
3 |
2 |
|
3,5 |
|
1 |
|
|
|
|
3 |
2,5 |
2,5 |
2,2 |
2 |
|
1,2 |
|||
|
b j |
(35; 45; 50; 36; 10; 14). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
1,8 |
|
2,5 |
3 |
1,5 |
|
1 |
|
6. |
ai |
(83; 47; 63); |
T |
4 |
|
1 |
|
2 |
3,5 |
1 |
|
3 |
|
|
|
|
|
2,5 |
|
3 |
|
2,2 |
2 |
1,2 |
|
2,5 |
|
|
b j |
(35; 45; 60; 20; 20; 13). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2,5 |
|
1 |
|
2 |
1,8 |
1,5 |
3 |
||
7. |
ai |
(34; 86; 70); |
T |
2 |
|
3 |
|
4 |
1 |
1 |
|
3,5 |
|
|
|
|
|
2,2 |
|
2,5 |
|
2,5 |
3 |
1,2 |
2 |
||
|
b j |
(55; 45; 32; 28; 14; 16). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1,8 |
|
1,5 |
|
3 |
2 |
2,5 |
1 |
||
8. |
ai |
(69; 71; 82); |
T |
1 |
|
1 |
|
3,5 |
4 |
2 |
3 |
||
|
|
|
|
3 |
|
1,2 |
|
2 |
2,5 |
2,2 |
2,5 |
||
|
b j |
(57; 33; 42; 34; 29; 27). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1,8 |
2 |
|
2,5 |
1 |
|
3 |
1,5 |
||
9. |
ai |
(77; 63; 84); |
T |
1 |
|
4 |
|
2 |
|
3 |
3,5 1 |
||
|
|
|
|
3 |
|
2,5 |
2,2 |
2,5 |
2 |
1,2 |
|||
|
b j |
(52; 38; 26; 55; 26; 27). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
1,5 |
2 |
1 |
2 |
1,8 |
|||
10. ai |
(96; 104; 58); |
T |
3,5 |
1 |
|
4 |
3 |
1 |
|
1 |
|||
|
|
|
|
2 |
|
1,2 |
5 |
2,5 |
3 |
1,6 |
|||
|
b j |
(51; 39; 76; 22; 34; 36). |
|
|
|
|
|
|
|
|
|
|
|
44
Глава 5. Транспортные задачи с учетом времени и издержек
Решение транспортных задач по критерию минимума времени оправдано лишь в особых случаях в связи с высокими затратами на их реализацию. Возможность существования нескольких планов, минимизирующих время, позволяет выбрать из них планы с наименьшими издержками.
Наряду с матрицей времени T tij используется матрица издержек C cij . По методу потенциалов определяется план Хс, минимизирующий издержки Zmin . Определяется продолжительность его реализации Тс. Если
такая продолжительность удовлетворительна в данной ситуации, то распределение следует считать наименьшим. Если же необходимо уложиться в более короткий срок Тк, то используют планы меньшей продолжительности и определяют затраты для их реализации.
Среди всех планов, которые входят во время Тк, найти план с относительно меньшими издержками, сохраняя запреты на клетки, для которых tij Tk . Осуществляют перераспределение грузов, снимая их с
«дорогих» коммуникаций и перебрасывая их на «дешевые» по замкнутым маршрутам. Так при перемещении по маршруту издержки изменяются на величину
Z Ci1 j1 Ci1 j2 |
Ci2 j2 Ci2 j1 |
Ci1 j1 Ci2 j2 Ci1 j2 Ci2 j1 |
||
(i1, j1) |
|
|
(i1, j2 ) |
|
|
|
|
|
|
|
- |
+ |
|
|
(i2 , j1) |
+ |
- |
(i2 , j2 ) |
|
|
|
|
Если выражение положительно, то его величина характеризует выигрыш в суммарных затратах, если отрицательно, то – удорожание стоимости перевозок.
Пример. Среди найденных планов наименьшего времени реализации по условию примера предыдущей главы найти план с относительно наименьшими издержками при заданной матрице издержек
|
6 |
3 |
4 |
7,5 |
5 |
5,5 |
С |
8 |
2,2 |
5,5 |
3 |
2 |
7,5 . |
|
7 |
6 |
5,8 |
4,2 |
4,3 |
3,2 |
Оценить выигрыш во времени и потери в издержках относительно Zmin .
Решение. Определяем план Хс, минимизирующий издержки, по методу потенциалов. Записывая tij в верхнем правом углу клеток, а Cij – в
нижнем правом (табл. 7)
45
(При реализации на компьютере внести информацию по ai ,bj и cij без
учета tij ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
План Хс |
|
|
|
|
|
|
|
Таблица 7 |
|
63 |
|
34 |
43 |
50 |
|
65 |
|
|
70 |
||
|
|
1,5 |
3 |
2,5 |
|
|
1 |
|
2 |
|
1,8 |
|
75 |
32 |
|
43 |
|
7,5 |
|
|
|
5,5 |
|||
|
|
6 |
3 |
4 |
|
5 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|||
|
|
1 |
3 |
2 |
|
|
3 |
|
4 |
|
1 |
|
100 |
|
|
34 |
|
1 |
|
|
65 |
|
|
|
|
|
|
8 |
|
2,2 |
5,5 |
|
|
3 |
2 |
|
7,5 |
|
|
|
|
|
|
|
|
||||||
|
|
1,2 |
2 |
2,2 |
|
|
2,5 |
|
2,5 |
|
3 |
|
150 |
33 |
49 |
|
|
70 |
|||||||
|
7 |
6 |
5,8 |
|
4,2 |
|
4,3 |
|
3,2 |
|||
|
|
|
|
|
||||||||
Определяем Тс max tij |
t25 |
4 (час); Zmin |
1218,6 руб. |
Для определения плана наименьшего по времени с относительно наименьшими издержками решим задачу с запретами на клетки, для которых tij 2,5 , заблокировав их запретительными тарифами M 100.
Данные для решения задачи на компьютере предоставлены в таблице
|
63 |
34 |
43 |
50 |
65 |
70 |
|
6 |
|
4 |
7,5 |
5 |
5,5 |
75 |
62 |
|
|
|
|
13 |
100 |
8 |
|
5,5 |
|
|
7,5 |
|
|
43 |
|
|
57 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
150 |
7 |
6 |
5,8 |
4,2 |
4,3 |
|
1 |
34 |
|
50 |
65 |
|
|
|
|
|
Получаем оптимальное решение задачи t 2,5 (час) Z 1808
Дополнительные издержки
Z Z Zmin 589,4
|
|
|
|
46 |
|
|
|
|
|
|
Выигрыш во времени составляет |
T |
1,5 100% |
37,5% |
, потери в |
||||||
|
|
|
||||||||
Tc |
4 |
|||||||||
|
|
|
|
|
|
|
||||
издержках – |
Z |
589,4 100% |
48,37% . |
|
|
|
|
|||
|
|
|
|
|
|
|
||||
Zmin |
1218,6 |
|
|
|
|
Вопросы для самопроверки
1.Почему возникает потребность в решении задач с учетом времени и издержек?
2.В каком случае удается снизить затраты при фиксированном минимальном времени реализации плана?
3.Как оценить потери в издержках и выигрыш во времени планов с Tmin
и Zmin ?
4. Как вычислить изменения в издержках Z при переброске груза по замкнутому маршруту?
Задачи для самостоятельного решения
Среди планов, наименьших по времени реализации, найти план с наименьшими издержками при заданной матрице С. Оценить выигрыш во времени и потери в издержках относительно Zmin .
Данные по мощностям поставщиков ai , потребностям потребителей b j и матрице Т даны в предыдущей главе
|
|
3 |
7,5 |
5 |
5,5 |
4 |
6 |
|
|
7,5 |
5 |
5,5 |
6 |
3 |
4 |
1. |
C |
2,2 |
3 |
2 |
7,5 |
5,5 |
8 . |
2. |
C |
3 |
2 |
7,5 |
8 |
2,2 |
5,5 . |
|
|
6 |
4,2 |
4,3 |
3,2 |
5,8 |
7 |
|
|
4,2 |
4,3 |
3,2 |
7 |
6 |
5,8 |
|
|
6 |
5,5 |
3 |
4 |
7,5 |
5 |
|
|
3 |
4 |
7,5 |
5,5 |
6 |
5 |
3. |
C |
8 |
7,5 |
2,2 |
5,5 |
3 |
2 . |
4. |
C |
2,2 |
5,5 |
3 |
7,5 |
8 |
2 . |
|
|
7 |
3,2 |
6 |
5,8 |
4,2 |
4,3 |
|
|
6 |
5,8 |
4,2 |
3,2 |
3 |
4,3 |
|
|
5,5 |
5 |
7,5 |
4 |
3 |
6 |
|
|
5 |
5,5 |
4 |
3 |
6 |
7,5 |
5. |
C |
7,5 |
2 |
3 |
5,5 |
2,2 |
8 . |
6. |
C |
2 |
7,5 |
5,5 |
2,2 |
8 |
3 . |
|
|
3,2 |
4,3 |
4,2 |
5,8 |
6 |
7 |
|
|
4,3 |
3,2 |
5,8 |
6 |
7 |
4,2 |
|
|
|
|
|
|
|
|
47 |
|
|
|
|
|
|
|
|
|
4 |
7,5 |
5 |
5,5 |
6 |
3 |
|
5,5 |
6 |
|
3 |
5 |
4 |
7,5 |
7. |
C |
5,5 |
3 |
2 |
7,5 |
8 |
2,2 . |
8. C |
7,5 |
8 |
|
2,2 |
2 |
5,5 |
3 . |
|
|
5,8 |
4,2 |
4,3 |
3,2 |
7 |
6 |
|
3,2 |
7 |
|
6 |
4,3 |
5,8 |
4,2 |
|
|
5,5 |
5 |
4 |
7,5 |
3 |
6 |
|
3 |
|
6 |
5 |
7,5 |
5,7 |
4,1 |
9. |
C |
7,5 |
2 |
5,5 |
3 |
2,2 |
8 . |
10. C |
2,2 |
|
8 |
2 |
3 |
7,5 |
5,6 . |
|
|
3,2 |
4,3 |
5,8 |
4,2 |
6 |
7 |
|
6 |
|
7 |
9 |
4,2 |
3,2 |
5,9 |
Глава 6. Транспортные задачи по перевозке неоднородного взаимозаменяемого груза
Задачи, связанные с перевозками однородного груза, имеют сравнительно ограниченное практическое применение. Значительно чаще приходится встречаться с перевозками неоднородного груза (планирование перевозок различного вида топлива, цемента разных марок, сортового железа и т.д.).
Характерной особенностью этих задач является условие взаимозаменяемости разных сортов груза при удовлетворении потребностей, т.е. некоторая часть потребностей может быть удовлетворена различными видами имеющегося в наличии груза, но в различных количествах, с учетом свойств каждого вида груза и характера потребностей.
Пусть имеется два поставщика A1 и A2 и два потребителя B1 и B2 . Обозначим через a1I и a1II ресурсы первого поставщика по I и II-у сорту груза соответственно. Аналогично для второго поставщика – a2I и a2II .
Таким образом, в дальнейшем будем рассматривать как бы четыре поставщика с ресурсами a1I , a1II , a2I , a2II .
Потребности у каждого потребителя могут быть трех видов:
1)потребности только на I-й сорт груза b1I ,b2I ;
2)потребности только на II-й сорт груза b1II ,b2II ;
3) |
взаимозаменяемые |
потребности |
на любой |
из |
двух |
сортов |
груза |
||
bIII ,bIII . |
|
|
|
|
|
|
|
||
1 |
2 |
|
|
|
|
|
|
|
|
bIII ,bIII |
– потребности |
первого и |
второго потребителя, |
выраженные, |
|||||
1 |
2 |
|
|
|
|
|
|
|
|
например, в единицах I-го сорта. |
|
|
|
|
|
|
|||
|
В дальнейшем вместо каждого из потребителей В1 |
и |
В2 |
будем |
|||||
рассматривать три потребителя с потребностями bI ,bII ,bIII , |
bI ,bII ,bIII . |
||||||||
|
|
|
|
1 |
1 |
1 |
2 |
2 |
2 |
|
|
|
|
|
|
|
|
|
|
48 |
|
|
|
|
|
|
|
|
|
|
||
Дана матрица удельных транспортных издержек |
|
C |
C11 |
|
C12 |
|
|
|
||||||||||||||
|
C21 |
|
C22 |
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
bj |
|
|
B1 |
|
|
|
|
|
B2 |
|
|
|
|
|
|
||
|
|
|
|
ai |
|
|
|
I |
II |
|
III |
I |
|
|
II |
III |
|
|
|
|
||
|
|
|
|
|
|
|
|
b1 |
b1 |
|
b1 |
b2 |
|
|
b2 |
b2 |
|
|
|
|
|
|
|
|
|
|
|
а I |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
A1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a II |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A2 |
a2I |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
a2II |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Cij |
характеризует затраты на перевозку 1 ед. груза из пункта |
Ai |
в пункт |
|||||||||||||||||||
B j . Коэффициенты затрат не зависят от сорта перевозимого груза, а |
||||||||||||||||||||||
определяются только тем, откуда и куда он перевозится. Известно, что р |
||||||||||||||||||||||
ед. груза I-го сорта могут быть заменены q единицами II-го сорта. Тогда |
||||||||||||||||||||||
данные |
задачи можно |
выразить в |
единицах |
|
груза |
первого |
сорта |
или |
||||||||||||||
второго при помощи коэффициента взаимозаменяемости |
|
q |
(в I-й |
|||||||||||||||||||
I |
p |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
сорт) или |
II |
p |
(во II-й сорт). |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
I |
показывает, сколько единиц груза I сорта могут заменить одну единицу |
|||||||||||||||||||||
груза II-го сорта. Аналогичный смысл имеет коэффициент |
|
II . |
|
|
|
|||||||||||||||||
|
Поскольку в условии задачи взаимозаменяемая потребность выражена |
|||||||||||||||||||||
в единицах I-го сорта, сведем данные задачи к этому сорта груза. Тогда |
||||||||||||||||||||||
ресурсы |
|
a II |
и |
a II |
эквивалентны |
1 |
a II |
и |
1 |
a II |
соответственно. |
|||||||||||
|
|
|
1 |
|
2 |
|
|
|
|
|
1 |
|
|
2 |
|
|
|
|
|
|||
Аналогично, |
потребности |
b II , |
b II |
эквивалентны соответственно |
1 |
b II , |
||||||||||||||||
|
|
|
|
|
|
|
|
1 |
2 |
|
|
|
|
|
|
|
|
|
|
1 |
||
1 |
b II единиц груза I сорта. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Так как затраты связаны с перевозками реального груза и зависят от |
|||||||||||||||||||||
реального веса, а не от потребительских свойств, то, увеличив |
||||||||||||||||||||||
искусственно ресурсы II сорта в |
I |
раз, необходимо соответственно в этих |
||||||||||||||||||||
строках |
уменьшить |
в |
I |
раз |
коэффициенты |
|
затрат. Наконец, |
следует |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
предусмотреть, чтобы потребности в I и II сортах груза удовлетворялись |
||||||||||||||||||||||
только определенным допустимым сортом груза. Для этого производится |
||||||||||||||||||||||
блокирование недопустимых перевозок с помощью запретительных |
||||||||||||||||||||||
тарифов М. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
Учитывая вышесказанное, все задачи можно представить в однородном |
|||||||||||||||||||||
условном грузе в таблице. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
49
|
bj |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ai |
|
|
b I |
|
b II |
b III |
b I |
|
b II |
b III |
||||||
|
1 |
1 1 |
|
1 |
|
2 |
1 2 |
2 |
|
|
||||||
a I |
|
C11 |
|
|
M |
|
C11 |
C12 |
|
M |
|
C12 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a II |
|
M |
|
|
С11 |
|
C11 |
M |
|
C12 |
|
C12 |
|||
|
|
|
|
|
|
|
||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
1 |
|
|
1 |
1 |
|
|
1 |
1 |
|
|||||||
|
|
|
|
|
|
|
||||||||||
a2I |
|
C21 |
|
|
M |
|
C21 |
C22 |
|
M |
|
C22 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
a2II |
|
M |
|
С21 |
|
|
C21 |
|
M |
|
С21 |
|
C21 |
|
|
1 |
|
|
1 |
|
1 |
|
|
1 |
1 |
|
||||||
|
|
|
|
|
|
|
|
Получим задачу с запретами.
Условие баланса a I |
a I |
1 |
a II |
a II |
bI |
bI |
1 |
bI |
1 |
2 |
1 |
2 |
1 |
2 |
1 |
Этого условия недостаточно для разрешимости задачи. Очевидно, запасы грузов I и II сорта должны потребностей в этих сортах
b2II .
быть не меньше
a I |
a I |
bI |
bI ; |
1 |
2 |
1 |
2 |
a II |
a II |
bII |
bII . |
1 |
2 |
1 |
2 |
Пример. Найти оптимальный план перевозок угля двух сортов (I – бурый уголь и II – антрацит) из двух складов ( А1 и А2 ) двум потребителям ( В1 и
В2 ). Исходные данные задачи приведены в таблице, где указаны запасы
угля I сорта (300 и 100 т) и II сорта (100 и 140 т); потребности в угле I сорта (100 и 200 т), II сорта (60 и 40 т) и взаимозаменяемые потребности (220 и 90 т) в единицах I сорта. Известно, что при удовлетворении взаимозаменяемых потребностей три единицы I сорта можно заменить
двумя единицами II сорта. Следовательно, 1 32 . В таблице указаны
удельные транспортные затраты C |
30 |
21 |
, которые могут |
|
15 |
24 |
|
приниматься пропорциональными расстояниям между соответствующими поставщиками и потребителями (без учета тарифов на перевозки)
|
|
|
|
50 |
|
|
|
Исходные данные задачи |
|
|
|
||||
|
bj |
|
B1 |
|
|
B2 |
|
ai |
|
100 |
60 |
220(I) |
200 |
40 |
90(I) |
|
300 |
|
|
|
|
|
|
A1 |
100 |
|
30 |
|
|
21 |
|
|
100 |
|
|
|
|
|
|
A2 |
140 |
|
15 |
|
|
24 |
|
Пересчитаем данные таблицы в единицах I сорта (бурый уголь) с помощью
коэффициента взаимозаменяемости |
|
|
3 |
. Получаем таблицу |
|||||||||||||||
1 |
2 |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bj |
|
|
|
В1 |
|
|
|
|
|
|
|
В2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
ai |
|
|
|
100 |
90 |
|
220 |
|
200 |
|
60 |
|
90 |
|||||
|
|
|
|
|
|
|
30 |
M |
|
30 |
|
|
|
|
21 |
|
M |
21 |
|
|
|
300 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
А1 |
|
|
|
|
|
M |
20 |
|
20 |
|
|
|
|
M |
|
14 |
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
150 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
15 |
M |
|
15 |
|
|
|
|
24 |
|
M |
25 |
|
|
|
|
100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
А2 |
|
|
|
|
|
M |
10 |
|
10 |
|
|
|
|
M |
|
16 |
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
210 |
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
В задаче выполняется условие баланса |
|
|
|
|
|
|
|
||||||||||||
300 |
150 |
100 |
210 |
100 |
90 |
220 |
200 |
90 |
60 |
760. |
|
Кроме того, выполняются условия удовлетворения потребностей в определенных сортах груза
300 100 100 200; 150 210 90 60 .
Следовательно, задача разрешима. Решаем полученную задачу с запретами, получаем условно-оптимальный план