 |
Задача № 2. Решить задачи линейного программирования
|
|
|
|
симплекс-методом
Задача:
Найти значения переменных x1...x2, при которых функция:
| Q = | 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 = | 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)= |
достигается в точке с координатами:
| x1= | ||||
| x2= | ||||
| s1= | ||||
| s2= | ||||
| s3= | ||||
| s4= |
Задача № 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 - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.
Задания к контрольной работе
Каждый студент выполняет контрольную работу по одному из десяти вариантов в соответствии с начальной буквой своей фамилии.
|
|
|
Начальная буква Вариант
А Б ВЧ Т У 1
Г Д ЕШФ 2
Ж З ИЩ Х 3
К ЛЭЦ 4
М Н ОЮ 5
П Р СЯ 6
Задание 1.
Вариант 1. Решить графически
1)
2)
Вариант 2. Решить графически
Вариант 3. Решить графически
Вариант 4. Решить графически
Вариант 5. Решить графически
Вариант 6. Решить графически
|
|
|
