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