Министерство образования и науки РФ
Федеральное государственное бюджетное учреждение высшего профессионального образования
« Саратовский государственный технический университет им. Гагарина Ю.А.»
«Решение транспортной задачи по распределительному методу
и методу потенциалов»
Выполнил
Студент АМФ
Гр. НТС-21
Карабашев Д.В.
Проверил
Куцемако А.Н.
Саратов 2015
1. Задание
При заданных значениях (табл. 1.1) построить наиболее оптимальный план перевозок с наименьшей возможной затратой, используя следующие методы:
а) метод распределительный; б) метод потенциалов.
Таблица 1.1
Поставщик |
360 |
220 |
320 |
|
|
Та |
22 |
14 |
16 |
28 |
30 |
Потребитель |
170 |
140 |
200 |
195 |
145 |
ри |
19 |
17 |
26 |
36 |
36 |
Функция цели |
21320 |
|
|
|
|
фы |
37 |
30 |
31 |
39 |
41 |
2. Решение
2.1 Метод распределительный
Составляем опорный план с использованием метода северо-западного угла (табл. 2.1.1). Так как в плане остаются лишние единицы товара в наличие, вводится графа , подразумевающая единицы товара, оставшиеся на складе.
Таблица 2.1.1
|
Наличие |
||||||
300/200/ /100/0 |
|||||||
300/200//100/0 |
|||||||
195/5/0 |
|||||||
Потребность |
100/0 |
100/0 |
200/100/0 |
100/0 |
290/190/0 |
5/0 |
795=795 |
Проверяем план на невырожденность: (3+6-1)=8. Условие выполняется, значит план невырожденный и решение можно продолжать.
Находим общую стоимость текущего опорного плана:
Строим циклы для свободных клеток и находим их оценки (рис. 2.1.1.1) и (рис. 2.1.1.2):
Рис. 2.1.1.1
Строим циклы для свободных клеток и находим их оценки (рис. 2.1.1.1):
(Рис. 2.1.1.1: a),
(Рис. 2.1.1.1: б),
(Рис. 2.1.1.1: в),
(Рис. 2.1.1.2: г),
(Рис. 2.1.1.2: д),
(Рис. 2.1.1.2: е),
(Рис. 2.1.1.2: ж),
(Рис. 2.1.1.2: з),
Продолжаем находить оценки свободных клеток (рис. 2.1.1.1):
(Рис. 2.1.1.2: и),
(Рис. 2.1.1.2: к).
Так как присутствует отрицательные оценки, план неоптимальный, поэтому находим наибольшую по модулю из отрицательных оценок с наименьшим тарифом и определяем наименьшее количество единиц товара в ее цикле (рис. 2.1.1.2: а), среди обозначенных отрицательным знаком клеток (2.2.1). Производим сдвиг по циклу и составляем новый план (табл. 2.1.2).
2.2.1
Таблица 2.1.2
|
||||||
Повторяем действия, проведенные ранее. Проверяем план на невырожденность: (3+6-1)=8. Условие выполняется, значит план невырожденный и решение можно продолжать.
Находим общую стоимость текущего опорного плана:
Строим циклы для свободных клеток и находим их оценки (рис. 2.1.2.1) и (рис. 2.1.2.2):
Рис. 2.1.2.1
Рис. 2.1.2
Находим оценки построенных циклов (рис. 2.1.2):
(Рис. 2.1.2.1: а),
(Рис. 2.1.2.1: б),
(Рис. 2.1.2.1: в),
(Рис. 2.1.2.2: а),
(Рис. 2.1.2.2: б),
(Рис. 2.1.2.2: в),
(Рис. 2.1.2.2: г),
(Рис. 2.1.2.2: д),
(Рис. 2.1.2.2: е),
(Рис. 2.1.2.2: ж),
Так как присутствует отрицательные оценки, план неоптимальный, поэтому находим наибольшую по модулю из отрицательных оценок с наименьшим тарифом и определяем наименьшее количество единиц товара в ее цикле (рис. 2.1.2: е), среди обозначенных отрицательным знаком клеток (2.2.2). Производим сдвиг по циклу и составляем новый план (табл. 2.1.3).
2.2.2
Таблица 2.1.3
|
||||||
Повторяем действия, проведенные ранее. Проверяем план на невырожденность: (3+6-1)=8. Условие выполняется, значит план невырожденный и решение можно продолжать.
Находим общую стоимость текущего опорного плана:
Строим циклы для свободных клеток и находим их оценки (рис. 2.1.3):
Рис. 2.1.3
Находим оценки свободных клеток (рис. 2.1.3):
(Рис. 2.1.3: б),
(Рис. 2.1.3: а),
(Рис. 2.1.3: в),
(Рис. 2.1.3: г),
(Рис. 2.1.3: д),
(Рис. 2.1.3: е),
(Рис. 2.1.3: ж),
(Рис. 2.1.3: з),
(Рис. 2.1.3: и),
(Рис. 2.1.3: к),
Так как все полученные оценки неотрицательные, план является оптимальным. Его значение равняется: