Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
1949г. – американский математик Данциг предложил универсальный метод решения задач ЛП. Этот метод получил название симплекс-метод. С.-м. носит итерационный характер. Это значит, что однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор, пока не будет получено оптимальное решение. При использовании симплекс-метода целевая функция и ограничения на переменные должны быть представлены в так называемой стандартной форме. При стандартной форме линейной модели:
1) все ограничения записываются в виде равенств с неотрицательной правой частью;
2) значения всех переменных модели должны быть неотрицательны;
3) целевая функция максимизируется или минимизируется.
Исходное ограничение, записанное в виде неравенства, можно представить в виде равенства, прибавляя некоторую переменную к левой части ограничения. Например, в левую часть исходного ограничения 2x1+5x2+3x3≤6
вводится переменная xu>0, в результате чего исходное неравенство обращается в равенство
2x1+5x2+3x3 +x4=6
Если правая часть равенства отрицательна, то, умножая обе части на -1, ее можно сделать неотрицательной.
Максимизацию функции F всегда можно заменить минимизацией функции -F и наоборот.
Например, Max F=7x1+x2+5x3
можно заменить Min (-F) =-7x1-x2-5x3
Если переменная, входящая в ограничения, неограниченна по знаку, то такую переменную можно представить как разность двух положительных переменных:
x1=x1'-x1'', x1’≥0, x1'' ≥0
Пример: требуется минимизировать функцию
F=3x1+4x2
при условии
x1+x2=10
-2x1+3x2≤-5
7x1-4x2≤6
x2≥0
x1 не ограничена по знаку.
Для решения задачи неравенства превратим в равенства путем добавления новых переменных, а переменную x1 представим как разность двух положительных переменных:
Min F=3 x1'-3x1''+4x2
x1'-x1''+x2=10,
2x1'-2x1''-3x2-s1=5,
7x1'-7x1''-4x2+s2=6,
x1', x1'', x2, s1, s2 ≥0
Общую идею симплекс-метода можно проиллюстрировать на примере.
Пусть требуется максимизировать функцию
F=3x1+2x2
при ограничениях
x1+2x2≤6,
2x1+x2≤8,
-x1+x2≤1,
x2≤2; x1, x2 ≥0.
Приведенная линейная модель может быть сведена к стандартной форме
Max F=3x1+2x2+0x3+0x4+0x5+0x6
при ограничениях
x1+2x2+x3 =6,
4x1+2x2 +x4 =8,
-x1+ x2 +x5 =1,
x2 +x6=2
x1, x2, x3, x4, x5, x6 ≥0
На рис.2.2 представлено пространство решений данной задачи. Каждую точку этого пространства можно определить c помощью переменных, входящих в модель стандартной формы. Например, при x3=0 первое ограничение принимает вид равенства 2x1+4x2=12, которое можно представить прямой 3-4.
Поскольку стандартная модель содержит четыре уравнения и шесть неизвестных, в каждой из экстремальных точек две переменные (=6-4) должны иметь нулевые значения. Например, в точке 1 – x1 и x2 равны нулю, в точке 2 – x4 и x2, в точке 3 – x3 и x4. Можно заметить, что экстремальные точки отличаются только одной переменной Переменные, имеющие
отличное от нуля значение, называются базисными, остальные – небазисными переменными.
Каждую последующую экстремальную точку можно определить путем замены одной из текущих небазисных переменных текущей базисной переменной.
Алгоритм симплекс-метода состоит из следующих шагов.
Шаг 1. Используя линейную модель стандартной формы, определяют
начальное допустимое базисное решение.
Шаг 2. Из числа текущих небазисных переменных выбирается одна, которая включается в новый базис. Увеличение этой переменной должно обеспечить улучшение значения целевой функции. Затем осуществляется переход к следующему шагу.
Шаг 3. Из числа базисных переменных выбирается одна, которая должна принять, нулевое значение (т.е. стать небазисной) при введении в состав базисных новой переменной.
Шаг 4. Находится новое базисное решение, соответствующее новым составам базисных и небазисных переменных.
В нашем примере точку I можно использовать как начальное допустимое решение. В этой точке x1=x2=0 и x3=6, x4=8, x5=1, x6=2, а функция F=0.
Преобразовав уравнение целевой функции так, чтобы его правая часть стала равна нулю F-3x1+2x2=0
можно убедиться, что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение.
Полученные результаты удобно представить в виде табл.2.1.
Первый столбец этой таблицы содержит переменные пробного базиса x3, x4, x5, x6, значения которых приведены в последнем столбце.
Является ли полученное решение оптимальным? Нет. Об этом свидетельствует наличие в строке целевой функции отрицательных чисел.
Таблица 2.1
Базисные переменные | F | x1 | x2 | x3 | x4 | x5 | x6 | Решение |
x3 | ||||||||
x4 | ||||||||
x5 | -1 | |||||||
x6 | ||||||||
F | -3 | -2 |
Это эквивалентно наличию положительных коэффициентов при этих переменных в исходной целевой функции. Поскольку речь идет о максимизации, значение F может быть увеличено при увеличении как x1, так и x2. Если бы в отроке целевой функции не было отрицательных чисел, это означало бы, что функция цели уже не пересекает оси в области положительных решений.
А в качестве переменной, включаемой в базис, выберем x1, так как коэффициент при ней больше и функция цели изменяется сильнее. Исключаемая переменная выбирается из совокупности базисных переменных x3, x4, x5, x6. Этой переменной является та, которая первой обращается в нуль при увеличении включаемой переменной вплоть до значения, соответствующего смежной экстремальной точке. В нашем случае переменная x1 достигает максимально допустимого значения, равного 4, в точке 2, при этом исключаемой из базиса переменной становится x4.
Отношение, фиксирующее искомую точку пересечения и идентифицирующее исключаемую переменную, можно определить прямо из симплекс-таблицы. Для этого в столбце, соответствующем вводимой переменной x, вычеркиваются отрицательные и нулевые элементы ограничений. Затем вычисляются отношения постоянных, фигурирующих в правых частях этих ограничений, к оставшимся элементам столбца, соответствующего вводимой переменной x1. Исключаемой переменной будет та переменная базиса, для которой указанное выше отношение минимально.
Указанная процедура иллюстрируется табл.2.2. Таблица 2.2
Базисные переменные | F | x1 | x2 | x3 | x4 | x5 | x6 | Решение |
x3 | 6 (6/1=6) | |||||||
x4 | 8 (8/2=4) | |||||||
x5 | -1 | |||||||
x6 | ||||||||
F | -3 | -2 |
Столбец симплекс-таблицы, ассоциируемый с вводимой переменной, будет называть ведущим столбцом. Строку, соответствующую исключаемой переменной, назовем ведущей строкой, а элемент таблицы, находящийся на пересечении ведущего столбца и ведущей строки, будем называть ведущим элементом.
Все элементы новой ведущей строки получаются путем деления элементов предыдущей ведущей отроки на ведущий элемент. Все остальные уравнения получаются по правилу
(Новое уравнение) = (Предыдущее уравнение) -
-(Коэффициент ведущего столбца предыдущего уравнения)*
*(Новая ведущая строка).
В новом ведущем уравнении ведущий элемент становится равным 1, а все остальные коэффициенты, фигурировавшие в ведущем столбце, становятся равными 0.
Составим по этому правилу новую симплекс-таблицу. Новая ведущая строка:
x1 | x2 | x3 | x4 | x5 | x6 | Решение | |
1/2 | 1/2 | 8/2=4 |
Для строки получим
|
| ||||
-3 | -2 |
|
|
3/2 | 3/2 |
|
|
-1/2 | 3/2 |
Для x3 – уравнения
|
| ||||
-1 | -1/2 | -1/2 | -4 |
|
|
3/2 | -1/2 |
Для x5 – уравнения
|
| ||||||||||
-1 | -1/2 | -1/2 | -4 |
|
|
3/2 | -1/2 |
x6 - уравнение останется таким же, постольку соответствующий коэффициент ведущего столбца равен нулю.
Таким образом, симплекс- таблица примет вид
Таблица 2.3
Базисные переменные | F | x1 | x2 | x3 | x4 | x5 | x6 | Решение |
x3 | 3/2 | -1/2 | 2 (4/3) | |||||
x1 | 1/2 | 1/2 | 4 (8) | |||||
x5 | 3/2 | 1/2 | 5 (10/3) | |||||
x6 | 2 (2) | |||||||
F | -1/2 | 3/2 |
Из последней таблицы следует, что на очередной итерации в качестве вводимой переменной следует выбрать x2, т.к. коэффициент при этой переменной в F -уравнении равен -1/2. Исключаемой переменной будет x3, а включаемой – x2. Новая симплекс-таблица будет иметь вид табл.2.4.
Таблица 2.4
Базисные переменные | F | x1 | x2 | x3 | x4 | x5 | x6 | Решение |
x3 | 2/3 | -1/3 | 4/3 | |||||
x1 | -1/3 | 2/3 | 10/3 | |||||
x5 | -1 | |||||||
x6 | -2/3 | 1/3 | 2/3 | |||||
F | 1/3 | 4/3 | 38/3 |
В новом базисном решении x1=10/3 и x2=4/3. Значение F увеличилось с 12 (предыдущая таблица) до 38/3. Этот прирост целевой функции обусловлен увеличением x2 от 0 до 4/3, так как из F -строки предыдущей симплекс-таблицы следует, что возрастанию данной переменной на единицу соответствует увеличение функции на 1/2.
Последняя симплекс-таблица соответствует оптимальному решению задачи, так как в F -строке ни одна из небазисных переменных не фигурирует c отрицательным коэффициентом. На этом и завершаются вычислительные процедуры симплекс-метода.
В случае минимизации функции цели в алгоритме необходимо изменить только условие оптимальности: в качестве новой базисной переменной следует выбрать ту переменную, которая в F -строке имеет наибольший положительный коэффициент.
Дата публикования: 2015-01-26; Прочитано: 660 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!