2.3 Симплекс-метод с искусственным базисом
Если математическая модель задачи линейного программирования содержит неравенства со знаком «≥» или (и) «=», для ее решения следует использовать симплекс-метод с искусственным базисом. Рассмотрим решение следующей задачи.
Задача 2.2.Определить оптимальный план задачи линейного программирования:
max Z = 25 x1 + 50 x2 + 40 x3
25 x1+ 50 x2 21000
40 x3 12000
x1 + x2 + x3 1000
10 x1 + x2 +25 x3 15760
x1, x2, x3 0
Вначале запишем задачу в каноническом виде, путем введения дополнительных и искусственных переменных. С помощью этих переменных система неравенств принимает вид уравнений.
Если в неравенстве стоит знак , то к левой части этого неравенства прибавляется некоторая неизвестная неотрицательная величина – дополнительная переменная. Ее обозначают буквой x с соответствующим номером.
Если в неравенстве стоит знак , то от левой его части вычитается дополнительная неотрицательная переменная. Кроме того, в такие ограничения вводятся искусственные переменные, которые служат для создания опорного решения.
Искусственные переменные вводятся также в целевую функцию с коэффициентом «–М» при решении задачи максимизации и с коэффициентом «+М» при минимизации целевой функции, где М – положительная константа, превосходящая модуль любого из коэффициентов целевой функции.
В результате получаем задачу в каноническойформе:
z = 25 x1 + 50x2 + 40 x3 + 0·()- M x8 - M x9 max
25x1+50x2 – x4 + x8 = 21000
40 x3 - x5 +x9 = 12000
x1 + x2 + x3 + x6 100
10x1 + x2 + 25x3+ x7 =15760
xJ 0,j=1,2,…,9
В симплекс-методе с искусственным базисом первоначальная таблица имеет две последние строки «М+1» и «М+2». Строку «М+1» формируют аналогично симметричному симплекс-методу, а в строку «М+2» записывают суммы соответствующих коэффициентов ограничений с искусственными переменными. В нашей задаче – это коэффициенты первого и второго ограничений. Сегмент последних двух строк, принадлежащий столбцам искусственных переменных x8 и x9, заполняют нулями.
Выпишем первую симплексную таблицу.
Таблица 1 – Первоначальная симплексная таблица.
Базис | B | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 |
X8 | 21000 | 25 | 50 | 0 | -1 | 0 | 0 | 0 | 1 | 0 |
X9 | 12000 | 0 | 0 | 40 | 0 | -1 | 0 | 0 | 0 | 1 |
X6 | 1000 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
X7 | 15760 | 10 | 1 | 25 | 0 | 0 | 0 | 1 | 0 | 0 |
М+1 | 0 | -25 | -50 | -40 | 0 | 0 | 0 | 0 | 0 | 0 |
M+2 | 33000 | 25 | 50 | 40 | 1 | 1 | 0 | 0 | 0 | 0 |
Разрешающий столбец определяют по наибольшему положительному элементу строки «М+2». Разрешающую строку выбирают по тому же правилу, что и в симплекс-методе без искусственных переменных. В ходе итераций искусственные переменные вытесняются из базиса, а соответствующие им столбцы исключают. Процесс продолжается до тех пор, пока все коэффициенты строки «М+2» не станут равными нулю. На этом первый этап решения задачи завершается. Его результатом является опорный план исходной задачи. Далее используются алгоритм симплекс-метода с выбором разрешающего столбца по строке «М+1».
В таблице 1 разрешающий элемент находится в строке 1 столбца х2. В результате пересчета получим таблицу 2.
Таблица 2 – Вторая симплексная таблица
Базис | B | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X9 |
X2 | 420 | 0.5 | 1 | 0 | 0.020 | 0 | 0 | 0 | 0 |
X9 | 12000 | 0 | 0 | 40 | 0 | -1 | 0 | 0 | 1 |
X6 | 580 | 0.50 | 0 | 1 | 0.02 | 0 | 1 | 0 | 0 |
X7 | 15340 | 9.5 | 0 | 25 | 0.02 | 0 | 0 | 1 | 0 |
М+1 | -21000 | 0 | 0 | -40 | -1 | 0 | 0 | 0 | 0 |
M+2 | 12000 | 0 | 0 | 40 | 0 | 1 | 0 | 0 | 0
|
Разрешающий элемент находится в строке 2 столбца х3. Следующая таблица будет иметь вид:
Таблица 3 – Третья симплексная таблица
Базис | B | X1 | X2 | X3 | X4 | X5 | X6 | X7 |
X2 | 420 | 0.5 | 1 | 0 | -0.02 | 0 | 0 | 0 |
X3 | 300 | 0 | 0 | 1 | 0 | -0.03 | 0 | 0 |
X6 | 280 | 0.5 | 0 | 0 | 0.02 | 0.03 | 1 | 0 |
X7 | 7840 | 9.5 | 0 | 0 | 0.02 | 0.63 | 0 | 1 |
М+1 | 33000 | 0 | 0 | 0 | -1 | -1 | 0 | 0 |
М+2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
В таблице 3 нет столбцов x8 и x9, так как эти искусственные переменные исключены из базиса. Строку «M+2» следует отбросить. Завершен первый этап решения задачи.
Разрешающий элемент находится в строке 3 столбца х4.
Таблица 4 – Четвертая симплексная таблица
Базис | B | X1 | X2 | X3 | X4 | X5 | X6 | X7 |
X2 | 700 | 1 | 1 | 0 | 0 | 0.02 | 1 | 0 |
X3 | 300 | 0 | 0 | 1 | 0 | -0.03 | 0 | 0 |
X4 | 14000 | 25 | 0 | 0 | 1 | 1.25 | 50 | 0 |
X7 | 7560 | 9 | 0 | 0 | 0 | 0.60 | -1 | 1 |
M+1 | 47000 | 25 | 0 | 0 | 0 | 0.25 | 50 | 0 |
Последняя строка таблицы 4 не содержит отрицательных элементов, следовательно, выполнился критерий оптимальности. Завершен второй этап решения.
Оптимальный план:
, ,,,
, ,
.
- Экономико-математические методы
- 1 Общая задача математического
- 1.1 Модель математического программирования
- 1.2 Математическая формулировка задач линейного
- 1.3 Примеры построения простейших моделей математического
- 1.4 Геометрическая интерпретация задач линейного
- 1.4.1 Графический метод решения
- 1.4.2 Схема решения задачи графическим методом
- 1.4.3 Особые случаи решения задач линейного
- 1.5 Контрольные вопросы к разделу 1
- 2 Симплекс-метод решения задач линейного
- 2.1 Симметричный симплекс-метод
- 2.2 Экономический анализ оптимального плана по последней
- 2.3 Симплекс-метод с искусственным базисом
- 2.4. Схема решения задач линейного программирования
- 2.5. Особые случаи при решении задач симплекс-методом
- 2.6 Контрольные вопросы к разделу 2
- 3 Двойственные задачи линейного
- 3.1 Понятие о двойственных задачах
- 3.2 Теоремы двойственности в линейном программировании
- 3.3 Экономическая интерпретация двойственных задач
- 3.4. Примеры построения двойственных задач
- 3.5 Контрольные вопросы к разделу 3
- 4 Транспортная задача линейного
- 4.1 Математическая постановка транспортной задачи
- 4.2 Метод потенциалов решения транспортной задачи
- Числаui являются потенциалами строк, аvj – потенциалами столбцов. Из теоремы следует, что для того, чтобы план был оптимальным, необходимо выполнение следующих условий:
- Если хотя бы одна незанятая клетка не удовлетворяет условию (б), то план не оптимален.
- 4.3 Схема решения транспортной задачи
- 4.4 Контрольные вопросы к разделу 4
- 5 Методы решения задач нелинейного
- 5.1 Классификация задач математического программирования
- 5.2 Метод Лагранжа
- 5.3 Метод динамического программирования
- 5.4 Применение динамического программирования для решения задач о замене оборудования и эффективного использования
- 5.5 Контрольные вопросы к разделу 5
- 6 Наиболее распространенные модели
- Содержание
- Литература
- Экономико-математические методы Учебное пособие