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

Математическая модель КЗ

Математическая модель вспомогательной КЗ

Лекция 3. Метод искусственного базиса // Marina Kuzminova [1:15:30]

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

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

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

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

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

$L(X)=\sum \limits _{j=1}^{n}c_{j}x_{j}\rightarrow \max$

${\begin{cases}\sum \limits _{j=1}^{n}a_{ij}x_{j}=b_{i},\ \forall i\in N_{m}\\x_{j}\geq 0,\forall j\in N_{n}\end{cases}}$

или

$L(X)=c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}\rightarrow \max$

${\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\ldots +a_{1n}x_{n}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\ldots +a_{2n}x_{n}=b_{2}\\\ldots \\a_{m1}x_{1}+a_{m2}x_{2}+\ldots +a_{mn}x_{n}=b_{m}\\x_{1}\geq 0,\ x_{2}\geq 0,\ldots ,\ x_{n}\geq 0\end{cases}}$

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

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

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

$L^{+}(X)=\sum \limits _{i=1}^{m}x_{n+i}\rightarrow \min$

${\begin{cases}\sum \limits _{j=1}^{n}a_{ij}x_{j}+x_{n+i}=b_{i},\ \forall i\in N_{m}\\x_{j}\geq 0,\forall j\in N_{n+m}\end{cases}}$

или

$L^{+}(X)=x_{n+1}+x_{n+2}+\ldots +x_{n+m}\rightarrow \min$

${\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\ldots +a_{1n}x_{n}+x_{n+1}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\ldots +a_{2n}x_{n}+x_{n+2}=b_{2}\\\ldots \\a_{m1}x_{1}+a_{m2}x_{2}+\ldots +a_{mn}x_{n}+x_{n+m}=b_{m}\\x_{1}\geq 0,\ x_{2}\geq 0,\ldots ,\ x_{n+m}\geq 0\end{cases}}$

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

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

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

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

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

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

• Симплекс-метод;
• М-метод.

Литература

• Юдин Д. Б., Гольштейн Е. Г. Линейное программирование — М., 1963.

Ссылки

• Участник:Logic-samara