Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Симплекс метод.
Стандартная форма задачи линейного программирования
Задачи >3х мерной решаются только симплекс методом (аналитически).
Сначала задача приводится к стандартному виду.
Ограничения задаются в виде системы линейных алгебраических уравнений:
(n,m-индексы) (1)
Среди неотрицательных решений (1) нужно найти такое при котром линейная целевая функция L, вида: L= C+c1x1+c2x2+..cnxn→min
Достигает наименьшего значения
Любая задача линейного пр-ия всегда может быть приведена к стандартной форме Т.к. max(f)=-min(-f) следует что задача max может быть сведена к поиску min отрицательной функции, а в результате знак меняют на противоположный.
Если ограничения заданы неравенствами, то их можно преобразовать в равенства путем добавления необходимых выравн. переменных.
A11x1+a12x2+…+amxn≤b1
Преобразуем в равенство:
A11x1+a12x2+..+a1nxn+a1(n+1)=b1
Xn+1 – выравнивающая переменная
A1(n+1)- обычно равен 1.
Можно считать, что дополнительные переменные входят в выражение для целевой функции с нулевыми коэффициентами.
Пример:
Ограничения:
X1,x2≥0
L=8x1+12x2→max
L=-8x1-12x2→min
Поиск решения с поиска исходного базиса:
X’1=0; x’2=0; x’3=440; x’4=65; x’5=321 – первое опорное решение
L’=0
X3,x4,x5-базисные X1,x2-свободные
Используя систему 1’ выразим базисные переменные через свободные:
X3=440-2x1-4x2 X4=65-0,5x1-0,25x2 X5=320-2x1-2,5x2
L=-8x1-12x2
Из выражения ЦФ видно что Х1 увеличивается или Х2 увеличиваясь может уменьшить L ЦФ. Примем х2=0
Тогда x1 ,будем увеличивать переводя из свободной в базисную, до тех пор пока одна из базисных переменных не станет равной нулю ( пока они неотрицательны)
→
Переменную х1 можно увеличивать только до 130
Т.к. при х1=130 следует что х4=0 – т.е. переходит в свободные
2 этап: x21=130; x22=0; x32=180; x42=0; x52=60.
Переменные рассчитываются из уравнения системы при x2=0 x1=130
Вычисляем значения ЦФ: L2=-8*130-12*0=-1040
Выразим ЦФ через новые свободные переменные
L=-8x1-12x2=-8(130-0,5x2-2x4)-12x2=-1040-8x2+16x4
Преобразуем систему уравнений ограничений применительно к новому базису, т.е. из предыдущей системы уравнений выразим новые базисные переменные через новые свободные
X1=130-0,5x2-2x4 X3=440-2(130-0,5x2-2x4)-4x2
X5=320-2(130-0,5x2-2x4)-2,5x2
Как видно из выражения ЦФ для уменьшения нужно увеличивать свободную переменную х2 до такого значения пока базисные переменные неотрицательные
Принимая х4=0, получим
→
Третий этап: х23=40; x13=110; x33=60; x43=0; x53=0.
L3=-8*410-12*40=880-480=-1360
Выпазим ЦФ через новые свободные переменные:
L=-1040-8x2+16x4=-1040-8(40-2/3*x5+8/3*x4)+16x4=1360-16/3*x4+16/3*x5
Принимаем х5=0 и вычисляем новое значение х4
Х4≤-15 Х4≤33 Х4≤15 X54=0; x44=0; x34=0; x14=60; x24=80
L4=-1440 L=-1440+4/3*X3+8/3*X5
Дальнейшее уменьшение ЦФ за счёт увеличения св. переменных возможно, следовательно предыдущее решение оптимально.
Теория:
Допустим, что в канонической форме сформирована задача линейного проектирования.
Допустим, что система ограничений преобразована так, что переменные выражены через остальные, т.о. имеем базисные и свободные переменные.
Основная идея метода это переход от базиса Б к базису Б’, так что бы при этом ЦФ уменьшалась или, по крайней мере не увеличивалась.
Т.О. в конечном счете находим либо оптимальное решение либо выясняем, что задача решений не имеет.
Переход к базису Б’ осуществляется путем удаления из базиса Б какой-либо базисной переменной и введение в него св. переменной. Это связано с перестройкой системы ограничений.
Новой системой ограничения будет соответственно новый базис и новое значение ЦФ.
Исходя из условий задачи записывают огр. и ЦФ:
Сист:X1=b1-(a1,r+1xr+1+a1,r+2+..+a1,nxn)
X2=br-(ar,r+1xr+1+ar,r+2xr+2+..+ar,nxn)
L=C0-(cr+1xr+1+cr+2xr+2+..+cnxn) (2)
X1..xr-базисные Xr+1....xn –свободные
При bi≥0: Б{x1,x2…xr}
Из выражения (2) следует, что для уменьшения ЦФ надо добиться того, что бы выражение в круглых скобках стало больше 0.
Это можно сделать при соблюдении условия неотрицательности базисной переменной.
Здесь в зависимости от знаков коэффициентов возможны 2 случая:
Это значит что значения ЦФ можно уменьшить, увеличивая свободную переменную Xj оставляя остальные свободные переменные равными нулю.
Будем иметь следующую систему ограничений:
X1=b1-a1jxj X2=b2-a2jxj Xr=br-arjxj L0=c0-cjxj
Увеличивая переменную хj мы должны следить за условием неотрицательности 1ых переменных.
Из системы (4), учитывая что все bi>0, видно что последнее условие зависит от знаков коэффициентов а.
Возможны 2 случая:
Это значит что переменную Xj можно увеличивать неограниченно, что приведет к уменьшению ЦФ , следовательно конечный минимум ЦФ не достигается
Тогда для положительного коэффициента следует найти отношение Bi/aij=K>0, и выбрать наименьшее из этих отношения.
Это значит, что для соблюдения условий неотрицательных базисных переменных свободную переменную Xj можно увеличивать до значения не больше К, а остальные свободные переменные оставляют равными 0.
X1=b1-aijK X2=b2-a2jK … Xi=bi-aijK=0 Xr=br-arlK
Как видно переменная Xi исключается из базиса, вместо неё Xj
На данном этапе ЦФ уменьшилась или как минимум не изменила своего значения L0=c0-cjK≤c0
для перехода к следующему этапу нужно преобразовать систему (1) и ЦФ применительно к новому базису и затем вычисления повторяются.
Нахождение исходного базиса.
В тех примерах исходный базис очевиден т.е. из уравнений ограничений всегда можно выразить базисные перменные через свободные
Если исходный базис неочевиден, то в этом случае применяется метод симплекс преобразований.
|
X1 |
X2 |
.. |
Xn |
Свобод. член |
|
A11 |
A12 |
… |
A1n |
B1 |
|
A21 |
A22 |
.. |
A2n |
B2 |
|
.. |
.. |
.. |
.. |
… |
|
Am1 |
Am2 |
.. |
amn |
Bm |
Если bi=<0 то умножают на (-1) всю строку
Среди коэффициентов сост. столбцы. Ищется такой столбец в котором есть хотя бы один положительный коэффициент.
Если несколько положительных, то выбирают который соответствует наименьшему отношению.
Строка- разрешающая строка.
Далее элементы разрешающей строки делятся на раз-щий элемент и переписываются в новую таблицу на соответствующие места.
Другие строки новой таблицы получают путем сложения соответствующих строк исходной таблицы со строкой разрешающего элемента.
Причём строку разреш. Элемента нужно умножить на такое число, что бы в клетка выделенного столбца были бы нули.
Данную процедуру продолжают пока не будут получено неотрицательное базисное решение.( m-разных столбцов у которых один коэффициент равен 1, а остальные нулю)
Пример:
Умножив последнюю строку на (-1) получаем искомый результат, а именно исходный базис
Б={x2=53, x4=63, x5=11, x6=26}
Столбцы базисных переменных имеют 1 и остальные нули, а столбцы свободных переменных заполнены числами.