Венгерский метод решения задач линейного программирования о назначении

Автор работы: Пользователь скрыл имя, 17 Марта 2012 в 13:23, курсовая работа

Краткое описание

Данная курсовая работа предусматривает выполнение теоретической и практической части.
Практическая часть содержит решение задачи линейного программирования с использованием математических методов. Ручной просчет задачи подтверждается машинным вариантом, реализованным на ПЭВМ Intel Pentium IV под управлением операционной системы Windows XP с использованием табличного процессора Microsoft Excel.

Содержание работы

1. Теоретическая часть 4
2. Практическая часть 8
2.1. Постановка задачи 8
2.2. Решение задачи 9
2.3. Экономическая интерпретация 11
3. Список литературы 12
4. Приложения

Содержимое работы - 12 файлов

1 Титульник.doc

— 25.50 Кб (Открыть файл, Скачать файл)

2 аннотация.doc

— 39.00 Кб (Открыть файл, Скачать файл)

3 Содержание.doc

— 41.00 Кб (Открыть файл, Скачать файл)

4 теоретическая часть.doc

— 41.50 Кб (Открыть файл, Скачать файл)

5 постановка задачи.doc

— 46.50 Кб (Открыть файл, Скачать файл)

6 решение задачи.doc

— 83.00 Кб (Скачать файл)


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+130*5 = 4020

                            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



Так как среди оценок свободных клеток нет отрицательных, то решение оптимально.

 



7 экономическая интерпритация.doc

— 36.50 Кб (Открыть файл, Скачать файл)

8 Список литературы.doc

— 40.50 Кб (Открыть файл, Скачать файл)

задача0.xls

— 28.50 Кб (Открыть файл, Скачать файл)

Приложение А.doc

— 37.50 Кб (Открыть файл, Скачать файл)

Приложение В.doc

— 46.00 Кб (Открыть файл, Скачать файл)

Приложение С.doc

— 36.50 Кб (Открыть файл, Скачать файл)

Информация о работе Венгерский метод решения задач линейного программирования о назначении