2015-05-14
364Лабораторная работа № 14
По аналогии с заданием № 6 необходимо решить задачу связи пунктов отправления 
и назначения 
, обеспечив вывоз всех грузов из пунктов отправления, ввоз во все пункты назначения требуемых объемов грузов при минимальных суммарных транспортных издержках. При этом транспортная задача решается методом потенциалов.
Инструкция по выполнению.
Сбалансированная задача
Рассмотрим сбалансированную задачу из задания № 6 (очевидно, что математическая модель задачи соответствует ранее составленной на с.88).
| Bj Ai | B1=60 | B2=100 | B3=40 | |||
| A1=100 | ||||||
| A2=50 | ||||||
| A3=50 | ||||||
Методом северо-западного угла составляется первоначальный план перевозок и проверяется на оптимальность.
| Bj Ai | B1=60 | B2=100 | B3=40 | Ui | |||
| A1=100 |  60
| - | |||||
| A2=50 | - | - | |||||
| A3=50 | - | ||||||
| Vj | -3 | -4 |
Расставляются потенциалы и определяются потенциальные оценки свободных клеток (т.е. разности между суммой потенциалов и себестоимостью перевозок в свободной клетке):
|
|
|
; 
;
; 
.
План перевозок не оптимален, поскольку имеются положительные потенциальные оценки, а значение целевой функции
может быть улучшено (здесь и далее размерность значения целевой функции – единицы транспортных издержек).
Выбор цикла с включением в качестве вершины клетки (3,1) с потенциальной оценкой +8 позволяет перераспределить перевозки с помощью цикла пересчета:
и получить новый план перевозок в виде очередной таблицы. При перераспределении соблюдаются строчные и столбцовые балансы («цены» ребер). Например, перемещение перевозки 60 невозможно, так как цена нижнего ребра 10.
| Bj Ai | B1=60 | B2=100 | B3=40 | Ui | |||
| A1=100 |  50
| - | |||||
| A2=50 | - | - | |||||
| A3=50 | - | ||||||
| Vj | -3 |
Полученный план также не оптимален, так как среди потенциальных оценок свободных клеток есть положительные:
; ;
; 
.
При этом значение целевой функции
улучшилось.
Далее осуществляются очередные шаги оптимизации плана перевозок с помощью метода потенциалов.
Для преобразований выбирается цикл с клеткой (1,3) с потенциальной оценкой 
.
| Bj Ai | B1=60 | B2=100 | B3=40 | Ui | |||
| A1=100 |  10
| ||||||
| A2=50 | - | - | |||||
| A3=50 | - | - | |||||
| Vj | -3 | -5 |
; 
;
; 
;
.
Для преобразований выбирается цикл с клеткой (2,1) с потенциальной оценкой 
.
| Bj Ai | B1=60 | B2=100 | B3=40 | Ui | |||
| A1=100 | - | ||||||
| A2=50 | - | ||||||
| A3=50 | - | - | |||||
| Vj |
; 
;
|
|
|
; 
;
.
Таким образом, получен оптимальный план перевозок.
Фиктивный поставщик
Условия задачи сведены в таблицу.
| Bj Ai | B1=60 | B2=100 | B3=40 | |||
| A1=100 | ||||||
| A2=50 | ||||||
Согласно условиям (см. таблицу) выполняются соотношения:
; 
; 
.
Поскольку величина запасов меньше величины потребностей, то в условия вводится «фиктивный» поставщик с недостающим запасом в 50 единиц груза. При этом себестоимость перевозок от него ко всем потребителям устанавливается на уровне максимальной из имеющихся возможных.
| Bj Ai | B1=60 | B2=100 | B3=40 | |||
| A1=100 | ||||||
| A2=50 | ||||||
| A3=50 | ||||||
Методом северо-западного угла, составляется первоначальный план перевозок и проверяется на оптимальность.
| Bj Ai | B1=60 | B2=100 | B3=40 | Ui | |||
| A1=100 | - | ||||||
| A2=50 | - | - | |||||
| A3=50 | - | ||||||
| Vj | -3 | -3 |
; ;
; 
;
.
При подсчете целевой функции учитываются только реальные перевозки (без учета «фиктивного» поставщика).
План перевозок не оптимален. Далее осуществляются шаги метода потенциалов до получения оптимального плана перевозок по аналогии с приведенными в сбалансированном варианте транспортной задачи.
Фиктивный потребитель
Условия задачи сведены в таблицу.
| Bj Ai | B1=60 | B2=100 | ||
| A1=100 | ||||
| A2=50 | ||||
| A3=50 | ||||
Согласно условиям (см. таблицу) выполняются соотношения:
; 
; 
.
Поскольку величина запасов меньше величины потребностей, то в условия вводится «фиктивный» потребитель с недостающими потребностями в 40 единиц груза. При этом себестоимость перевозок к нему от всех потребителей устанавливается на уровне максимальной из имеющихся возможных.
| Bj Ai | B1=60 | B2=100 | B3=40 | |||
| A1=100 | ||||||
| A2=50 | ||||||
| A3=50 | ||||||
Методом северо-западного угла, составляется первоначальный план перевозок и проверяется на оптимальность.
| Bj Ai | B1=60 | B2=100 | B3=40 | Ui | |||
| A1=100 | - | ||||||
| A2=50 | - | - | |||||
| A3=50 | - | ||||||
| Vj | -3 | -1 |
; ;
; ;
.
При подсчете целевой функции учитываются только реальные перевозки (без учета «фиктивного» потребителя).
План перевозок не оптимален. Далее осуществляются шаги метода потенциалов до получения оптимального плана перевозок по аналогии с приведенными выше.
Исходные данные к транспортной задаче.
Вариант № 1
| Bj Ai | B1=100 | B2=60 | B3=40 | |||
| A1=75 | ||||||
| A2=75 | ||||||
Вариант № 2
| Bj Ai | B1=100 | B2=110 | ||
| A1=120 | ||||
| A2=130 | ||||
| A3=50 | ||||
Вариант № 3
| Bj Ai | B1=100 | B2=160 | B3=40 | |||
| A1=175 | ||||||
| A2=75 | ||||||
Вариант № 4
| Bj Ai | B1=100 | B2=60 | ||
| A1=75 | ||||
| A2=75 | ||||
| A3=100 | ||||
Вариант № 5
| Bj Ai | B1=60 | B2=100 | B3=140 | |||
| A1=100 | ||||||
| A2=150 | ||||||
Вариант № 6
| Bj Ai | B1=120 | B2=90 | ||
| A1=75 | ||||
| A2=125 | ||||
| A3=50 | ||||
Вариант № 7
| Bj Ai | B1=80 | B2=60 | B3=60 | |||
| A1=75 | ||||||
| A2=75 | ||||||
Вариант № 8
|
|
|
| Bj Ai | B1=150 | B2=60 | ||
| A1=170 | ||||
| A2=130 | ||||
| A3=50 | ||||
Вариант № 9
| Bj Ai | B1=60 | B2=40 | B3=200 | |||
| A1=80 | ||||||
| A2=100 | ||||||
Вариант № 10
| Bj Ai | B1=100 | B2=160 | ||
| A1=150 | ||||
| A2=150 | ||||
| A3=100 | ||||
Вариант № 11
| Bj Ai | B1=100 | B2=160 | B3=140 | |||
| A1=175 | ||||||
| A2=125 | ||||||
Вариант № 12
| Bj Ai | B1=100 | B2=160 | ||
| A1=75 | ||||
| A2=175 | ||||
| A3=250 | ||||
Вариант № 13
| Bj Ai | B1=150 | B2=60 | B3=90 | |||
| A1=100 | ||||||
| A2=100 | ||||||
Вариант № 14
| Bj Ai | B1=200 | B2=160 | ||
| A1=150 | ||||
| A2=150 | ||||
| A3=250 | ||||
Вариант № 15
| Bj Ai | B1=120 | B2=70 | B3=100 | |||
| A1=80 | ||||||
| A2=90 | ||||||
Вариант № 16
| Bj Ai | B1=100 | B2=160 | ||
| A1=150 | ||||
| A2=150 | ||||
| A3=150 | ||||
Вариант № 17
| Bj Ai | B1=100 | B2=80 | B3=70 | |||
| A1=70 | ||||||
| A2=130 | ||||||
Вариант № 18
| Bj Ai | B1=100 | B2=60 | ||
| A1=80 | ||||
| A2=100 | ||||
| A3=50 | ||||
Вариант № 19
| Bj Ai | B1=100 | B2=90 | B3=100 | |||
| A1=110 | ||||||
| A2=100 | ||||||
Вариант № 20
| Bj Ai | B1=100 | B2=60 | ||
| A1=50 | ||||
| A2=100 | ||||
| A3=120 | ||||
Вариант № 21
| Bj Ai | B1=200 | B2=100 | B3=140 | |||
| A1=110 | ||||||
| A2=280 | ||||||
Вариант № 22
| Bj Ai | B1=100 | B2=160 | ||
| A1=250 | ||||
| A2=100 | ||||
| A3=50 | ||||
Вариант № 23
| Bj Ai | B1=150 | B2=60 | B3=40 | |||
| A1=120 | ||||||
| A2=80 | ||||||
Вариант № 24
|
|
|
| Bj Ai | B1=90 | B2=100 | ||
| A1=100 | ||||
| A2=80 | ||||
| A3=80 | ||||
Вариант № 25
| Bj Ai | B1=160 | B2=50 | B3=50 | |||
| A1=70 | ||||||
| A2=130 | ||||||
Вариант № 26
| Bj Ai | B1=90 | B2=140 | ||
| A1=80 | ||||
| A2=80 | ||||
| A3=170 | ||||
Вариант № 27
| Bj Ai | B1=135 | B2=95 | B3=80 | |||
| A1=50 | ||||||
| A2=100 | ||||||
Вариант № 28
| Bj Ai | B1=130 | B2=60 | ||
| A1=70 | ||||
| A2=100 | ||||
| A3=60 | ||||
Вариант № 29
| Bj Ai | B1=100 | B2=80 | B3=40 | |||
| A1=70 | ||||||
| A2=100 | ||||||
Вариант № 30
| Bj Ai | B1=100 | B2=60 | ||
| A1=70 | ||||
| A2=100 | ||||
| A3=70 | ||||
Вариант № 31
| Bj Ai | B1=110 | B2=60 | B3=140 | |||
| A1=80 | ||||||
| A2=80 | ||||||
Вариант № 32
| Bj Ai | B1=100 | B2=140 | ||
| A1=120 | ||||
| A2=50 | ||||
| A3=170 | ||||
Вариант № 33
| Bj Ai | B1=90 | B2=150 | B3=70 | |||
| A1=80 | ||||||
| A2=110 | ||||||
Вариант № 34
| Bj Ai | B1=100 | B2=80 | ||
| A1=90 | ||||
| A2=80 | ||||
| A3=70 | ||||
Вариант № 35
| Bj Ai | B1=100 | B2=120 | B3=110 | |||
| A1=120 | ||||||
| A2=130 | ||||||
Вариант № 36
| Bj Ai | B1=135 | B2=60 | ||
| A1=75 | ||||
| A2=100 | ||||
| A3=95 | ||||
Вариант № 37
| Bj Ai | B1=100 | B2=60 | B3=200 | |||
| A1=130 | ||||||
| A2=100 | ||||||
Вариант № 38
| Bj Ai | B1=115 | B2=95 | ||
| A1=75 | ||||
| A2=125 | ||||
| A3=75 | ||||
Вариант № 39
| Bj Ai | B1=105 | B2=145 | B3=90 | |||
| A1=100 | ||||||
| A2=100 | ||||||
Вариант № 40
| Bj Ai | B1=135 | B2=60 | ||
| A1=70 | ||||
| A2=80 | ||||
| A3=85 | ||||
