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

Материал из Циклопедии
Перейти к: навигация, поиск
Математическая модель вспомогательной КЗ
Лекция 3. Метод искусственного базиса // Marina Kuzminova [1:15:30]

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

Содержание

[править] Описание метода

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

[править] Каноническая задача

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

[math]L(X) = \sum\limits_{j=1}^n c_jx_j \rightarrow \max[/math]
[math]\begin{cases}\sum\limits_{j=1}^n a_{ij}x_j=b_i, \ \forall i\in N_m \\ x_j \ge 0, \forall j\in N_n\end{cases}[/math]

или

[math]L(X) = c_1x_1 + c_2x_2 + \ldots + c_nx_n \rightarrow \max[/math]
[math]\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 \ge 0, \ x_2 \ge 0, \ldots, \ x_n \ge 0 \end{cases}[/math]

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

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

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

[math]L^+(X) = \sum\limits_{i=1}^m x_{n+i} \rightarrow \min[/math]
[math]\begin{cases}\sum\limits_{j=1}^n a_{ij}x_j + x_{n+i} =b_i, \ \forall i\in N_m \\ x_j \ge 0, \forall j\in N_{n+m}\end{cases}[/math]

или

[math]L^+(X) = x_{n+1} + x_{n+2} + \ldots + x_{n+m} \rightarrow \min[/math]
[math]\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 \ge 0, \ x_2 \ge 0, \ldots, \ x_{n+m} \ge 0 \end{cases}[/math]

[править] Метод решения

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

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

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

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

[править] Другие методы

[править] Литература

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

[править] Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты