Курсовая работа по "Теории принятия решений"

1. - для всех базисных клеток
2. - для всех свободных клеток

План  обладает свойством, называющимся потенциальным, а соответствующие ему платежи  - потенциалами пунктов A_i и B_j соответственно. Тогда всякий потенциальный план является оптимальным. Для решения транспортной задачи необходимо построить потенциальный план. При улучшении плана необходимо основываться на следующем свойстве платежей и псевдостоимостей: какова бы ни была система платежей , удовлетворяющая условию , для каждой свободной клетки цена цикла пересчета в данной клетке.

 

 

Блок-схема решения транспортной задачи

 

Рис. 2. Блок-схема алгоритма решения задачи

Аналитическое решение задачи

Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись  суммарной потребности потребителей. Проверим это условие. В нашем случае, потребность всех потребителей - 280 единиц продукции равна запасам всех поставщиков.

Математическая модель транспортной задачи:

F = ∑∑cijxij,

при условиях:

∑xij = ai, i = 1,2,…, m,

∑xij = bj, j = 1,2,…, n,

Стоимость доставки единицы груза  из каждого пункта отправления в  соответствующие пункты назначения задана матрицей тарифов, данные которой занесем в таблицу 1.

Таблица 1

Поставщик	Потребитель			Запас
	B1	B2	B3
А1	1	2	2	50
А2	4	5	7	100
А3	6	2	4	130
Потребность	70	100	110	-

 

1. Поиск первого опорного плана.

Используя метод минимального элемента, построим первый опорный план транспортной задачи, для этого составим таблицу (тарифы c_ij располагаются в нижнем правом углу ячейки).

Минимальный элемент матрицы тарифов  находится в ячейке A₁B₁ и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₁ к потребителю B₁ наиболее рентабельный. Запасы поставщика A₁ составляют 50 единиц продукции. Потребность потребителя B₁ составляет 70 единиц продукции. От поставщика A₁ к потребителю B₁ будем доставлять min = { 50 , 70 } = 50 единиц продукции. Разместим в ячейку A₁B₁ значение равное 50. Мы полностью израсходoвали запасы поставщика A₁. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения (Таблица 2).

Минимальный элемент матрицы тарифов находится  в ячейке A₃B₂ и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₃ к потребителю B₂ наиболее рентабельный. Запасы поставщика A₃ составляют 130 единиц продукции. Потребность потребителя B₂ составляет 100 единиц продукции. От поставщика A₃ к потребителю B₂ будем доставлять min = { 130 , 100 } = 100 единиц продукции. Разместим в ячейку A₃B₂ значение равное 100. Мы полностью удовлетворили потребность потребителя B₂. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения (Таблица 2).

Продолжая вычисления, получаем первый опорный план (Таблица 3).

Таблица 2

Поставщик	Потребитель			Запас
	B1	B2	B3
А1	50 1	- 3	- 2	50
А2	- 4	- 5	- 7	100
А3	- 6	100 2	- 4	130
Потребность	70	100	110	-

 

Таблица 3

Поставщик	Потребитель			Запас
	B1	B2	B3
А1	50 1	-   3	-   2	50
А2	20 4	-   5	80 7	100
А3	-  6	100 2	30 4	130
Потребность	70	100	110	-

Заполненные нами ячейки будем называть базисными, остальные - свободными. Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.  Количество базисных ячеек (задействованных маршрутов) равно 5, что и требовалось.

Мы нашли  начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

Значение  целевой функции для этого  опорного плана равно:

S₀ = 1 * 50 + 4 * 20 + 7 * 80 + 2 * 100 + 4 * 30 = 1010 ден. ед.

Общие затраты на доставку всей продукции, для начального решения, составляют 1010 ден. ед.

2. Оценка полученного решения.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя. Для базисной ячейки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.

u_i + v_j = c_ij, где c_ij - тариф клетки A_iB_j

Поскольку, число базисных клеток - 5, а общее количество потенциалов  равно 6, то для однозначного определения  потенциалов, значение одного из них  можно выбрать произвольно.

Примем v3 = 0.

v3 + u2 = c23,     v3 + u2 = 7,    u2 = 7 - 0 = 7

v3 + u3 = c33,      v3 + u3 = 4,     u3 = 4 - 0 = 4

v1 + u2 = c21,      v1 + u2 = 4,     v1 = 4 - 7 = -3

v2 + u3 = c32,      v2 + u3 = 2,     v2 = 2 - 4 = -2

v1 + u1 = c11 ,         v1 + u1 = 1,       u1 = 1- (-3) = 4

 

Таблица 4

Поставщик	Потребитель			Uj
	B1	B2	B3
А1	50         1	-          3	-         2	u1 = 4
А2	20         4	-          5	80        7	u2 = 7
А3	-        6	100       2	30        4	u3 = 4
Vi	v1 = -3	v2 = -2	v3 = 0	-

 

Найдем  оценки свободных ячеек следующим  образом (в таблице 5 они располагаются  в нижнем левом углу ячейки):

12 = c12 - ( u1 + v2 ) = 3 - ( 4 + ( -2 )) = 1,

13 = c13 - ( u1 + v3 ) = 2 - ( 4 + 0 ) = -2,

22 = c22 - ( u2 + v2 ) = 5 - ( 7 + ( -2 )) = 0,

31 = c31 - ( u3 + v1 ) = 6 - ( 4 + ( -3 )) = 5.

 

Таблица 5

Поставщик	Потребитель			Uj
	B1	B2	B3
А1	50 1	1     -        3	-2          -        2	u1 = 4
А2	20 4	0           -         5	80       7	u2 = 7
А3	5          -         6	100      2	30       4	u3 = 4
Vi	v1 = -3	v2 = -2	v3 = 0	-

 

Оценка  свободной ячейки A₁B₃ (незадействованного маршрута) отрицательная ( ₁₃ = -2), следовательно, решение не является оптимальным.

Построим  цикл для выбранной ячейки A₁B₃. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

Ячейки, образующие цикл для свободной ячейки A₁B₃:

A₁B₃, A₁B₁, A₂B₁, A₂B₃

Пусть ячейка A₁B₃, для которой мы строили цикл, имеет порядковый номер один (Таблица 6).

Среди ячеек  цикла A₁B₁ , A₂B₃ , номера которых четные, найдем ячейку, обладающую наименьшим значением.

min = {50, 80} = 50

В данном случае, это ячейка A₁B₁.

Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A₁ к потребителю B₁, по которому доставляется меньше всего (50) единиц продукции. Данный маршрут мы исключим из схемы доставки продукции.

 

Таблица 6

Поставщик	Потребитель			Запас
	B1	B2	B3
А1	50        1	1       -        3	-2          -         2	50
А2	20        4	0           -         5	80       7	100
А3	5          -         6	100      2	30       4	130
Потребность	70	100	110	-

 

От ячеек  цикла с четными номерами отнимает 50. К ячейкам с нечетными номерами прибавляем 50.

Мы вводим новый маршрут доставки продукции  от поставщика A₁ к потребителю B₃. По данному маршруту доставим 50 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 50 ден. ед.

По маршруту от поставщика A₁ к потребителю B₁ мы полностью перестаем доставлять продукцию. Общие затраты уменьшатся на 1 * 50 ден. ед. От поставщика A₂ к потребителю B₁ дополнительно поставим 50 единиц продукции, по цене доставки 4 за единицу продукции. Общие затраты увеличатся на 4 * 50 ден. ед. Сократим поставку от поставщика A₂ к потребителю B₃ на 50 единиц продукции, по цене доставки 7 за единицу продукции. Общие затраты уменьшатся на 7 * 50 ден. ед.

Данные  преобразования не изменят баланс между  поставщиками и потребителями. Все  поставщики израсходуют все свои запасы, а все потребители получат  необходимое им количество продукции.

 

Таблица 7

Поставщик	Потребитель			Запас
	B1	B2	B3
А1	50-50     1	1       -        3	-2          +50        2	50
А2	20+50    4	0           -         5	80-50    7	100
А3	5          -         6	100      2	30       4	130
Потребность	70	100	110	-