Пример решения задачи линейного программирования нашим сервисом:
(задача с искусственным базисом, обыкновенные дроби)
Заметьте! Решение вашей конкретной задачи будет выглядеть аналогично данному примеру, включая все таблицы и поясняющие тексты, представленные ниже, но с учетом ваших исходных данных…
Задача:
Найти значения переменных x1...x2, при которых функция:
принимает минимальное значение, при условии следующих ограничений :
| | 2 | x1 | + | 12 | x2 | ≥ | | 20 | | (1) | | | 4 | x1 | + | 6 | x2 | ≥ | | 32 | | (2) | | | 3 | x1 | | | | ≥ | | 14 | | (3) | | | | | | 18 | x2 | ≥ | | 42 | | (4) |
x1, x2 ≥ 0
Шаг:1
Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3, 4 неотрицательные балансовые переменные s1, s2, s3, s4.
| | 2 | x1 | + | 12 | x2 | - | | s1 | | | | | | | | | | = | | 20 | | (1) | | | 4 | x1 | + | 6 | x2 | | | | - | | s2 | | | | | | | = | | 32 | | (2) | | | 3 | x1 | | | | | | | | | | - | | s3 | | | | = | | 14 | | (3) | | | | | | 18 | x2 | | | | | | | | | | - | | s4 | = | | 42 | | (4) |
x1, x2, s1, s2, s3, s4 ≥ 0
Шаг:2
Ищем в системе ограничений базисные переменные.
Базисные переменные в исходной задаче отсутствуют, это значит, что исходная задача не содержит
в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу.
Введем по одной искусственной неотрицательной переменной ri в каждое уравнение
системы ограничений.
Получим следующую систему ограничений,
| | 2 | x1 | + | 12 | x2 | - | | s1 | | | | | | | | | | + | | r1 | | | | | | | | | | = | | 20 | | (1) | | | 4 | x1 | + | 6 | x2 | | | | - | | s2 | | | | | | | | | | + | | r2 | | | | | | | = | | 32 | | (2) | | | 3 | x1 | | | | | | | | | | - | | s3 | | | | | | | | | | + | | r3 | | | | = | | 14 | | (3) | | | | | | 18 | x2 | | | | | | | | | | - | | s4 | | | | | | | | | | + | | r4 | = | | 42 | | (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 = | - | 9 | x1 | - | 36 | x2 | + | s1 | + | s2 | + | s3 | + | s4 | + | 108 | |
Теперь мы можем сформировать начальную симплекс-таблицу.
Шаг:3
Начальная симплекс-таблица
| БП | x1 | x2 | s1 | s2 | s3 | s4 | r1 | r2 | r3 | r4 | Решение | Отношение | | r1 | 2 | 12 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 20 | | | r2 | 4 | 6 | 0 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 32 | | | r3 | 3 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0 | 14 | -- | | r4 | 0 | 18 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 42 | | | Q | 12 | 10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -- | | G | -9 | -36 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | -108 | -- |
Итерация 1
| БП | x1 | x2 | s1 | s2 | s3 | s4 | r2 | r3 | r4 | Решение | Отношение | | x2 | | 1 | | 0 | 0 | 0 | 0 | 0 | 0 | | | | r2 | 3 | 0 | | -1 | 0 | 0 | 1 | 0 | 0 | 22 | | | r3 | 3 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | 14 | | | r4 | -3 | 0 | | 0 | 0 | -1 | 0 | 0 | 1 | 12 | -- | | Q | | 0 | | 0 | 0 | 0 | 0 | 0 | 0 | | -- | | G | -3 | 0 | -2 | 1 | 1 | 1 | 0 | 0 | 0 | -48 | -- |
Итерация 2
| БП | x1 | x2 | s1 | s2 | s3 | s4 | r2 | r4 | Решение | Отношение | | x2 | 0 | 1 | | 0 | | 0 | 0 | 0 | | -- | | r2 | 0 | 0 | | -1 | 1 | 0 | 1 | 0 | 8 | | | x1 | 1 | 0 | 0 | 0 | | 0 | 0 | 0 | | -- | | r4 | 0 | 0 | | 0 | -1 | -1 | 0 | 1 | 26 | | | Q | 0 | 0 | | 0 | | 0 | 0 | 0 | | -- | | G | 0 | 0 | -2 | 1 | 0 | 1 | 0 | 0 | -34 | -- |
Итерация 3
| БП | x1 | x2 | s1 | s2 | s3 | s4 | r4 | Решение | Отношение | | x2 | 0 | 1 | 0 | | | 0 | 0 | | -- | | s1 | 0 | 0 | 1 | -2 | 2 | 0 | 0 | 16 | -- | | x1 | 1 | 0 | 0 | 0 | | 0 | 0 | | -- | | r4 | 0 | 0 | 0 | 3 | -4 | -1 | 1 | 2 | | | Q | 0 | 0 | 0 | | | 0 | 0 | | -- | | G | 0 | 0 | 0 | -3 | 4 | 1 | 0 | -2 | -- |
Итерация 3-a
| БП | x1 | x2 | s1 | s2 | s3 | s4 | Решение | Отношение | | x2 | 0 | 1 | 0 | 0 | 0 | | | -- | | s1 | 0 | 0 | 1 | 0 | | | | -- | | x1 | 1 | 0 | 0 | 0 | | 0 | | -- | | s2 | 0 | 0 | 0 | 1 | | | | -- | | Q | 0 | 0 | 0 | 0 | 4 | | | -- | | G | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -- |
Получено оптимальное решение вспомогательной задачи (найден минимум функции G
т.к. в строке целевой функции нет отрицательных коэффициентов).
Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению
исходной задачи, приняв полученное базисное решение в качестве опорного. Сторка "G" нам
больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях,
будем принимать по строке "Q"
Итерация 4
| БП | x1 | x2 | s1 | s2 | s3 | s4 | Решение | Отношение | | x2 | 0 | 1 | 0 | 0 | 0 | | | -- | | s1 | 0 | 0 | 1 | 0 | | | | -- | | x1 | 1 | 0 | 0 | 0 | | 0 | | -- | | s2 | 0 | 0 | 0 | 1 | | | | -- | | Q | 0 | 0 | 0 | 0 | 4 | | | -- |
Достигнуто оптимальное решение, т.к. в строке целевой функции нет отрицательных коэффициентов.
Ответ:| Оптимальное значение функции Q(x)= | |
достигается в точке с координатами:
см. пример решения задачи с начальным базисом...
решить мою задачу...
на ввод размеров...
к списку решаемых задач...
|
|