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

Автор работы: Пользователь скрыл имя, 03 Июня 2012 в 21:12, курсовая работа

Описание работы

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

Содержание работы

1. Техническое задание 4
2. Составление матричной модели транспортной задачи 6
3. Нахождение допустимых планов перевозок 8
3.1. Метод северо-западного угла 9
3.2. Метод минимальной стоимости 9
4. Проверка наилучшего найденного плана на оптимальность решения 11
5. Нахождение оптимального решения методом потенциалов 13
6. Использование программы QSB для решения транспортной задачи 19
Выводы 21
Список литературы 22

Скачать архив (118.15 Кб) Сколько стоит заказать работу?

Файлы: 1 файл

Kursovaya1эконометрика.doc

— 412.50 Кб (Скачать файл)

Рассчитаем транспортные затраты для полученного решения: С=1684 денежных единиц. Данный результат на 8 денежных единиц лучше предыдущего плана. Этот факт подтверждает то обстоятельство, что мы правильно применили метод потенциалов, тем самым уменьшив транспортные затраты.

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

Vj – Ui ≤ Cij

V1-U2	1,04	1,07	+
V1-U3	0,95	0,98	+
V1-U4	0,99	1,02	+
V2-U3	0,81	0,82	+
V2-U4	0,85	0,86	+
V2-U5	-0,14	0,00	+
V3-U1	0,82	0,80	-
V3-U2	0,98	0,98	+
V3-U5	-0,06	0,00	+
V4-U1	0,78	0,77	-
V4-U4	0,89	0,90	+
V4-U5	-0,10	0,00	+

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

Таблица 11

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

b=2143 a=2143	b1=484	b2=576	b3=530	b4=553
a1=426	0,88 252	0,74 174	0,80 -	0,77 -	U1 = 0,11
a2=518	1,07 +	0,90 402	0,98 +	0,94 116	U2 = -0,05
a3=472	0,98 +	0,82 +	0,89 35	0,85 437	U3 = 0,04
a4=495	1,02 +	0,86 +	0,93 495	0,90 +	U4 = 0
a5=232	0 232	0 +	0 +	0 +	U5 = 0,99
	V1 = 0,99	V2 = 0,85	V3 = 0,93	V4 = 0,89

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

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

Таблица 12

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

b=2143 a=2143	b1=484	b2=576	b3=530	b4=553
a1=426	0,88 252	0,74 174-Z	0,80 -	0,77 Z
a2=518	1,07 +	0,90 402+Z	0,98 +	0,94 116-Z
a3=472	0,98 +	0,82 +	0,89 35	0,85 437
a4=495	1,02 +	0,86 +	0,93 495	0,90 +
a5=232	0 232	0 +	0 +	0 +

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

174 – Z≥ 0

402 + Z ≥ 0

116 – Z ≥ 0

Z ≥ 0

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

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

Таблица 13

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

b=2143 a=2143		b1=484		b2=576		b3=530		b4=553
a1=426		0,88 252		0,74 58		0,80 -		0,77 116	U1= 0
a2=518		1,07 +		0,90 518		0,98 +		0,94 +	U2=-0,16
a3=472		0,98 +		0,82 +		0,89 35		0,85 437	U3=- 0,08
a4=495		1,02 +		0,86 +		0,93 495		0,90 +	U4= -0,12
a5=232		0 232		0 +		0 +		0 +	U5=0,88
	V1=0,88		V2=0,74		V3=0,81		V4= 0,77

Рассчитаем транспортные затраты для полученного решения: С=1683 денежных единиц.

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

Vj – Ui ≤ Cij

v1-u2	1,04	1,07	+
v1-u3	0,96	0,98	+
v1-u4	1,00	1,02	+
v2-u3	0,82	0,82	+
v2-u4	0,86	0,86	+
v2-u5	-0,14	0	+
v3-u1	0,81	0,80	-
v3-u2	0,97	0,98	+
v3-u5	-0,07	0	+
v4-u2	0,93	0,94	+
v4-u4	0,89	0,90	+
v4-u5	-0,11	0	+

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