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


Полнотекстовый поиск по базе:

Главная >> Контрольная работа >> Информатика, программирование


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




Задача №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

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

Похожие работы: