Автор работы: Пользователь скрыл имя, 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
Таблица 14
Проверка оптимальности решения
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 |
|
Анализируемая модель содержит в себе допустимый базисный план перевозок, однако он не является оптимальным. Согласно алгоритму метода потенциалов вернемся к пункту 2. Как мы видим, одна клетка (X13) не удовлетворяют признаку оптимальности базисного невырожденного плана перевозок. Теперь согласно алгоритму метода нам необходимо устранить образовавшийся в результате появления нового значения Z цикл.
X13,X23,X33,X34,X24,X14 образуют цикл (таблица 15).
Таблица 15
Введение новой переменной Z и способ устранения образовавшего цикла
b=2143 a=2143 | b1=484 | b2=576 | b3=530 | b4=553 |
a1=426 | 0,88 252 | 0,74 58 | 0,80 Z | 0,77 116-Z |
a2=518 | 1,07 + | 0,90 518 | 0,98 + | 0,94 + |
a3=472 | 0,98 + | 0,82 + | 0,89 35-Z | 0,85 437+Z |
a4=495 | 1,02 + | 0,86 + | 0,93 495 | 0,90 + |
a5=232 | 0 232 | 0 + | 0 + | 0 + |
Чтобы сделать план базисным, надо избавиться от данного цикла, то есть Z должно быть равно min(35,116). Z = 35.
35 – Z≥ 0
437 + Z ≥ 0
35 – Z ≥ 0
Z ≥ 0
Ячейка X33 будет равна нулю. Таким образом, третий поставщик не будет поставлять продукцию третьему потребителю.
Преобразуем нашу таблицу, введем вместо Z реальное значение и устраним цикл (таблица 16).
Таблица 16
Введение вместо переменной Z реальное значение и устранение образовавшего цикла
b=2143 a=2143 | b1=484 | b2=576 | b3=530 | b4=553 |
| ||||||
a1=426 | 0,88 252 | 0,74 58 | 0,80 35 | 0,77 81 | U1= 0 | ||||||
a2=518 | 1,07 + | 0,90 518 | 0,98 + | 0,94 + | U2=-0,16
| ||||||
a3=472 | 0,98 + | 0,82 + | 0,89 + | 0,85 472 | U3=- 0,08
| ||||||
a4=495 | 1,02 + | 0,86 + | 0,93 495 | 0,90 + | U4= -0,13
| ||||||
a5=232 | 0 232 | 0 + | 0 + | 0 + | U5=0,88
| ||||||
| V1=0,88 | V2=0,74 | V3=0,80 | V4= 0,77 |
| ||||||
Рассчитаем транспортные затраты для полученного решения: С=1682,8 денежных единиц.
Проверим полученное решение на выполнение условия оптимальности (таблица 17).
Vj – Ui ≤ Cij
v1-u2 | 1,04 | 1,07 | + |
v1-u3 | 0,96 | 0,98 | + |
v1-u4 | 1,01 | 1,02 | + |
v2-u3 | 0,82 | 0,82 | + |
v2-u4 | 0,87 | 0,86 | - |
v2-u5 | -0,14 | 0,00 | + |
v3-u2 | 0,96 | 0,98 | + |
v3-u3 | 0,88 | 0,89 | + |
v3-u5 | -0,08 | 0,00 | + |
v4-u2 | 0,93 | 0,94 | + |
v4-u4 | 0,90 | 0,90 | + |
v4-u5 | -0,11 | 0,00 | + |
Таблица 17
Проверка оптимальности решения
b=2143 a=2143 | b1=484 | b2=576 | b3=530 | b4=553 |
|
a1=426 | 0,88 252 | 0,74 58 | 0,80 35 | 0,77 81 | U1= 0 |
a2=518 | 1,07 + | 0,90 518 | 0,98 + | 0,94 + | U2=-0,16
|
a3=472 | 0,98 + | 0,82 + | 0,89 + | 0,85 472 | 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 |
|
Информация о работе Решение оптимизационной задачи по грузоперевозкам