Автор работы: Пользователь скрыл имя, 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
Анализируемая модель содержит в себе допустимый базисный план перевозок, однако он не является оптимальным. Согласно алгоритму метода потенциалов вернемся к пункту 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).
Информация о работе Решение оптимизационной задачи по грузоперевозкам