Реферат: Транспортная задача 5
Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Два из них - метод потенциалов и Венгерский метод - рассматриваются ниже.
4. Методы определения первоначального опорного плана
4.1. Метод минимального элемента
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел 
и 
. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Пример
Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:
| 2 | 3 | 4 | 15 |
| 11 | 6 | 10 | 1 |
| 8 | 9 | 3 | 3 |
| 4 | 1 | 2 | 21 |
| 10 | 20 | 10 |
Решение:
Задача сбалансирована.
Строим первоначальный опорный план методом минимального элемента.
- Выясним минимальную стоимость перевозок.
Первая перевозка будет осуществляться с пункта производства 
в пункт потребления и она составит максимально возможное число единиц продукта 
:. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки 
.Выясним минимальную стоимость перевозок (без учета столбца № 2). 
Вторая и третья перевозки будут осуществляться с пункта производства 
и 
в пункт потребления 
и 
соответственно и составят максимально возможное число единиц продукта : 
, 
; 
- Четвертая перевозка осуществляется с пункта
в пункт потребления , т.к. 
(без учета первого, второго столбца и четвертой строки). 
. - Пятая перевозка осуществляется с пункта в пункт потребления , т.к.
(без учета первого, второго столбца, третьей и четвертой строки). 
.
6. Шестая перевозка осуществляется с пункта 
в пункт потребления т.к. 
(без учета первого, второго столбца, первой, третьей и четвертой строки). 
Опорный план имеет вид;
| 10 | 5 | 0 |
| 0 | 1 | 0 |
| 0 | 3 | 0 |
| 0 | 11 | 10 |
4.2. Метод аппроксимации Фогеля
При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость.
Если минимальная стоимость одинакова для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).
Пример
Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи:
(Здесь мы перенесли потребности в верхнюю строку для удобства построения плана). Рассмотрим задачу, приведенную для методов северо-западного угла и минимального элемента
Решение:
| 10 | 20 | 10 | ||||
|
2 7 |
3 0 |
4 8 | 15 | 1 | 1 | 1 |
|
11 0 |
6 1 |
10 0 | 1 | 4 | 4 | - |
|
К-во Просмотров: 483
Бесплатно скачать Реферат: Транспортная задача 5
|