Решение оптимизационной задачи по грузоперевозкам
Курсовая работа, 03 Июня 2012, автор: пользователь скрыл имя
Описание работы
В данной расчетной работе мы исследовали и проанализировали транспортную задачу перевозки продукции. При этом мы использовали три метода: метод северо-западного угла, метод минимальной стоимости и метод потенциалов. Метод северо-западного угла и метод минимальной стоимости в исключительных случаях дают нам оптимальный план перевозок, однако с помощью них можно получить базисное невырожденное допустимое решение, которое является стартом для метода потенциалов.
Содержание работы
1. Техническое задание 4
2. Составление матричной модели транспортной задачи 6
3. Нахождение допустимых планов перевозок 8
3.1. Метод северо-западного угла 9
3.2. Метод минимальной стоимости 9
4. Проверка наилучшего найденного плана на оптимальность решения 11
5. Нахождение оптимального решения методом потенциалов 13
6. Использование программы QSB для решения транспортной задачи 19
Выводы 21
Список литературы 22
Файлы: 1 файл
Kursovaya1эконометрика.doc
— 412.50 Кб (Скачать файл)
Таблица 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 |
|