Обозначим общее количество имеющегося в наличие груза:
Лабораторная работа №5
Решение транспортных задач»
Пример решения 5.1.
Постановка задачи: Исходные данные транспортной задачи приведены схематически: внутри прямоугольника заданы удельные транспортные затраты на перевозку единицы груза, слева указаны мощности поставщиков, а сверху мощности потребителей. Сформулировать экономико-математическую модель транспортной задачи, найти оптимальный план закрепления поставщиков за потребителями.
| 40 | 30 | 30 | 50 | |
| 60 70 20 | 2 3 2 | 3 4 5 | 5 9 2 | 1 4 5 |
Обозначим общее количество имеющегося в наличие груза:
a = 60 + 70 + 20 = 150
Потребности в грузе:
b = 40 + 30 + 30 +50 = 150
Так как a=b имеем закрытую модель или модель удовлетворяющую условию баланса. В этой модели суммарный объем груза у поставщиков равен суммарному спросу потребителей.
Общее число базисных клеток равно: m+n-1=6.
Найдём опорный план перевозок транспортной задачи методом минимальной стоимости.
В этом методе построение исходного решения начинают с клетки с наименьшей величиной стоимости. Из оставшейся таблицы снова выбирают наименьшую стоимость, и процесс распределения запасов продолжается, пока все запасы не будут распределены.
| Пункты | В 
| В 
| В 
| В 
| Запасы |
| А
| 2 10 | 3 | 5 | 1 50 | 60 |
| А
| 3 30 | 4 30 | 9 10 | 4 | 70 |
| А
| 2 | 5 | 2 20 | 5 | 20 |
| Потребности | 40 | 30 | 30 | 50 | 150 |
|
|
|
Общая стоимость перевозок: 
Исследование базисного решения на оптимальность.
Вычислим потенциалы. Исходя из базисных переменных. Для их
нахождения используем условие: 
Полагая, например, 
найдём:
Для каждой свободной клетки вычислим относительные оценки:
| 
| 
| 
| ||||||
| Пункты | В
| В
| В
| В
| Запасы | ||||
| А
| - 2
10 | 3 | + 5
l
| 1 50 | 60 | |||
| А
| + 3
30
| 4 30 | - 9 10 | 4 | 70 | |||
| А
| 2 | 5 | 2 20 | 5 | 20 | |||
| Потребности | 40 | 30 | 30 | 50 | 150 | ||||
Минимальной разностью является 
для клетки (1;3). Для определения количества груза подлежащего распределению, построим замкнутый цикл (указан пунктиром в табл.).
Найдём значение l=min(10,10)=10, равное наименьшему из чисел, стоящих в отрицательных вершинах цикла. Далее двигаясь по означенному
циклу, вычитаем из объемов перевозок, расположенных в клетках, которые обозначены знаком «-», и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком «+». Элементы таблицы не входящие в цикл, остаются без изменений.
|
|
|
Получим новую таблицу:
|
|
|
|
| |||
| Пункты | В
| В
| В
| В
| Запасы | |
|
| А
| 2 0 | 3 | 5 10 | 1 50 | 60 |
|
| А
| 3 40 | 4 30 | 9 | 4 | 70 |
|
| А
| 2 | 5 | 2 20 | 5 | 20 |
| Потребности | 40 | 30 | 30 | 50 | 150 | |
Стоимость перевозок по этому плану: 
Вычислим потенциалы.
Полагая, например, найдём:
Для каждой свободной клетки вычислим относительные оценки:
Так как для всех свободных клеток таблицы неравенство 
выполняется, то полученное решение
будет оптимальным. При таком плане перевозок затраты будут наименьшими и составят 
.
Решение с помощью надстройки над решением:
| Целевая ячейка (Минимум) |
|
|
|
| ||||
|
| Ячейка | Имя | Исходное значение | Результат |
|
| ||
|
| $N$8 | Коэфф в ЦФ ЦФ | 460 | 460 |
|
| ||
|
|
|
|
|
|
|
| ||
|
|
|
|
|
|
|
| ||
| Изменяемые ячейки |
|
|
|
| ||||
|
| Ячейка | Имя | Исходное значение | Результат |
|
| ||
|
| $B$5 | Значение x1 | 40 | 40 |
|
| ||
|
| $C$5 | Значение x2 | 0 | 0 |
|
| ||
|
| $D$5 | Значение x3 | 10 | 10 |
|
| ||
|
| $E$5 | Значение x4 | 10 | 10 |
|
| ||
|
| $F$5 | Значение x5 | 0 | 0 |
|
| ||
|
| $G$5 | Значение x6 | 30 | 30 |
|
| ||
|
| $H$5 | Значение x7 | 0 | 0 |
|
| ||
|
| $I$5 | Значение x8 | 40 | 40 |
|
| ||
|
| $J$5 | Значение x9 | 0 | 0 |
|
| ||
|
| $K$5 | Значение x10 | 0 | 0 |
|
| ||
|
| $L$5 | Значение x11 | 20 | 20 |
|
| ||
|
| $M$5 | Значение x12 | 0 | 0 |
|
| ||
|
|
|
|
|
|
|
| ||
|
|
|
|
|
|
|
| ||
| Ограничения |
|
|
|
| ||||
|
| Ячейка | Имя | Значение | Формула | Статус | Разница | ||
|
| $N$11 | Рес склада 1 Лев часть | 60 | $N$11=$P$11 | не связан. | 0 | ||
|
| $N$12 | Рес склада 2 Лев часть | 70 | $N$12=$P$12 | не связан. | 0 | ||
|
| $N$13 | Рес склада 3 Лев часть | 20 | $N$13=$P$13 | не связан. | 0 | ||
|
| $N$14 | Потр магазина 1 Лев часть | 40 | $N$14=$P$14 | не связан.
| 0 | ||
|
| $N$15 | потр магазина 2 Лев часть | 30 | $N$15=$P$15 | не связан. | 0 | ||
|
| $N$16 | Потр магазина 3 Лев часть | 30 | $N$16=$P$16 | не связан. | 0 | ||
|
| $N$17 | Потр магазина 4 Лев часть | 50 | $N$17=$P$17 | не связан. | 0 | ||
|
| $B$5 | Значение x1 | 40 | $B$5>=$B$6 | не связан. | 40 | ||
|
| $C$5 | Значение x2 | 0 | $C$5>=$C$6 | связанное | 0 | ||
|
| $D$5 | Значение x3 | 10 | $D$5>=$D$6 | не связан. | 10 | ||
|
| $E$5 | Значение x4 | 10 | $E$5>=$E$6 | не связан. | 10 | ||
|
| $F$5 | Значение x5 | 0 | $F$5>=$F$6 | связанное | 0 | ||
|
| $G$5 | Значение x6 | 30 | $G$5>=$G$6 | не связан. | 30 | ||
|
| $H$5 | Значение x7 | 0 | $H$5>=$H$6 | связанное | 0 | ||
|
| $I$5 | Значение x8 | 40 | $I$5>=$I$6 | не связан. | 40 | ||
|
| $J$5 | Значение x9 | 0 | $J$5>=$J$6 | связанное | 0 | ||
|
| $K$5 | Значение x10 | 0 | $K$5>=$K$6 | связанное | 0 | ||
|
| $L$5 | Значение x11 | 20 | $L$5>=$L$6 | не связан. | 20 | ||
|
| $M$5 | Значение x12 | 0 | $M$5>=$M$6 | связанное | 0 | ||
Пример решения 5.2.
Постановка задачи: Составить план перевозок грузов с наименьшей стоимостью от трех поставщиков 
соответственно в количествах 130, 90, 100 ед. к пяти потребителям 
соответственно в количествах 45, 60, 70, 80, 65. Стоимость перевозок единиц груза приведена в таблице.
Таблица стоимости перевозок:
| 2 | 3 | 6 | 8 | 2 |
| 8 | 1 | 2 | 3 | 5 |
| 7 | 4 | 4 | 1 | 4 |
Обозначим общее количество имеющегося в наличие груза:
a = 130 + 90 + 100 = 320
Потребности в грузе:
b = 45 + 60 + 70 + 80 + 65 = 320
Так как a=b имеем закрытую модель или модель удовлетворяющую условию баланса. В этой модели суммарный объем груза у поставщиков равен суммарному спросу потребителей.
Общее число базисных клеток равно: m+n-1=7.
Найдём опорный план перевозок транспортной задачи методом минимальной стоимости.
В этом методе построение исходного решения начинают с клетки с наименьшей величиной стоимости. Из оставшейся таблицы снова выбирают наименьшую стоимость, и процесс распределения запасов продолжается, пока все запасы не будут распределены.
| Пункты | В
| В 
| В
| В 
| В 
| Запасы |
| А
| 2 45 | 3 20 | 6 | 8 | 2 65 | 130 |
| А
| 8 | 1 40 | 2 50 | 3 | 5 | 90 |
| А
| 7 | 4 | 4 20 | 1 80 | 4 | 100 |
| Потребности | 45 | 60 | 70 | 80 | 65 | 320 |
Общая стоимость перевозок: 
Дата добавления: 2018-11-24; просмотров: 307; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!