Автор: Пользователь скрыл имя, 30 Января 2011 в 13:10, курсовая работа
Данная курсовая работа предусматривает выполнение теоретической и практической части.
Практическая часть содержит решение задачи линейного программирования с использованием математических методов. Ручной просчет задачи подтверждается машинным вариантом, реализованным на ПЭВМ Intel Pentium IV под управлением операционной системы Windows XP с использованием табличного процессора Microsoft Excel.
1. Теоретическая часть 4
2. Практическая часть 8
2.1. Постановка задачи 8
2.2. Решение задачи 9
2.3. Экономическая интерпретация 11
3. Список литературы 12
4. Приложения
2.2 Решение задачи
1. Определим модель задачи:
∑ ai = ∑ bj , следовательно модель открытая, добавлять фиктивных получателей не нужно.
2. Распределим груз по методу min элемента
| V1=2 | V2=3 | V3=0 | |||
| ai
bi |
450 | 370 | 400 | ||
| U1= | 0 | 320 | 170 2 | 150 3 | 4 |
| U2= | -1 | 280 | 280 1 | 5 | 3 |
| U3= | 2 | 270 | 6 | +λ 4 | -λ 270 2 |
| U4= | 5 | 350 | 7 | -λ 220 8 | +λ 130 5 |
3. Определим первоначальную стоимость перевозки груза
Z = 170*2+150*3+280*1+270*2+220*8+
4. Определим потенциал для занятых клеток, исходя из условия
U1 принимаем за 0
V1 = 2-0=2
V2 = 3-0=3
U2 = 1-2=-1
U4 = 8-3=5 и т.д.
5.
Определим потенциал для
Δe
= Сij-(Ui+Vi)
Δ 13=4-(0+0)=4
Δ22=5-(-1+3)=3
Δ23=3-(-1+0)=4
Δ31=6-(2+2)=-3
Δ32=4-(2+3)=-1
Δ41=7-(5+2)=0
Так как среди оценок свободных клеток есть отрицательная, то решение не оптимально. Перейдем к другой итерации.
6. Построим цикл по λ
λ=min(220;270)=220
| V1=2 | V2=3 | V3=1 | |||
| ai
bi |
450 | 370 | 400 | ||
| U1= | 0 | 320 | 170 2 | 150 3 | 4 |
| U2= | -1 | 280 | 280 1 | 5 | 3 |
| U3= | 1 | 270 | 6 | 220 4 | 50 2 |
| U4= | 4 | 350 | 7 | 8 | 350 5 |
7. Определим стоимость перевозки груза
Z2 = 4020-|-1|*220=3800
Повторяя
алгоритм метода потенциалов, определим
потенциал для заняты клеток Ui и
Vi, а затем оценки свободных клеток.
Δ13=4-(0+1)=3
Δ23=5-(-1+3)=3
Δ24=3-(-1+1)=3
Δ31=6-(1+2)=3
Δ41=7-(4+2)=1
Δ42=8-(4+3)=1
Так как среди оценок свободных клеток нет отрицательных, то решение оптимально.
Информация о работе Венгерский метод решения задач линейного программирования о назначении