Курсовая работа: Симплекс метод решения задачи линейного программирования
Задача №1 (Симплекс метод решения задачи линейного программирования.)
Найти Fmax = 9x1+ 10x2 + 16x3, при ограничениях:
/>
Запишем задачу в каноническом виде:
F=9x1+ 10x2 + 16x3 → max
/>
Заполним начальную таблицу:
/>
Таблица 0.
9
10
16
Отношение,
θ
i
/>
Базис
/>
/>
/>
/>
/>
/>
/>
1
/>
360
18
15
12
1
30
2
/>
192
6
4
8
1
24
3
/>
180
5
3
3
1
60
∆j
-9
-10
-16
Zj
Zj вычисляется по формуле />
Оценки (∆j) вычисляются по формуле />, где /> — коэффициент из первой строки таблицы.
Выбираем минимальную (отрицательную) оценку. Она определяет направляющий столбец.
Заполняем столбец «θ», по минимальному значению определяем направляющую строку.
На пересечение строки и столбца находится направляющий элемент.
Заполняем новую таблицу
Таблица 1.
9
10
16
Отношение,
θ
i
/>
Базис
/>
/>
/>
/>
/>
/>
/>
1
/>
72
9
9
1
/>
8
2
16
/>
24
/>
/>
1
/>
--PAGE_BREAK----PAGE_BREAK--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
∞
30,61
32,99
61,64
78,55
2
∞
13,19
15,61
46,28
65,14
3
17,72
0,30
∞
29,43
51,44
4
20,10
2,72
∞
0,38
21,39
5
58,37
43,01
39,05
10,00
∞
6
75,28
61,87
61,06
31,01
∞
↓
1
2
3
4
5
6
1
∞
30,61
32,99
61,64
78,55
2
∞
13,19
15,61
46,28
65,14
3
17,72
0,30
∞
29,43
51,44
4
20,10
2,72
∞
0,38
21,39
5
58,37
43,01
39,05
10,00
∞
6
75,28
61,87
61,06
31,01
∞
Шаг 2. Определим оценки нулевых клеток:
/>/>
/>/>
/>/>
Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (5 – 6)
/>
продолжение--PAGE_BREAK--
Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6-5 ставим ∞).
1
2
3
4
5
1
∞
30,61
32,99
61,64
2
∞
13,19
15,61
46,28
3
17,72
0,30
∞
29,43
4
20,10
2,72
∞
0,38
6
75,28
61,87
61,06
31,01
∞
Далее повторяем шаги 1 – 4, пока не дойдем до одной клетки.
Второй этап.
Шаг 1. Приведем матрицу расстояний по строкам и столбцам.
1
2
3
4
5
1
∞
30,61
32,99
61,64
2
∞
13,19
15,61
46,28
3
17,72
0,30
∞
29,43
4
20,10
2,72
∞
0,38
6
75,28
61,87
61,06
31,01
∞
0,38
↓
1
2
3
4
5
1
∞
30,61
32,99
61,26
2
∞
13,19
15,61
45,90
3
17,72
0,30
∞
29,05
4
20,10
2,72
∞
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
∞
29,05
4
20,10
∞
6
75,28
61,06
31,01
∞
Третий этап.
Шаг 1. Приведем матрицу расстояний по строкам и столбцам.
1
3
4
5
2
∞
13,19
15,61
45,90
3
17,72
∞
29,05
4
20,10
∞
6
75,28
61,06
31,01
∞
17,72
↓
1
3
4
5
2
∞
13,19
15,61
45,90
13,19
3
∞
29,05
4
2,38
продолжение--PAGE_BREAK--
∞
6
57,56
61,06
31,01
∞
31,01
↓
1
3
4
5
2
∞
2,42
32,71
3
∞
29,05
4
2,38
∞
6
26,55
30,05
∞
Шаг 2. Определим оценки нулевых клеток:
/>
/>/>
/>/>
Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (4 – 5)
/>
Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 4 ставим ∞).
1
3
4
2
∞
2,42
3
∞
6
26,55
30,05
∞
Четвертый этап.
Шаг 1. Приведем матрицу расстояний по строкам и столбцам.
1
3
4
2
∞
2,42
3
∞
6
26,55
30,05
∞
26,55
↓
1
3
4
2
∞
2,42
3
∞
6
3,50
∞
Шаг 2. Определим оценки нулевых клеток:
/>
Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (3 – 4)
/>
Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 – 3 ставим ∞).
1
3
2
∞
6
∞
Пятый этап.
Остались не задействованными связи 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
это и есть кратчайший путь.
/>