Контрольная работа: Симплекс метод решения задачи линейного программирования
Задача №1 (Симплекс метод решения задачи линейного программирования.)
Найти Fmax = 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 | |||
Изменяется базис в позиции направляющей строки. Базисным становится вектор, соответствующий направляющему столбцу, т. е.
Столбец становится базисным, то есть единичным.
Новые значения в направляющей строке получаем делением элементов этой строки на направляющий элемент.
Остальные элементы в небазисных столбцах и в столбце вычисляем по правилу треугольника.
Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец.
Заполняем столбец «θ»
По минимальному значению определяем направляющую строку.
На пересечении направляющей строки и столбца находится направляющий элемент.
Заполнение второй таблицы осуществляется по аналогии с предыдущей.
--> ЧИТАТЬ ПОЛНОСТЬЮ <--