симплекс-методом
Задача:
Найти значения переменных x1...x2, при которых функция:
принимает минимальное значение, при условии следующих ограничений:
|
| x1
| +
|
| x2
| ≥
| |
| | (1)
|
|
| x1
| +
|
| x2
| ≥
| |
| | (2)
|
|
| x1
| | | | ≥
| |
| | (3)
|
| | | |
| x2
| ≥
| |
| | (4)
|
x1, x2 ≥ 0
Шаг:1
Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3, 4 неотрицательные балансовые переменные s1, s2, s3, s4.
|
| x1
| +
|
| x2
| -
| | s1
| | | | | | | | | | =
| |
| | (1)
|
|
| x1
| +
|
| x2
| | | | -
| | s2
| | | | | | | =
| |
| | (2)
|
|
| x1
| | | | | | | | | | -
| | s3
| | | | =
| |
| | (3)
|
| | | |
| x2
| | | | | | | | | | -
| | s4
| =
| |
| | (4)
|
x1, x2, s1, s2, s3, s4 ≥ 0
Шаг:2
Ищем в системе ограничений базисные переменные.
Базисные переменные в исходной задаче отсутствуют, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу.
Введем по одной искусственной неотрицательной переменной ri в каждое уравнение системы ограничений.
Получим следующую систему ограничений,
|
| x1
| +
|
| x2
| -
| | s1
| | | | | | | | | | +
| | r1
| | | | | | | | | | =
| |
| | (1)
|
|
| x1
| +
|
| x2
| | | | -
| | s2
| | | | | | | | | | +
| | r2
| | | | | | | =
| |
| | (2)
|
|
| x1
| | | | | | | | | | -
| | s3
| | | | | | | | | | +
| | r3
| | | | =
| |
| | (3)
|
| | | |
| x2
| | | | | | | | | | -
| | s4
| | | | | | | | | | +
| | r4
| =
| |
| | (4)
|
x1, x2, s1, s2, s3, s4, r1, r2, r3, r4 ≥ 0
с базисными переменными r1,r2,r3,r4.
Целью решения вспомогательной задачи является получение допустимого базисного решения не содержащего искусственных переменных (r1,r2,r3,r4). Для этого сформируем вспомогательную целевую функцию:
и проведем ее минимизацию в заданной системе ограничений. Если после минимизации функции G ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции G ее оптимальное значение окажется отличным от нуля, значит исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет.
Для решения вспомогательной задачи симплекс методом выразим функцию G через свободные переменные, для этого:
- вычтем из функции G уравнение 1
- вычтем из функции G уравнение 2
- вычтем из функции G уравнение 3
- вычтем из функции G уравнение 4
Функция G примет вид:
G =
| -
|
| x1
| -
|
| x2
| +
| s1
| +
| s2
| +
| s3
| +
| s4
| +
|
| |
Теперь мы можем сформировать начальную симплекс-таблицу.
Шаг:3
Начальная симплекс-таблица
БП
| x1
| x2
| s1
| s2
| s3
| s4
| r1
| r2
| r3
| r4
| Решение
| Отношение
|
r1
|
|
| -1
|
|
|
|
|
|
|
|
| |
r2
|
|
|
| -1
|
|
|
|
|
|
|
| |
r3
|
|
|
|
| -1
|
|
|
|
|
|
| --
|
r4
|
|
|
|
|
| -1
|
|
|
|
|
| |
Q
|
|
|
|
|
|
|
|
|
|
|
| --
|
G
| -9
| -36
|
|
|
|
|
|
|
|
| -108
| --
|
Итерация 1
БП
| x1
| x2
| s1
| s2
| s3
| s4
| r2
| r3
| r4
| Решение
| Отношение
|
x2
| |
| |
|
|
|
|
|
| | |
r2
|
|
| | -1
|
|
|
|
|
|
| |
r3
|
|
|
|
| -1
|
|
|
|
|
| |
r4
| -3
|
| |
|
| -1
|
|
|
|
| --
|
Q
| |
| |
|
|
|
|
|
| | --
|
G
| -3
|
| -2
|
|
|
|
|
|
| -48
| --
|
Итерация 2
БП
| x1
| x2
| s1
| s2
| s3
| s4
| r2
| r4
| Решение
| Отношение
|
x2
|
|
| |
| |
|
|
| | --
|
r2
|
|
| | -1
|
|
|
|
|
| |
x1
|
|
|
|
| |
|
|
| | --
|
r4
|
|
| |
| -1
| -1
|
|
|
| |
Q
|
|
| |
| |
|
|
| | --
|
G
|
|
| -2
|
|
|
|
|
| -34
| --
|
Итерация 3
БП
| x1
| x2
| s1
| s2
| s3
| s4
| r4
| Решение
| Отношение
|
x2
|
|
|
| | |
|
| | --
|
s1
|
|
|
| -2
|
|
|
|
| --
|
x1
|
|
|
|
| |
|
| | --
|
r4
|
|
|
|
| -4
| -1
|
|
| |
Q
|
|
|
| | |
|
| | --
|
G
|
|
|
| -3
|
|
|
| -2
| --
|
Итерация 3-a
БП
| x1
| x2
| s1
| s2
| s3
| s4
| Решение
| Отношение
|
x2
|
|
|
|
|
| | | --
|
s1
|
|
|
|
| | | | --
|
x1
|
|
|
|
| |
| | --
|
s2
|
|
|
|
| | | | --
|
Q
|
|
|
|
|
| | | --
|
G
|
|
|
|
|
|
|
| --
|
Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к. в строке целевой функции нет отрицательных коэффициентов). Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Сторка "G" нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке "Q"
Итерация 4
БП
| x1
| x2
| s1
| s2
| s3
| s4
| Решение
| Отношение
|
x2
|
|
|
|
|
| | | --
|
s1
|
|
|
|
| | | | --
|
x1
|
|
|
|
| |
| | --
|
s2
|
|
|
|
| | | | --
|
Q
|
|
|
|
|
| | | --
|
Достигнуто оптимальное решение, т.к. в строке целевой функции нет отрицательных коэффициентов.
Ответ:
Оптимальное значение функции Q(x)=
| |
достигается в точке с координатами:
Задача № 3. Пример решения задачи линейного программирования
(задача с искусственным базисом, обыкновенные дроби) табличным симплекс-методом
Для упрощения процесса решения исходные данные задачи линейного программирования при решении ее симплекс методом записываются в специальные симплекс-таблицы. Поэтому одна из модификаций симплекс метода получила название табличный симплекс метод. Задача линейного программирования в каноническом виде:
F=a0,1x1+a0,2x2+...a0,nxn +b0 → max
a1,1x1+a1,2x2+...a1,nxn + xn+1=b1
a2,1x1+a2,2x2+...a2,nxn +xn+2 =b2
.......................................
am,1x1+am,2x2+...am,nxn+xn+m=bm
Исходная таблица для задачи имеет следующий вид:
| x1
| x2
| ...
| xn-1
| xn
| b
|
F
| -a0,1
| -a0,2
| ...
| -a0,n-1
| -a0,n
| -b0
|
xn+1
| a1,1
| a1,2
| ...
| a1,n-1
| a1,n
| b1
|
xn+2
| a2,1
| a2,2
| ...
| a2,n-1
| a2,n
| b2
|
...
| ...
| ...
| ...
| ...
| ...
| ...
|
xn+m
| am,1
| am,2
| ...
| am,n-1
| am,n
| bm
|
x1, x2, xn - исходные переменные, xn+1, xn+2, xn+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.