Реферат: Симплекс метод решения задачи линейного программирования
Задача №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 | 48 | |||||
3 | 108 | - | 1 | 72 | |||||
∆j | 384 | 3 | -2 | 2 | |||||
Zj | 384 | 12 | 8 | 2 |
Изменяется базис в позиции направляющей строки. Базисным становится вектор, соответствующий направляющему столбцу, т. е.
Столбец становится базисным, то есть единичным.
Новые значения в направляющей строке получаем делением элементов этой строки на направляющий элемент.
Остальные элементы в небазисных столбцах и в столбце вычисляем по правилу треугольника.
Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец.
Заполняем столбец «θ»
По минимальному значению определяем направляющую строку.
На пересечении направляющей строки и столбца находится направляющий элемент.
Заполнение второй таблицы осуществляется по аналогии с предыдущей.
Таблица 2.
9 | 10 | 16 | Отношение, θ | ||||||
i | Базис | ||||||||
1 | 10 | 8 | 1 | 1 | - | ______ | |||
2 | 16 | 20 | 1 | - | ______ | ||||
3 | 96 | - | 1 | ______ | |||||
∆j | 400 | 5 | |||||||
Zj | 400 | 14 | 10 | 16 |
Так как нет отрицательных оценок ∆j, значит выполняется признак оптимальности и не вводились искусственные переменные, то получено оптимальное решение.
Ответ:
Максимальное значение функции Fmax =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 | ∞ | 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)
Шаг 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 | ∞ | |||
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
это и есть кратчайший путь.