Метод искусственного базиса

Материал из ALL
Перейти к: навигация, поиск
Математическая модель вспомогательной КЗ

Метод искусственного базиса — это метод нахождения опорного решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств.

Описание метода

Суть метода искусственного базиса состоит в построении вспомогательной задачи с базисом и переходе к новому базису, подходящему для исходной задачи.

Каноническая задача

Математическая модель канонической задачи имеет следующий вид:

СМ01.JPG

или

СМ02.JPG

Постановка вспомогательной задачи

Для нахождения опорного решения задачи канонического вида необходимо составить вспомогательную задачу. Введём новые (искусственные) переменные xj – остатки ресурсов (j-n)-го ограничения, j=n+1,n+2,…,n+m. Добавим эти переменные к соответствующим ограничениям, введём новую целевую функцию равную сумме остатков ресурсов ограничений, в результате получим вспомогательную задачу.

Математическая модель вспомогательной задачи имеет следующий вид:

МИБ01.JPG.

или

МИБ02.JPG

Метод решения

Вспомогательная задача решается симплекс-методом.

Начальная симплекс-таблица для вспомогательной задачи имеет вид: МИБ03.JPG

Если оптимальное значение целевой функции вспомогательной задачи равно нулю, то получено решение, которое при отбрасывании искусственных переменных совпадает с опорным решением исходной задачи канонического вида, причём расширенная матрица коэффициентов симплекс-таблицы вспомогательной задачи в части без искусственных переменных совпадает с расширенной матрицей коэффициентов симплекс-таблицы исходной задачи. Далее, заменив в симплекс-таблице коэффициенты целевой функции на значения исходной задачи и пересчитав значения оценок Δj, можно решать исходную задачу симплекс-методом. В случае если оптимальное значение целевой функции вспомогательной задачи не равно нулю, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений.

Другие методы:

Ссылки