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

 

Рассчитаем транспортные затраты для полученного решения: С=98*0,87 + 78*0,72 + 166*0,89 + 52*0,93 + 197*0,88 +26*0,93 + 182*0,89= 697,04 денежных единиц. Данный результат  на 2,94 денежных единиц лучше предыдущего плана. Этот факт подтверждает то обстоятельство, что мы правильно применили метод потенциалов, тем самым уменьшив транспортные затраты.

 

 

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

Vj – Ui ≤ Cij

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

X14 :  0,76-0 = 0,76 >0,75 -

X21 : 0,87+0,17 = 1,04 ≤ 1,08+

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

X31 : 0,87+0,08 = 0,95 ≤ 0,98 +

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

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

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

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

X52 : 0,72-0,87 = -0,15≤0+

X53 :0,8-0,87 = -0,07 ≤ 0 +

X54 : 0,76-0,87 = -0,11 ≤0 + 

 

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

 

Таблица 11

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

 

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

 

Анализируемая модель содержит в себе допустимый базисный план перевозок, однако он не является оптимальным. Согласно алгоритму метода потенциалов вернемся к пункту 2. Как мы видим, две клетки (X13, X14) не удовлетворяют признаку оптимальности базисного невырожденного плана перевозок. Мы можем выбрать из них любую, потому что они обе имеют отклонение в 0,01. ВыберемX14. Теперь согласно алгоритму метода нам необходимо устранить образовавшийся в результате появления нового значения Zцикл.

X14, X24, X22, X12 образуют цикл (таблица 12).

 

 

 

 

 

 

 

Таблица 12

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

 

b=903 a=903	b1=202	b2=244	b3=223	b4=234
a1=176	0,8798	0,7278-Z	0,79	0,75Z
a2=218	1,08	0,89   166+Z	0,98	0,93      52-Z
a3=197	0,98	0,81	0,88        197	0,84
a4=208	1,03	0,85	0,9326	0,89       182
a5=104	0104	0	0	0

 

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

52 – Z≥ 0

166 + Z ≥ 0

78 – Z ≥ 0

Z ≥ 0

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

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

 

Таблица 13

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

 

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

 

Рассчитаем транспортные затраты для полученного решения: С=98*0,87 + 26*0,71 + 218*0,89 + 52*0,75 + 197*0,88 + 26*0,93 + 182*0,89 + 104*0 = 696,26  денежных единиц.

Проверим полученное решение на выполнение условия оптимальности (таблица 14).

Vj – Ui ≤ Cij

X13 :  0,79-0 = 0,79 ≤ 0,79 +

X21 : 0,87+0,17 = 1,04 ≤ 1,08 +

X23 : 0,79+0,17 = 0,96 ≤ 0,98 +

X24 : 0,75+0,17 = 0,92> 0,93 +

X31 : 0,87+0,09 = 0,96 > 0,98 +

X32 : 0,71+0,09 = 0,8 ≤ 0,81 +

X34 :0,75+0,09 = 0,84 ≤ 0,84 +

X41 : 0,87+0,14 = 1,01 ≤ 1,03 +

X42 :0,71+0,14 = 0,85≤ 0,85+

X52 : 0,72-0,87 = -0,15≤0+

X53 : 0,79-0,87 = -0,08 > 0 +

X54 : 0,75-0,87 = -0,12 ≤0 + 

 

Таблица 14

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

 

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

 

Подсчитаем транспортные затраты еще раз: С=98*0,87 + 26*0,71 + 218*0,89 + 52*0,75 + 197*0,88 + 26*0,93 + 182*0,89 + 104*0 = 696,26  денежных единиц.

Все клетки удовлетворяют условию оптимальности, а значит, мы нашли оптимальное решение данной задачи (рис. 3).

 

Рис. 3 Оптимальное решение транспортной задачи

 

Так получается, что первый поставщик доставит 98 ед. продукции первому потребителю, 26 ед. продукции – второму потребителю, 52 ед. – четвертому.

Второй поставщик доставит всю свою продукцию, все 218 ед. второму потребителю.

Третий поставщик доставит всю свою продукцию, все 197 ед. третьему потребителю.

Четвертый поставщик доставит 26 ед. продукции третьему потребителю и 182 ед. продукции – четвертому потребителю.

В процессе данных перевозок будут удовлетворены потребности всех потребителей, кроме первого. Первый будет удовлетворен на 48,5%.

При данном плане перевозок транспортные затраты буду сведены к минимуму и будут равняться 696,26  денежных единиц.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6. Использование программы QSB для решения транспортной задачи 

      

Для того чтобы найти оптимальный план можно воспользоваться подпрограммойWin QSB Networking Modeling. Введем исходные данные (рис.4)

 

 

Рис. 4 Ввод исходных данных.

 

Расшифруем обозначения, используемые в программе:

Source 1,2,3,4,5 – поставщики продукции

Destination 1,2,3,4 - потребители

Demand – потребность каждого потребителя в продукции

Supply – наличие продукции у поставщика.

Нажимаем команду «Solve the problem». Программа выдают нам следующую таблицу (рис. 5).

 

 

Рис. 5 Результат. Оптимальный план перевозок.

 

Как мы видим, транспортные затраты, найденные нами вручную и посчитанные программой, совпадают. Однако сами планы перевозок отличаются. Данный факт означает, что существует в данной задаче несколько оптимальных планов, при которых транспортные затраты минимальны. И вправду, при выполнении команды в Win QSB Networking Modeling «Obtain Alternative Solution» получаем план, еще более похожий на тот, что был найден нами ранее вручную (рис. 6).

 

 

Рис. 6 Результат. Альтернативный оптимальный план перевозок.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выводы

 

В данной расчетной работе мы исследовали и проанализировали транспортную задачу перевозки продукции. При этом мы использовали три метода: метод северо-западного угла, метод минимальной стоимости и метод потенциалов. Метод северо-западного угла и метод минимальной стоимости в исключительных случаях дают нам оптимальный план перевозок, однако с помощью них можно получить базисное невырожденное допустимое решение, которое является стартом для метода потенциалов. Что касается метода потенциалов, то, на мой взгляд, данный способ нахождения оптимального плана является очень трудоемким. Мы, прежде чем, найти оптимальное решение, применили данный метод трижды.  Поэтому, если есть возможность расчета транспортной задачи с помощью программы Win QSB, то лучше воспользоваться им, тем более, мы доказали, что транспортные затраты будут одинаковы. У программы Win QSB есть еще одно несравнимое превосходство: она может вывести несколько альтернативных оптимальных планов перевозок, поэтому при анализе он будет более предпочтителен.

Таким образом, решив предложенную нам транспортную задачу, мы получили следующие результаты: первый поставщик доставит 98 ед. продукции первому потребителю, 26 ед. продукции – второму потребителю, 52 ед. – четвертому.

Второй поставщик доставит всю свою продукцию, все 218 ед. второму потребителю.

Третий поставщик доставит всю свою продукцию, все 197 ед. третьему потребителю.

Четвертый поставщик доставит 26 ед. продукции третьему потребителю и 182 ед. продукции – четвертому потребителю.

В процессе данных перевозок будут удовлетворены потребности всех потребителей, кроме первого. Первый будет удовлетворен на 48,5%.

При данном плане перевозок транспортные затраты буду сведены к минимуму и будут равняться 696,26  денежных единиц.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы.

 

1. В.А. Кузьменков, В.Н. Юрьев Математические методы и модели исследования операций, СПб, СПбГПУ, 2011.

2. В.А. Кузьменков, В.Н. Юрьев  Методы оптимизации в экономике  и менеджменте, СПб, СПбГПУ, 2008.

3. А.Л. Кутузов Математические методы и модели исследования операций. Линейная оптимизация с помощью WINQSB и EXCEL, СПб, СПбГПУ 2009 .