Автор работы: Пользователь скрыл имя, 27 Февраля 2013 в 08:40, курсовая работа
Задача, решаемая в данной работе, относится к классу оптимизационных, функционал которой имеет экстремум. Поиск экстремума заключается в выборе оптимального варианта из множества вариантов прикрепления пунктов отправления и назначения грузов. Предполагается, что на всех направлениях осуществляются перевозки однородного груза.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ВОДНЫХ КОММУНИКАЦИЙ»
ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ
Курсовая работа
на тему: " Оптимизация доставки грузов и план выпуска промышленной продукции"
Вариант №16
Исполнитель:
студент группы ЭУс/с, 4ый курс
Руководитель:
Санкт-Петербург
2012 г.
1. Оптимизация доставки грузов.
Задача, решаемая в данной работе, относится к классу оптимизационных, функционал которой имеет экстремум. Поиск экстремума заключается в выборе оптимального варианта из множества вариантов прикрепления пунктов отправления и назначения грузов. Предполагается, что на всех направлениях осуществляются перевозки однородного груза.
Необходимо решить задачу связи пунктов отправления и назначения, обеспечив вывоз всех грузов из пункта отправления, ввоз во все пункты назначения требуемых объемов грузов и достижения минимального суммарного грузооборота.
Таблица1
Пункты отправления |
Объемы вывоза, тыс. тонн |
А1 |
330 |
А2 |
240 |
А3 |
290 |
Таблица2
Пункты назначения |
Объемы ввоза, тыс. тонн |
В1 |
220 |
В2 |
310 |
В3 |
100 |
В4 |
150 |
В5 |
80 |
Таблица3
Расстояния между пунктами, км | |
А1-В1 |
215 |
А1-В2 |
280 |
А1-В3 |
250 |
А1-В4 |
300 |
А1-В5 |
150 |
А2-В1 |
235 |
А2-В2 |
285 |
А2-В3 |
220 |
А2-В4 |
105 |
А2-В5 |
230 |
А3-В1 |
250 |
А3-В2 |
300 |
А3-В3 |
210 |
А3-В4 |
300 |
А3-В5 |
250 |
Задача: для выпуска четырех видов продукции требуются запасысырья, рабочего времени и оборудования. Необходимо сформулировать экономико-математическую модель задачи на максимум прибыли найти оптимальный план выпуска продукции.
Таблица11
Тип ресурса |
Нормы затрат ресурсов на единицу продукции |
Запасы ресурсов | |||
1 |
2 |
3 |
4 | ||
Сырье |
7 |
5 |
3 |
6 |
70 |
Рабочее время |
24 |
15 |
20 |
18 |
500 |
Оборудование |
12 |
16 |
9 |
18 |
150 |
Прибыль на единицу продукции |
32 |
27 |
10 |
18 |
|
Искомая переменная:
Х-количество выпускаемой продукции
Целевая функция:
Z=ПX1+ПX2+ПX3+ПX4→max
Z= 32Х1+27Х2+10Х3+18Х4→max
Ограничения:
Так как в ограничениях нашей задачи левая часть меньше или равна правой, то наравенства мы преобразуем в равенства (кроме первого) путем добавления свободных переменных, коэффициент которых равен 1.
Х5—неиспользованное сырье
Х6—неиспользованное время
Х7—неиспользуемое оборудование.
С экономической точки зрения свободные переменные представляют собой неиспользованные ресурсы, поэтому их цена в целевой функции равна 0.
Коэффициенты при свободных переменных образуют единичную матрицу, определитель которой равен 1. Векторы, составленные из коэффициентов при свободных переменных образуют базис
Таблица12
Cj |
32 |
27 |
10 |
18 |
0 |
0 |
0 | ||
Ci |
Базис |
P0 |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
0 |
X5 |
70 |
7 |
5 |
3 |
6 |
1 |
0 |
0 |
0 |
X6 |
500 |
24 |
15 |
20 |
18 |
0 |
1 |
0 |
0 |
X7 |
150 |
12 |
16 |
9 |
18 |
0 |
0 |
1 |
Zj |
0 |
0 |
0 |
0 |
0 |
0 |
0 | ||
Zj-Cj |
-32 |
-27 |
-10 |
-18 |
0 |
0 |
0 | ||
Z=0*70+0*450+0*300=0
Zj-Cj—признак оптимальности в симплекс таблице. Если задача решается на максимум, то план явуляется оптимальным, если Zj-Cj ≥0
1) План1
а) Определяем вектор (столбец), который вводится в базис. Это вектор с максимальным нарушением оптимальности (по модулю). Индекс ключевого столбца-k
max 32;27;10;18;0;0;0 =32 ключевой столбец—Х1
б) Определяем вектор (строку), который
выводится из базиса. Это строка,
в которой имеет место
Θ=min , Xik >0
Xi—вектор решения
Xik—число, стоящее на пересечении i-ой строки и ключевого столбца
Инднекс ключевой стоки-r. Элемент таблицы, находящийся на пересечении ключевого столбца и ключевой строки, называется генеральным, и обозначается Xrk
Θ=min =10 ключевая строка—Х5
в) Рассчитываем новые значения вектора решений
X′i=Xi—Θik*Xik
Правило1: для ключевой строки новое значение вектора решений не рассчитывается, а просто берется, как значение Θ.
X′5=Θ=14 (см.правило1)
X′6=500-10*24=260
X′7=150-10*12=30
г) Определяем новые значения ключевой строки
X′rj=Xrj÷Xrk
Правило2: каждый столбец, у которого на пересечении с ключевой строкой стоит 0, переписывается без изменений.
Правило3: в новой симплекс-таблице значения элементов ключевого столбца будут равны 0, а на месте генерального элемента будет стоять 1.
Правило4: каждая строка, у которой на пересечении с ключевым столбцом стоит 0, переписывается без изменений.
X′11=1 (см.правило 3)
X′12=5/7=0,7
X′13=3/7=0,4
X′14=6/7=0,9
X′15=1/7= 0,1
X′16=0 (см.правило2)
X′17=0 (см.правило2)
д) Находим значения остальных элементов новой симплекс-таблицы:
X′ij=Xij- Xrj*Xik/Xrk
X′61=0 (см.правило2)
X′71=0 (см.правило2)
X′62=15-5*24/7=-2,2
X′63=20-3*24/7=9,8
X′64=18-6*24/7=-2,4
X′65=0-1*24/7=-3,4
X′72=16-5*12/7=7,5
X′73=9-3*12/7=3,9
X′74=18-6*12/7=7,8
X′75=0-1*12/7=-1,7
X′66=1 (см.правило2)
X′76=0 (см.правило2)
X′67=0 (см.правило2)
X′77=1 (см.правило2)
е) Определяем значения Zj
Zj=
C1=32, C6=0,C7=0
Z1=32*1+0+0=32
Z2=32*0,7+0+0=22,4
Z3=32*0,4+0+0=12,8
Z4=32*0,9+0+0=28,8
Z5=32*0,1+0+0=3,2
Z6=32*0+0+0=0
Z7=32*0+0+0=0
Таблица13
Cj |
32 |
27 |
10 |
18 |
0 |
0 |
0 | ||
Ci |
Базис |
P0 |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
32 |
X1 |
10 |
1 |
0,7 |
0,4 |
0,9 |
0,1 |
0 |
0 |
0 |
X6 |
260 |
0 |
-2,2 |
9,8 |
-2,4 |
-3,4 |
1 |
0 |
0 |
X7 |
30 |
0 |
7,5 |
3,9 |
7,8 |
-1,7 |
0 |
1 |
Zj |
32 |
22,4 |
12,8 |
28,8 |
3,2 |
0 |
0 | ||
Zj-Cj |
0 |
-1,6 |
2,8 |
10,8 |
3,2 |
0 |
0 | ||
Z=32*10+0*260+0*30=320 у.д.е
Признак оптимальности нарушен!
2) План2.
а) Ключевой столбец- Х2
б) Θ=min =4 ключевая строка—Х7
в) Рассчитываем новые значения вектора решений
X′i=Xi—Θik*Xik
X′1=10-4*0,7=7
X′6=260-4*7,5=230
г) Определяем новые значения ключевой строки
X′rj=Xrj÷Xrk
X′71=0 (см.правило 4)
X′73=3,9/7,5 = 0,52
X′72=1 (см. правило 3)
X′74=7,8/7,5=1,04
X′75=-1,7/7,5=-0,2
X′76=1 / 7,5 = 0,13
X′77=0 (см.правило2)
д) Находим значения остальных элементов новой симплекс-таблицы:
X′ij=Xij- Xrj*Xik/Xrk
X′13=0,4-3,9*0,7/7,5=0,04
X′14=0,9-7,8*0,7/7,5=0,2
X′15=0,1-(-1,7)* 0,7/7,5=0,25
X′17=0-1*0,7/7,5=-0,09
X′63=9,8-3,9*(-2,2)/7,5=10,97
X′64=-2,4-7,8*(-2,2)/7,5=-0,6
X′65=-3,4-(-1,7)* (-2,2)/7,5=-3,9
X′67=0-(-2,2)/7,5=0,3
е) Определяем значения Zj
Zj=
C1=32, C2=27,C6=0
Z1=32
Z2=27
Z3=32*0,04+27*0,52=15,32
Z4=32*0,2+27*1,04=34,48
Z5=32*0,25+27*(-0,2)=2,6
Z6=0
Z7=32*(-0,09)+25*0,13=0,37
Таблица14
Cj |
31 |
27 |
10 |
18 |
0 |
0 |
0 | ||
Ci |
Базис |
P0 |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
32 |
X1 |
7 |
1 |
0 |
0,04 |
0,2 |
0,25 |
0 |
-0,09 |
0 |
X6 |
230 |
0 |
0 |
10,97 |
-0,6 |
-3,9 |
1 |
0,3 |
27 |
X2 |
4 |
0 |
1 |
0,52 |
1,04 |
-0,2 |
0 |
0,13 |
Zj |
32 |
27 |
15,32 |
34,48 |
2,6 |
0 |
0,37 | ||
Zj-Cj |
0 |
0 |
5,32 |
16,48 |
2,6 |
0 |
0,37 | ||
Информация о работе Оптимизация доставки грузов и план выпуска промышленной продукции