Метод искусственного базиса
Решение задачи линейного программирования симплекс-методом начинается с нахождения какого-либо опорного плана. До сих пор такой план находился приведением системы ограничительных уравнений к единичному базису. Рассмотрим другой метод построения начального плана.
Метод искусственного базиса применяется для решения задач линейного программирования в случае, когда задача не имеет начального опорного решения с базисом из единичных векторов.
Согласно данному методу для задачи линейного программирования составляется так называемая расширенная задача, которая решается симплексным методом. На основе результатов решения расширенной задачи либо находится оптимальное решение исходной задачи, либо устанавливается причина его отсутствия.
Искусственными переменными называют неотрицательные переменные, которые вводятся в ограничения-равенства для получения начального опорного решения с базисом из единичных векторов. Каждая искусственная переменная вводится в левую часть одного из уравнений системы ограничений с коэффициентом +1 и в целевую функцию в задаче на минимум с коэффициентом +М, а в задаче на максимум с коэффициентом –М, число М сколь угодно большое по сравнению с единицей.
Пусть задача записана в канонической форме:
Рассмотрим расширенную задачу, составленную на основе предыдущей
следующим образом. Предполагая в равенствах
,
введем в каждое из уравнений по одной неотрицательной переменной
(будем называть их искусственными), а из
целевой функции вычтем сумму искусственных переменных, умноженную на сколь
угодно большое положительное число M. В результате получим так называемую M-задачу.
В этой системе переменные
образуют базис, называемый искусственным. При
получаем начальный опорный план
M-задачи.
Получением оптимального плана исходной задачи основано на следующих утверждениях:
1) если в оптимальном плане M-задачи все искусственные переменные
,
то есть
,
то план
является оптимальным планом исходной задачи.
2) если в оптимальном плане M-задачи по крайней мере одна из искусственных переменных положительна при любом большом M, то исходная задача не имеет ни одного плана;
3) если M-задача не имеет решения, то и исходная задача неразрешима.
При решении задачи линейного программирования методом искусственного базиса искусственные переменные следует вводить лишь в те уравнения, которые не разрешены относительно естественных базисных переменных.
Целевая функция
состоит из двух слагаемых:
и
,
поэтому в симплексных таблицах для нее удобнее отводить две строки: одну для
,
другую для
.
Если преобразования выполняются с двумя строками, то признак оптимальности
проверяется сначала по второй строке. По ней же определяется переменная,
подлежащая включению в базис. Процесс симплекс - преобразований продолжают до
тех пор, пока из базиса не будут исключены все искусственные переменные. По мере исключения из базиса этих переменных
соответствующие столбцы элементов можно опускать. Объясняется это тем, что
искусственные переменные в базис больше не возвращают, а поэтому отвечающие им
столбцы больше не потребуются. После исключения из базиса всех искусственных
переменных процесс отыскания оптимального плана продолжают с использованием
первой строки целевой функции.
Если в исходной задаче нужно целевую функцию минимизировать, то в M-задаче целевая функция будет иметь вид:
и также минимизируется.
Задача 1
Решить задачу линейного программирования методом искусственного базиса.
Решение
Ограничение имеет предпочтительный вид, если при неотрицательности правой части левая часть имеет
переменную, входящую с коэффициентом, равным единице, а остальные
ограничения-равенства - с коэффициентом, равным нулю. В нашем случае 1-е, 3-е
ограничения имеют предпочтительный вид с соответствующими базисными переменными
.
2-е ограничение не имеет предпочтительного вида, поэтому для него вводим
искусственную переменную
.
В целевую функцию искусственную переменную введем с коэффициентом
,
где
- большое положительное число. Получили M-задачу,
которая всегда имеет предпочтительный вид.
Заполняем симплексную таблицу 0-й итерации.
| БП |
|
|
|
|
|
|
|
|
|
Симплексные отношения |
| 1 | -1 | 1 | 1 | 1 | -1 | M | ||||
|
|
1 | 9 | 1 | 0 | 0 | 1 | 0 | 6 | 0 | 9 |
|
|
M | 2 | 3 | 1 | -4 | 0 | 0 | 2 | 1 | 2/3 |
|
|
1 | 6 | 1 | 2 | 0 | 0 | 1 | 2 | 0 | 6 |
|
15 | 1 | 3 | -1 | 0 | 0 | 9 | 0 | ||
| 2M | 3M | M | -4M | 0 | 0 | 2M | 0 | |||
Так как мы решаем задачу на минимум – наличие в индексной строке положительных чисел при решении задачи на минимум свидетельствует о том, что нами оптимальное решение не получено и что от таблицы 0-й итерации необходимо перейти к следующей.
Переход к следующей итерации осуществляем следующим образом:
Ведущий столбец соответствует
.
Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е.3.
Теперь приступаем к составлению 1-й итерации. Вместо единичного
вектора
вводим вектор
.
В новой таблице на месте разрешающего элемента пишем 1, все остальные элементы ключевого столбца –нули. Элементы ключевой строки делятся на разрешающий элемент. Все остальные элементы таблицы вычисляются по правилу прямоугольника.
Переходим к таблице 1-й итерации:
| БП |
|
|
|
|
|
|
|
|
|
Симплексные отношения |
| 1 | -1 | 1 | 1 | 1 | -1 | M | ||||
|
|
1 | 25/3 | 0 | -1/3 | 4/3 | 1 | 0 | 16/3 | - | 25/16 |
|
|
1 | 2/3 | 1 | 1/3 | -4/3 | 0 | 0 | 2/3 | - | 1 |
|
|
1 | 16/3 | 0 | 5/3 | 4/3 | 0 | 1 | 4/3 | - | 4 |
|
|
43/3 | 0 | 8/3 | 1/3 | 0 | 0 | 25/3 | - | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | |||
Ключевой столбец для 1-й итерации соответствует
.
Находим ключевую строку, для этого определяем:
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 2/3.
Вектор
выводим из базиса и вводим вектор
.
На сайте можно заказать решение задач, контрольных, самостоятельных, домашних работ (возможно срочное решение). Для этого вам нужно только связаться со мной:
Телеграм (+7 968 849-45-98)
ВКонтакте
WhatsApp (+7 968 849-45-98)
Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту. Опыт работы более 25 лет.
Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.
Переходим к таблице 2-й итерации:
| БП |
|
|
|
|
|
|
|
|
|
Симплексные отношения |
| 1 | -1 | 1 | 1 | 1 | -1 | M | ||||
|
|
1 | 3 | -8 | -3 | 12 | 1 | 0 | 0 | - | 1/4 |
|
|
-1 | 1 | 3/2 | 1/2 | -2 | 0 | 0 | 1 | - | — |
|
|
1 | 4 | -2 | 1 | 4 | 0 | 1 | 0 | - | 1 |
|
|
6 | -25/2 | -3/2 | 17 | 0 | 0 | 0 | - | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | |||
Ключевой столбец для 2-й итерации соответствует
.
Находим ключевую строку, для этого определяем:
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 12.
Вектор
выводим из базиса и вводим вектор
.
Переходим к таблице 3-й итерации:
| БП |
|
|
|
|
|
|
|
|
|
Симплексные отношения |
| 1 | -1 | 1 | 1 | 1 | -1 | M | ||||
|
|
1 | 1/4 | -2/3 | -1/4 | 1 | 1/12 | 0 | 0 | - | — |
|
|
-1 | 3/2 | 1/6 | 0 | 0 | 1/6 | 0 | 1 | - | — |
|
|
1 | 3 | 2/3 | 2 | 0 | -1/3 | 1 | 0 | - | 3/2 |
|
|
7/4 | -7/6 | 11/4 | 0 | -17/12 | 0 | 0 | - | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | |||
Ключевой столбец для 3-й итерации соответствует
.
Находим ключевую строку, для этого определяем:
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 2.
Вектор
выводим из базиса и вводим вектор
.
Переходим к таблице 4-й итерации:
| БП |
|
|
|
|
|
|
|
|
|
Симплексные отношения |
| 1 | -1 | 1 | 1 | 1 | -1 | M | ||||
|
|
1 | 5/8 | -7/12 | 0 | 1 | 1/24 | 1/8 | 0 | - | |
|
|
-1 | 3/2 | 1/6 | 0 | 0 | 1/6 | 0 | 1 | - | |
|
|
-1 | 3/2 | 1/3 | 1 | 0 | -1/6 | 1/2 | 0 | - | |
|
|
-19/8 | -25/12 | 0 | 0 | -23/24 | -11/8 | 0 | - | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | |||
В индексной строке все члены неположительные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):
Задача 2
Решить задачу линейного программирования методом искусственного базиса.
Решение
Ограничение имеет предпочтительный вид, если при неотрицательности правой части левая часть имеет
переменную, входящую с коэффициентом, равным единице, а остальные
ограничения-равенства - с коэффициентом, равным нулю. 1-е, 2-е ограничения не
имеют предпочтительного вида, поэтому для них вводим искусственные переменные
.
В целевую функцию искусственные переменные введем с коэффициентами
,
где
- большое положительное число. Получили
M-задачу, которая всегда имеет предпочтительный вид.
Заполняем симплексную таблицу 0-й итерации.
| БП |
|
|
|
|
|
|
|
|
Симплексные отношения |
| 8 | -6 | -5 | 2 | -M | -M | ||||
|
|
-M | 16 | 1 | 4 | -1 | 1 | 1 | 0 | 16 |
|
|
-M | 20 | 4 | -6 | 3 | -7 | 0 | 1 | 5 |
|
|
0 | -8 | 6 | 5 | -2 | 0 | 0 | ||
| -36M | -5M | 2M | -2M | 6M | 0 | 0 | |||
Так как мы решаем задачу на максимум – наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что нами оптимальное решение не получено и что от таблицы 0-й итерации необходимо перейти к следующей.
Переход к следующей итерации осуществляем следующим образом:
Ведущий столбец соответствует
.
Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е.4.
Теперь приступаем к составлению 1-й итерации. Вместо единичного
вектора
вводим вектор
.
В новой таблице на месте разрешающего элемента пишем 1, все остальные элементы ключевого столбца –нули. Элементы ключевой строки делятся на разрешающий элемент. Все остальные элементы таблицы вычисляются по правилу прямоугольника.
Переходим к таблице 1-й итерации:
| БП |
|
|
|
|
|
|
|
|
Симплексные отношения |
| 8 | -6 | -5 | 2 | -M | -M | ||||
|
|
-M | 11 | 0 | 11/2 | -7/4 | 11/4 | 1 | - | 2 |
|
|
8 | 5 | 1 | -3/2 | 3/4 | -7/4 | 0 | - | — |
|
|
40 | 0 | -6 | 11 | -16 | 0 | - | ||
| -11M | 0 | -11/2M | 7/4M | -11/4M | 0 | - | |||
Ключевой столбец для 1-й итерации соответствует
.
Находим ключевую строку, для этого определяем:
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 11/2.
Вектор
выводим из базиса и вводим вектор
.
Переходим к таблице 2-й итерации:
| БП |
|
|
|
|
|
|
|
|
Симплексные отношения |
| 8 | -6 | -5 | 2 | -M | -M | ||||
|
|
-6 | 2 | 0 | 1 | -7/22 | 1/2 | - | - | 4 |
|
|
8 | 8 | 1 | 0 | 3/11 | -1 | - | - | — |
|
|
52 | 0 | 0 | 100/11 | -13 | - | - | ||
| 0 | 0 | 0 | 0 | 0 | - | - | |||
Ключевой столбец для 2-й итерации соответствует
.
Находим ключевую строку, для этого определяем:
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 1/2.
Вектор
выводим из базиса и вводим вектор
.
Переходим к таблице 3-й итерации:
| БП |
|
|
|
|
|
|
|
|
Симплексныеотношения |
| 8 | -6 | -5 | 2 | -M | -M | ||||
|
|
2 | 4 | 0 | 2 | -7/11 | 1 | - | - | |
|
|
8 | 12 | 1 | 2 | -4/11 | 0 | - | - | |
|
|
104 | 0 | 26 | 9/11 | 0 | - | - | ||
| 0 | 0 | 0 | 0 | 0 | - | - | |||
В индексной строке все члены неотрицательные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):
