Автор работы: Пользователь скрыл имя, 28 Февраля 2014 в 11:52, курсовая работа
Целью данной работы является решение транспортной задачи в заданных условиях.
В связи с поставленной целью необходимо решить ряд задач:
- построить опорные планы транспортной модели методами северо-западного угла, минимальной стоимости и методом Фогеля;
- произвести оценку полученных решений методом потенциалов;
- сделать выводы по результатам решения.
Введение
1. Транспортная модель закрытого типа
1.1 Условие задачи
1.2 Построение опорных планов транспортной модели
1.2.1 Построение опорного плана методом северо-западного угла
1.2.2 Построение опорного плана методом минимальной стоимости
1.2.3 Построение опорного плана методом Фогеля
1.3 Оптимизация транспортной модели закрытого типа
1.3.1 Метод потенциалов на основе опорного плана, построенного методом северо-западного угла
1.3.2 Метод потенциала на основе опорного плана, построенного методом минимальной стоимости
1.3.3 Метод потенциалов на основе опорного плана, построенного методом Фогеля
2. Транспортная модель открытого типа
2.1 Условия задачи
Построение опорных планов транспортной модели
2.2.1 Построение опорного плана методом северо-западного угла
2.2.2 Построение опорного плана методом минимальной стоимости
2.2.3 Построение опорного плана методом Фогеля
2.3 Оптимизация транспортной модели открытого типа
2.3.1 Метод потенциала на основе опорного плана, построенного методом северо-западного угла
2.3.1 Метод потенциала на основе опорного плана, построенного методом минимальной стоимости
2.3.1 Метод потенциала на основе опорного плана, построенного методом Фогеля
Заключение
Список использованных источников
v2 + u3 = c32 |
v2 + u3 = 4 |
u3 = 4 - 0 = 4 |
v2 + u4 = c42 |
v2 + u4 = 3 |
u4 = 3 - 0 = 3 |
v2 + u5 = c52 |
v2 + u5 = 0 |
u5 = 0 - 0 = 0 |
v3 + u5 = c53 |
v3 + u5 = 0 |
v3 = 0 - 0 = 0 |
v1 + u2 = c21 |
v1 + u2 = 3 |
v1 = 3 - 4 = -1 |
v1 + u1 = c11 |
v1 + u1 = 1 |
u1 = 1 - ( -1 ) = 2 | ||||||||
Поставщик |
Потребитель |
U j | ||||||||
B 1 |
B 2 |
B 3 | ||||||||
A 1 |
120 |
- |
- |
u 1 = 2 | ||||||
1 |
2 |
9 | ||||||||
A 2 |
105 |
5 |
- |
u 2 = 4 | ||||||
3 |
4 |
1 | ||||||||
A 3 |
- |
20 |
- |
u 3 = 4 | ||||||
6 |
4 |
8 | ||||||||
A 4 |
- |
70 |
- |
u 4 = 3 | ||||||
2 |
3 |
3 | ||||||||
A 5 |
- |
40 |
140 |
u 5 = 0 | ||||||
0 |
0 |
0 | ||||||||
V i |
v 1 = -1 |
v 2 = 0 |
v 3 = 0 |
|||||||
Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
12 = c12 - ( u1 + v2 ) = 2 - ( 2 + 0 ) = 0 |
13 = c13 - ( u1 + v3 ) = 9 - ( 2 + 0 ) = 7 |
23 = c23 - ( u2 + v3 ) = 1 - ( 4 + 0 ) = -3 |
31 = c31 - ( u3 + v1 ) = 6 - ( 4 + ( -1 ) ) = 3 |
33 = c33 - ( u3 + v3 ) = 8 - ( 4 + 0 ) = 4 |
41 = c41 - ( u4 + v1 ) = 2 - ( 3 + ( -1 ) ) = 0 |
43 = c43 - ( u4 + v3 ) = 3 - ( 3 + 0 ) = 0 |
51 = c51 - ( u5 + v1 ) = 0 - ( 0 + ( -1 ) ) = 1 | ||||||||
Поставщик |
Потребитель |
U j | ||||||
B 1 |
B 2 |
B 3 | ||||||
A 1 |
120 |
- |
- |
u 1 = 2 | ||||
1 |
0 |
2 |
7 |
9 | ||||
A 2 |
105 |
5 |
- |
u 2 = 4 | ||||
3 |
4 |
-3 |
1 | |||||
A 3 |
- |
20 |
- |
u 3 = 4 | ||||
3 |
6 |
4 |
4 |
8 | ||||
A 4 |
- |
70 |
- |
u 4 = 3 | ||||
0 |
2 |
3 |
0 |
3 | ||||
A 5 |
- |
40 |
140 |
u 5 = 0 | ||||
1 |
0 |
0 |
0 | |||||
V i |
v 1 = -1 |
v 2 = 0 |
v 3 = 0 |
|||||
Оценка свободной ячейки A2B3 (незадействованного маршрута) отрицательная (∆23 =-3) , следовательно решение не является оптимальным.
Построим цикл для выбранной ячейки A2B3:
Ячейки образующие цикл для свободной ячейки A2B3:
A2B3 , A2B2 , A5B2 , A5B3
Пусть ячейка A2B3, для которой мы строили цикл, имеет порядковый номер один.
Среди ячеек цикла A2B2 , A5B3 , номера которых четные, найдем ячейку, обладающую наименьшим значением.
min = (5, 140) = 5
В данном случае, это ячейка A2B2.
Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A2 к потребителю B2, по которому доставляется меньше всего (5) единиц продукции. Данный маршрут мы исключим из схемы доставки продукции.
От ячеек цикла с четными номерами отнимает 5. К ячейкам с нечетными номерами прибавляем 5.
Мы вводим новый маршрут доставки продукции от поставщика A2 к потребителю B3. По данному маршруту доставим 5 единиц продукции, по цене доставки 1 за единицу продукции. Общие затраты увеличатся на 1 * 5 ден. ед.
По маршруту от поставщика A2 к потребителю B2 мы полностью перестаем доставлять продукцию.
Общие затраты уменьшатся на 4 * 5 ден. ед.
От поставщика A5 к потребителю B2 дополнительно поставим 5 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты увеличатся на 0 * 5 ден. ед.
Сократим поставку от поставщика A5 к потребителю B3 на 5 единиц продукции, по цене доставки 0 за единицу продукции. Общие затраты уменьшатся на 0 * 5 ден. ед.
Общие расходы на доставку продукции от поставщиков к потребителям изменятся на
1 * 5 - 4 * 5 + 0 * 5 - 0 * 5 = ( 1 - 4 + 0 - 0 ) * 5 = -3 * 5 ден. ед.
Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.
Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.
Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 745 + ( - 15 ) = 730 ден. ед..
Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.
(ui + vj = cij, где cij - тариф клетки AiBj)
Поскольку, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
Примем v1 = 0. |
v1 + u1 = c11 |
v1 + u1 = 1 |
u1 = 1 - 0 = 1 |
v1 + u4 = c41 |
v1 + u4 = 2 |
u4 = 2 - 0 = 2 |
v1 + u5 = c51 |
v1 + u5 = 0 |
u5 = 0 - 0 = 0 |
v2 + u5 = c52 |
v2 + u5 = 0 |
v2 = 0 - 0 = 0 |
v3 + u5 = c53 |
v3 + u5 = 0 |
v3 = 0 - 0 = 0 |
v3 + u2 = c23 |
v3 + u2 = 1 |
u2 = 1 - 0 = 1 |
v2 + u3 = c32 |
v2 + u3 = 4 |
u3 = 4 - 0 = 4 |
Поставщик |
Потребитель |
U j | |||||
B 1 |
B 2 |
B 3 | |||||
A 1 |
120 |
- |
- |
u 1 = 1 | |||
1 |
2 |
9 | |||||
A 2 |
- |
- |
110 |
u 2 = 1 | |||
3 |
4 |
1 | |||||
A 3 |
- |
20 |
- |
u 3 = 4 | |||
6 |
4 |
8 | |||||
A 4 |
70 |
- |
- |
u 4 = 2 | |||
2 |
3 |
3 | |||||
A 5 |
35 |
115 |
30 |
u 5 = 0 | |||
0 |
0 |
0 | |||||
V i |
v 1 = 0 |
v 2 = 0 |
v 3 = 0 |
||||
Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
12 = c12 - ( u1 + v2 ) = 2 - ( 1 + 0 ) = 1 |
13 = c13 - ( u1 + v3 ) = 9 - ( 1 + 0 ) = 8 |
21 = c21 - ( u2 + v1 ) = 3 - ( 1 + 0 ) = 2 |
22 = c22 - ( u2 + v2 ) = 4 - ( 1 + 0 ) = 3 |
31 = c31 - ( u3 + v1 ) = 6 - ( 4 + 0 ) = 2 |
33 = c33 - ( u3 + v3 ) = 8 - ( 4 + 0 ) = 4 |
42 = c42 - ( u4 + v2 ) = 3 - ( 2 + 0 ) = 1 |
43 = c43 - ( u4 + v3 ) = 3 - ( 2 + 0 ) = 1 |
Поставщик |
Потребитель |
U j | |||||
B 1 |
B 2 |
B 3 | |||||
A 1 |
120 |
- |
- |
u 1 = 1 | |||
1 |
1 |
2 |
8 |
9 | |||
A 2 |
- |
- |
110 |
u 2 = 1 | |||
2 |
3 |
3 |
4 |
1 | |||
A 3 |
- |
20 |
- |
u 3 = 4 | |||
2 |
6 |
4 |
4 |
8 | |||
A 4 |
70 |
- |
- |
u 4 = 2 | |||
2 |
1 |
3 |
1 |
3 | |||
A 5 |
35 |
115 |
30 |
u 5 = 0 | |||
0 |
0 |
0 | |||||
V i |
v 1 = 0 |
v 2 = 0 |
v 3 = 0 |
||||