2015-08-21
5287
Приводим задачу к каноническому виду. Для задачи максимизации составляем симплекс-таблицу. Если распределение не оптимально, то строим новую симплекс таблицу по специальным формулам. И т.д. Задача минимизации сводится к задаче максимизации умножением целевой функции на -1.
Пример 2. Решим задачу ЛП
F = x1+x2 → max
Приведем к каноническому виду и перейдём к уравнениям:
Основные переменные x1, x2 (входят в целевую функцию), неосновные переменные x3, x4, x5 (введены дополнительно). Выразим неосновные переменные через основные переменные.
Составим симплекс-таблицу.
| -x1 | -x2 | b | |
| x3 | -1 | -2 | |
| x4 | -1 | ||
| x5 | -1 | ||
| F | -1 | -1 |
В таблице собраны коэффициенты при (- x1), (- x2) в выражениях для x3, x4, x5, F. Столбец b – это столбец свободных членов. Если последний столбец и последняя строка (кроме правой нижней клетки) не содержат отрицательных чисел, то получен ответ. Если этого не наблюдаем, проводится МЖИ-операция. Сначала избавляются от минусов в последнем столбце, затем – в последней строке.
|
|
|
У нас есть минусы в последнем столбце. Выбираем любой отрицательный элемент в последнем столбце. Это -2. Двигаемся по строке, где находится этот выбранный элемент, и берем любой отрицательный элемент в этой строке. Это -1. Смотрим, в каком столбце находится выбранный элемент -1. Во втором. Этот столбец называется разрешающим.
Далее поэлементно делим последний столбец на разрешающий столбец и среди положительных конечных отношений берем наименьшее: min {(-2)/(-1), 13/2}=2. Строку, где достигается этот минимум, назовем разрешающей. Это – первая строка.
Элемент на пересечении разрешающей строки и разрешающего столбца назовем разрешающим. Это -1. Выделим его.
Преобразуем таблицу. В разрешающих строке и столбце переменные меняем местами (это x2 и x3). На месте разрешающего элемента пишем 1/(разрешающий элемент) = 1/(-1) = -1. В разрешающей строке каждое число делим на разрешающий элемент. В разрешающем столбце каждое число делим на разрешающий элемент и результат берем со знаком минус. Остальные элементы считаем по правилу прямоугольников.
 |
Элемент ∆ находится в разрешающей строке в одном столбце со старым элементом. Элемент 
находится в разрешающем столбце в одной строке со старым элементом.
Получим таблицу:
| -x1 | -x3 | b | |
| x2 | -1 | -1 | |
| x4 | |||
| x5 | -1 | ||
| F | -2 | -1 |
Последний столбец не содержит отрицательных чисел. Зато отрицательные числа есть в последней строке. Выбираем любое из них. Например -2. Теперь первый столбец – разрешающий. Применим МЖИ-операцию. Получим:
| -x5 | -x3 | b | |
| x2 | 0,5 | -1,5 | |
| x4 | -0,5 | 2,5 | |
| x1 | 0,5 | -0,5 | |
| F | -2 |
Применим МЖИ-операцию. Получим:
|
|
|
| -x5 | -x4 | b | |
| x2 | 0,6 | ||
| x3 | -0,2 | 0,4 | |
| x1 | 0,2 | ||
| F | 0,6 | 0,8 |
Ответ получен. Из 1-го и 4-го столбцов x2 = 9, x3 = 2, x1 = 5. Из 1-й и 5-й строк F = 14 - 0,6 x5 – 0,8 x4
Fmax = 14, x1 = 5, x2 = 9.
Критерий оптимальности решения при отыскании максимума целевой функции: если в выражении линейной функции через неосновные переменные отсутствуют положительные коэффициенты при неосновных переменных, то решение оптимально. У нас это так (-0,6 < 0, -0,8<0).
Задача 3. Решить симплекс-методом задачу ЛП
F = x1+3x2 → max
