Задачи линейного программирования транспортного типа - файл n1.doc

Задачи линейного программирования транспортного типа
Скачать все файлы (128.5 kb.)

Доступные файлы (1):
n1.doc129kb.31.03.2014 14:00скачать

n1.doc

ФГБОУ ВПО

Уфимский Государственный Авиационный Технический Университет
ЛАБОРАТОРНАЯ РАБОТА №2
ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ТРАНСПОРТНОГО ТИПА
Вариант №3


Выполнила:

студентка гр. ИВТ-229


Проверил:

Насыров Р.В.
Уфа-2012

Цель работы:
Изучение методов решения задач ЛП. Исследование чувствительности решения. Построение графических изображений задачи.
Задание:
1. Определить тип задачи.

2. В случае необходимости привести задачу к каноническому виду.

3. Сформулировать экономико-математическую модель задачи.

4. Построить начальное распределение перевозок методом «северо-западного» угла и найти его стоимость.

5. Построить начальное распределение перевозок методом наименьшей стоимости и найти его стоимость.

6. Построить начальное распределение перевозок методом Фогеля и найти его стоимость.

7. Выбрать из двух распределений лучшее и, начиная с него, найти решение задачи.





B1

B2

B3

B4

aij

A1

7

17

5

2

500

A2

8

10

6

9

400

A3

12

6

7

4

210

A4

5

7

9

15

80

bij

400

120

270

500






Решение:
Найти объёмы перевозок для каждой пары "поставщик - потребитель" так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех потребителей были удовлетворены;

3) суммарные затраты на перевозку были бы минимальны.

















предложение




7

17

5

2

500




8

10

6

9

400




12

6

7

4

210




5

7

9

15

80

спрос

400

120

270

500





Спрос больше предложения на 100. Добавляем фиктивное предложение:





B1

B2

B3

B4

предложение

A1

7

17

5

2

500

A2

8

10

6

9

400

A3

12

6

7

4

210

A4

5

7

9

15

80

A5

0

0

0

0

100

спрос

400

120

270

500





Решение методом "северо- западного угла":





B1

B2

B3

B4

предложение

A1

7




400

17
100

5

2

500

A2


8

10




20

6




270

9
110

400

A3

12

6

7


4
210

210

A4

5

7

9


15
80

80

A5

0

0

0

0
100

100

спрос

400

120

270

500






Общая стоимость перевозок по данному методу составляет 9350 у.е.


Метод наименьшей стоимости:





B1

B2

B3

B4

предложение

A1

7



17


5

2
500

500

A2


8




130

10



6
270

9
0

400

A3

12




90

6
120

7


4
0

210

A4

5
80

7

9


15


80

A5

0
100

0

0

0


100

спрос

400

120

270

500








Общая стоимость перевозок по данному составляет 5860 у.е.

Метод Фогеля





B1

B2

B3

B4

предложение

A1

7



17


5


2
500

500

A2


8




220

10


6




180

9


400

A3

12

6




120

7
90

4
0

210

A4

5
80

7

9


15


80

A5

0
100

0


0

0


100

спрос

400

120

270

500






Штраф по строкам:

  1. 5-2=3

  2. 8-6=2

  3. 6-4=2

  4. 7-5=2

  5. 0-0=0

Штраф по столбцам:

  1. 7-5=2

  2. 7-6=1

  3. 6-5=1

  4. 4-2=2







Общая стоимость перевозок по данному методу составляет 5590 у.е.

Найдём оптимальное решение, используя начальное решение, полученное методом Фогеля.
Значения потенциалов:


v1 + u2 = c21

v1 + u2 = 8

u2 = 8 - 0 = 8




v3 + u2 = c23

v3 + u2 = 6

v3 = 6 - 8 = -2




v3 + u3 = c33

v3 + u3 = 7

u3 = 7 - ( -2 ) = 9




v4 + u3 = c34

v4 + u3 = 4

v4 = 4 - 9 = -5




v1 + u4 = c41

v1 + u4 = 5

u4 = 5 - 0 = 5




v1 + u5 = c51

v1 + u5 = 0

u5 = 0 - 0 = 0




v4 + u1 = c14

v4 + u1 = 2

u1 = 2 - ( -5 ) = 7




v2 + u3 = c32

v2 + u3 = 6

v2 = 6 - 9 = -3







v1=0

v2=-3

v3=-2

v4=-5





u1=0


7


17


5


2
500


500


u2=8


8
220

10


6
180

9



400


u3=9


12


6
120

7
90

4
0


210


u4=5


5
80

7


9


15



80


u5=0


0
100

0


0


0



100




400

120

270

500





Значения для каждой небазисной переменной:


k11 = ( u1 + v1 ) - c11= -7 +( 7 + 0 ) = 0




k12 = ( u1 + v2 ) - c12 = -17 + ( 7 + ( -3 ) ) = -13




k13 = ( u1 + v3 ) - c13 = -5 + ( 7 + ( -2 ) ) = 0




k22 = ( u2 + v2 ) – c22 = -10 + ( 8 + ( -3 ) ) = -5




k24 = ( u2 + v4 ) – c24 = -9 + ( 8 + ( -5 ) ) = -6




k31 = ( u3 + v1 ) – c31 = -12 + ( 9 + 0 ) = -3




k42 = ( u4 + v2 ) – c42 = -7 + ( 5 + ( -3 ) ) = -5




k43 = ( u4 + v3 ) – c43 = -9 + ( 5 + ( -2 ) ) = -6




k44 = ( u4 + v4 ) – c44 = -15 + ( 5 + ( -5 ) ) = -15




k52 = ( u5 + v2 ) – c52= -0 + ( 0 + ( -3 ) ) = -3




k53 = ( u5 + v3 ) – c53 = -0 + ( 0 + ( -2 ) ) = -2




k54 = ( u5 + v4 ) - c54 = -0 + ( 0 + ( -5 ) ) = -5







v1=0

v2=-3

v3=-2

v4=-5





u1=7


7
0

17
-13

5
0

2
500


500


u2=8


8
220

10
-5

6
180

9
-6


400


u3=9


12
-3

6
120

7
90

4
0


210


u4=5


5
80

7
-5

9
-6

15
-15


80


u5=0


0
100

0
-3

0
-2

0
-5


100




400

120

270

500






Все оценки свободных ячеек неположительные, следовательно, найдено оптимальное решение.
Вывод:

В лабораторной работе была решена задача линейного программирования транспортного типа и построены начальные распределения методами северо-западного угла, наименьшей стоимости и Фогеля. Распределение методом Фогеля было выбрано как лучшее; после проверки методом потенциалов выяснилось, что решение является оптимальным.

Учебный текст
© perviydoc.ru
При копировании укажите ссылку.
обратиться к администрации