Решение оптимизационной задачи по грузоперевозкам

Применим данный метод к конкретной задаче (таблица 5).

 

Таблица 5

Применение метода минимальной стоимости

b=903 a=903	b1=202	b2=244	b3=223	b4=234
a1=176	0,87	0,72     176	0,79	0,75
a2=218	1,08	0,89   68	0,98	0,93      150
a3=197	0,98       98	0,81	0,88        99	0,84
a4=208	1,03	0,85	0,93124	0,89       84
a5=104	0104	0	0	0

 

В этом случае транспортные затраты составят С= 176*0,72 + 68*0,89 + 150*0,93 + 98*0,98 + 99*0,88 + 124*0,93 + 84*0,89 + 0 = 699,98 денежных единиц.

Проанализируем полученное решение: сравнивая с предыдущим методом, мы существенно сократили транспортные затраты. В данном случае, в противоположность методу северо-западного угла,  мы в полной мере удовлетворим потребности второго, третьего и четвертого потребителя. Однако  первый не вполне будет удовлетворен, на 48,5%.

Нам нужно доказать, что данный план является базисным для того, чтобы при необходимости проверить его на оптимальность.

Для того чтобы узнать, является ли план базисным или нет, надо исследовать решение на следующие условия:

1. Число положительных  клеток должно быть меньше  либо ровно N;

2. Отсутствие циклов.

N = m + n – 1. N = 8. Число положительных клеток данной модели равно 8.Это удовлетворяет условию  8 ≤ N. Из этого следует, что план невырожденный.

Также здесь отсутствует цикл.

В результате данный план является базисным невырожденным решением задачи.

Таким образом, в ходе применения метода минимальной стоимости мы получили следующее решение (рис. 2) при транспортных затратах в 699,98  денежных единиц.

Рис. 2 Результат применения метода минимальной стоимости.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Проверка наилучшего плана на оптимальность решения  

    

Оптимальным является базисный план при условии С(х) С(х*).

Проверить план на его оптимальность можно с помощью признака оптимальности базисного невырожденного плана перевозок.

Пусть X=(Xij), где i=1…m, j=1…n является базисным невырожденным решением системы уравнений:

, i=1…m, j=1…n (только для положительных клеток).

Если найденные решения удовлетворяют условию , i=1…m, j=1…n для всех клеток, то Х- оптимальный план перевозок.

Проверим на оптимальность наилучший план перевозок, найденный с помощью применения вышеуказанных методов. В нашем случае лучший результат мы получили с помощью метода минимальной стоимости. Затраты в нем равняются 699,98 денежных единиц. Для облегчения расчетов продублируем ниже таблицу, содержащую наилучшее из полученных решений (таблица 6)

 

Таблица 6

Результаты применения метода минимальной стоимости

b=903 a=903	b1=202	b2=244	b3=223	b4=234
a1=176	0,87	0,72     176	0,79	0,75
a2=218	1,08	0,89   68	0,98	0,93      150
a3=197	0,98       98	0,81	0,88       99	0,84
a4=208	1,03	0,85	0,93         124	0,89       84
a5=104	0104	0	0	0

 

Определим значения vj и ui.

Vj – Ui = Cij прихij > 0

 

X12=176>0          V2 – U1 = 0,72

X22=68>0            V2 – U2 = 0,89

X24=150>0          V4 – U2 = 0,93

X31=98>0            V1 – U3 = 0,98

X33=99>0            V3 – U3 = 0,88

X43=124>0          V3 – U4 = 0,93

X44=84>0            V4 – U4 = 0,89

X51=104>0          V1 – U5 = 0

Берем произвольно: U1 = 0, тогда

U1=0                        V1=0, 9

U2 = -0, 17               V2=0,72

U3= -0, 08                V3= 0,8

U4 = -0, 13               V4= 0,76

U5= 0, 9

Проверим условие оптимальности для неположительных клеток матричной модели. Знак «+» говорит о том, что условие выполняется, знак «-» - не выполняется.

Vj – Ui ≤ Cij

X11 :0,9-0 = 0,9 > 0,87-

X13 :  0,8-0= 0,8>0,79 -

X14 : 0,76-0 = 0,75 ≤0,75 +

X21 :0,9 +0,17 = 1,07 ≤1,08 +

X23 : 0,8+0,17 = 0,97≤0,98 +

X32 : 0,72+0,08 = 0,8 ≤ 0,81 +

X34 :0,76+0,08 = 0,84≤ 0,84 +

X41 : 0,9+0,13 = 1,03 ≤ 1,03 +

X42 : 0,72+0,13 = 0,85≤0,85+

X52 : 0,72-0,9 = -0,18≤ 0 +

X53 :0,8-0,9 = -0,1 ≤ 0 +

X54 : 0,76-0,9 = -0,14 ≤0 +

 

Таким образом, мы получаем следующую таблицу.

 

Таблица 7

Проверка оптимальности решения

 

b=903 a=903	b1=202	b2=244	b3=223	b4=234
a1=176	0,87       -	0,72     176	0,79        -	0,75        +
a2=218	1,08       +	0,89   68	0,98         +	0,93      150
a3=197	0,98       98	0,81       +	0,88        99	0,84+
a4=208	1,03       +	0,85       +	0,93124	0,89       84
a5=104	0104	0          +	0          +	0          +

 

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

 

 

 

 

 

 

 

 

 

 

 

5. Нахождение оптимального решения методом потенциалов 

 

Метод потенциалов используется для нахождения оптимального плана. Он стартует с неоптимального базисного невырожденного плана перевозок.

Алгоритм метода потенциалов:

1. Базисный невырожденный план перевозок
2. Проверка оптимальности
3. Нахождение Vj, Ui
4. Vj – Ui ≤ Cij
5. Если П. 4 выполняется, то оптимальный план найден.

Если П. 4 не выполняется, то находим p,q по следующей формуле:

6. Находим Xqp

Xqp=Z

7. Находим и устраняем цикл.
8. Возвращаемся к П.2.

Итак, применим метод потенциалов для лучшей из полученных моделей (получена методом минимальной стоимости). Модель представлена в таблице 8, на которой отображена проверка решения на оптимальность.

 

Таблица 8

Проверка оптимальности решения

 

b=903 a=903	b1=202	b2=244	b3=223	b4=234
a1=176	0,87       -	0,72     176	0,79        -	0,75        +
a2=218	1,08       +	0,89   68	0,98         +	0,93      150
a3=197	0,98       98	0,81       +	0,88        99	0,84+
a4=208	1,03       +	0,85       +	0,93124	0,89       84
a5=104	0104	0          +	0          +	0          +

 

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

Как мы видим, две клетки (X11, X13) не удовлетворяют признаку оптимальности базисного невырожденного плана перевозок. Клетка X11 содержит максимальное отклонениеV1 – U1 от C11 в 0,03, поэтому разместим в этой клетке значение Z. Теперь, согласно алгоритму метода, нам необходимо устранить образовавшийся в результате появления нового значения Z цикл.

X11, X12, X22, X24, X44, X43, X33, X31 образуют цикл (таблица 9).

 

 

 

 

 

 

 

Таблица 9

Введение новой переменной Z и способ устранения образовавшего цикла

 

b=903 a=903	b1=202	b2=244	b3=223	b4=234
a1=176	0,87       Z	0,72     176-Z	0,79        -	0,75        +	U1 = 0
a2=218	1,08       +	0,89   68+Z	0,98         +	0,93      150-Z	U2 = -0,17
a3=197	0,98       98-Z	0,81       +	0,88        99+Z	0,84+	U3 = -0,08
a4=208	1,03       +	0,85       +	0,93124-Z	0,89       84+Z	U4 = -0,13
a5=104	0104	0          +	0          +	0          +	U5 = 0,9
	V1 = 0,9	V2 = 0,72	V3 = 0,8	V4 = 0,76

 

Чтобы сделать план базисным, надо избавиться от данного цикла, то есть Z должно быть равно min(176;98). Z = 98.

176 – Z  ≥ 0

68 + Z ≥ 0

150 – Z ≥ 0

84 + Z ≥ 0

124 – Z ≥ 0

99 + Z ≥ 0

98 – Z ≥ 0

Z ≥ 0

ЯчейкаX31 будет равна нулю. Таким образом, третий поставщик не будет поставлять продукцию первому потребителю.

Преобразуем нашу таблицу, введем вместо Z реальное значение и устраним цикл (таблица 10).

 

Таблица 10

Введение вместо переменной Z реальное значение и устранение образовавшего цикла

 

b=903 a=903	b1=202	b2=244	b3=223	b4=234
a1=176	0,8798	0,7278	0,79	0,75	U1 = 0
a2=218	1,08	0,89   166	0,98	0,93      52	U2 = -0,17
a3=197	0,98	0,81	0,88        197	0,84	U3 = -0,08
a4=208	1,03	0,85	0,9326	0,89       182	U4 = -0,13
a5=104	0104	0	0	0	U5 = 0,87
	V1 = 0,87	V2 = 0,72	V3 = 0,8	V4 = 0,76