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

Задача №1 (Симплекс метод решения задачи линейного программирования.)



Найти F max = 9x1+ 10x2 + 16x3, при ограничениях:







Запишем задачу в каноническом виде:



F=9x1+ 10x2 + 16x3 → max





Заполним начальную таблицу:







Таблица 0.





0

9

10

16

0

0

0

Отношение,

θ

i



Базис

















1

0



360

18

15

12

1

0

0

30

2

0



192

6

4

8

0

1

0

24

3

0



180

5

3

3

0

0

1

60



∆j

0

-9

-10

-16

0

0

0





Zj

0

0

0

0

0

0

0





Zj вычисляется по формуле 

Оценки (∆j) вычисляются по формуле , где  - коэффициент из первой строки таблицы.

Выбираем минимальную (отрицательную) оценку. Она определяет направляющий столбец.

Заполняем столбец «θ», по минимальному значению определяем направляющую строку.

На пересечение строки и столбца находится направляющий элемент. 



Заполняем новую таблицу 



Таблица 1.





0

9

10

16

0

0

0

Отношение,

θ

i



Базис

















1

0



72

9

9

0

1



0

8

2

16



24





1

0



0

48

3

0



108





0

0

-

1

72



∆j

384

3

-2

0

0

2

0





Zj

384

12

8

0

0

2

0





Изменяется базис в позиции направляющей строки. Базисным становится вектор, соответствующий направляющему столбцу, т. е. 

Столбец  становится базисным, то есть единичным.

Новые значения в направляющей строке получаем делением элементов этой строки на направляющий элемент.

Остальные элементы в небазисных столбцах и в столбце  вычисляем по правилу треугольника.

Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец.

Заполняем столбец «θ»

По минимальному значению определяем направляющую строку.

На пересечении направляющей строки и столбца находится направляющий элемент.

Заполнение второй таблицы осуществляется по аналогии с предыдущей.



Таблица 2.



0

9

10

16

0

0

0

Отношение,

θ

i



Базис

















1

10



8

1

1

0



-

0

______

2

16



20



0

1

-



0

______

3

0



96



0

0



-

1

______



∆j

400

5

0

0





0





Zj

400

14

10

16





0





Так как нет отрицательных оценок ∆j, значит выполняется признак оптимальности и не вводились искусственные переменные, то получено оптимальное решение.

Ответ:

Максимальное значение функции F max =400 достигается в точке с координатами:



=0 

=8

=20

=0

=0

=96



Задача №2 (Метод Литтла)



Найти кратчайший путь в графе, заданном графически в виде чертежа, методом Литтла. 





Из чертежа запишем матрицу расстояний. (Расстояние от т.1 до т.2 равно:

 , и т.д.)





1

2

3

4

5

6

1

∞

18,87

49,48

51,86

80,51

97,42

2

18,87

∞

32,06

34,48

65,15

84,01

3

49,48

32,06

∞

31,76

61,19

83,20

4

51,86

34,48

31,76

∞

32,14

53,15

5

80,51

65,15

61,19

32,14

∞

22,14

6

97,42

84,01

83,20

53,15

22,14

∞



Предположим что кратчайший путь будет следующим:



 т.1→ т.2→ т.3→ т.4→ т.5→ т.6→т.1 и составит 







Решение: Первый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам

(в строке вычитаем из каждого элемента минимальный, затем в столбцах)






1

2

3

4

5

6



1

∞

18,87

49,48

51,86

80,51

97,42

18,87

2

18,87

∞

32,06

34,48

65,15

84,01

18,87

3

49,48

32,06

∞

31,76

61,19

83,20

31,76

4

51,86

34,48

31,76

∞

32,14

53,15

31,76

5

80,51

65,15

61,19

32,14

∞

22,14

22,14

6

97,42

84,01

83,20

53,15

22,14

∞

22,14

 						 ↓



1

2

3

4

5

6

1

∞

0

30,61

32,99

61,64

78,55

2

0

∞

13,19

15,61

46,28

65,14

3

17,72

0,30

∞

0

29,43

51,44

4

20,10

2,72

0

∞

0,38

21,39

5

58,37

43,01

39,05

10,00

∞

0

6

75,28

61,87

61,06

31,01

0

∞



0

0

0

0

0

0

 ↓



1

2

3

4

5

6

1

∞

0

30,61

32,99

61,64

78,55

2

0

∞

13,19

15,61

46,28

65,14

3

17,72

0,30

∞

0

29,43

51,44

4

20,10

2,72

0

∞

0,38

21,39

5

58,37

43,01

39,05

10,00

∞

0

6

75,28

61,87

61,06

31,01

0

∞



Шаг 2. Определим оценки нулевых клеток:



	

	

	



Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (5 – 6)





Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6-5 ставим ∞).





1

2

3

4

5

1

∞

0

30,61

32,99

61,64

2

0

∞

13,19

15,61

46,28

3

17,72

0,30

∞

0

29,43

4

20,10

2,72

0

∞

0,38

6

75,28

61,87

61,06

31,01

∞



Далее повторяем шаги 1 – 4, пока не дойдем до одной клетки.



Второй этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.





1

2

3

4

5

1

∞

0

30,61

32,99

61,64

2

0

∞

13,19

15,61

46,28

3

17,72

0,30

∞

0

29,43

4

20,10

2,72

0

∞

0,38

6

75,28

61,87

61,06

31,01

∞



0

0

0

0

0,38

 					 ↓



1

2

3

4

5

1

∞

0

30,61

32,99

61,26

2

0

∞

13,19

15,61

45,90

3

17,72

0,30

∞

0

29,05

4

20,10

2,72

0

∞

0

6

75,28

61,87

61,06

31,01

∞



Шаг 2. Определим оценки нулевых клеток:



	



	



Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (1 – 2)







Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 2 – 1 ставим ∞).





1

3

4

5

2

∞

13,19

15,61

45,90

3

17,72

∞

0

29,05

4

20,10

0

∞

0

6

75,28

61,06

31,01

∞



Третий этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.



1

3

4

5

2

∞

13,19

15,61

45,90

3

17,72

∞

0

29,05

4

20,10

0

∞

0

6

75,28

61,06

31,01

∞



17,72

0

0

0

 				 ↓



1

3

4

5



2

∞

13,19

15,61

45,90

13,19

3

0

∞

0

29,05

0

4

2,38

0

∞

0

0

6

57,56

61,06

31,01

∞

31,01

 				 ↓



1

3

4

5

2

∞

0

2,42

32,71

3

0

∞

0

29,05

4

2,38

0

∞

0

6

26,55

30,05

0

∞



Шаг 2. Определим оценки нулевых клеток:





	

		


Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (4 – 5)







Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 4 ставим ∞).





1

3

4

2

∞

0

2,42

3

0

∞

0

6

26,55

30,05

∞



Четвертый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.





1

3

4



2

∞

0

2,42

0

3

0

∞

0

0

6

26,55

30,05

∞

26,55

 ↓



1

3

4

2

∞

0

2,42

3

0

∞

0

6

0

3,50

∞



Шаг 2. Определим оценки нулевых клеток:







Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (3 – 4)







Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 3 ставим ∞).






1

3

2

∞

0

6

0

∞

 

Пятый этап.

Остались не задействованными связи 2 – 3 и 6 – 1.

В результате получаем следующую цепочку: 



1→ 2→ 3 → 4→ 5→ 6 →1



Длина пути составляет: 



L=18,87+32,06+31,76+32,14+22,14+97,42=234,39 



это и есть кратчайший путь.