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