11.Общая, каноническая, стандартная задача линейного программирования.
В общем виде задачи об использовании ресурсов и о диете можно записать в общем виде. Пусть дана система m линейных неравенств с n- неизвестными.
(7)
И
линейная функция
(8)
Необходимо найти такое решение Х=(х1,х2,…,хn) удовлетворяющее неотрицательности
x1≥0, x2≥0,…,xn≥0 (9).
При котором функция(8) принимает оптимальное (мин,мах) значение. Это задача называется ЗЛП.
Система(7) система ограниченная ЗЛП, функция (8) – целевая функция.
Допустимым решением ЗЛП называется решение Х=(х1,х2,…,хn) системы ограничении удовлетворения условиям неотрицательности.
Оптимальным решением решения ЗЛП наз-ся план х1,х2,…,хn при которой целевая функция принимает оптимальное значение. Мы рассмотрели ЗЛП в которых система ограничений состоят только из неравенств, такие ЗЛП называются СТАНДАРТНЫМИ. Но система ограничений может состоять и из линейных неравенств и из линейных уравнений – ОБЩАЯ ЗЛП. Если же система ограничений ЗЛП состоит только из уравнений то ЗЛП называют КАНОНИЧЕСКОЙ.
12. Симплексная форма злп.
f+Cr+1Xr+1 + ... + CnXn = bn min
Допустимое решение ЗЛП называется Базисным, если все его свободные неизвестные равны нулю, а соответствующие ему значения целевой функции f(b1,b2,…,br,0)=b0 называется базисным.
Симплексная форма ЗЛП удовлетворяет следующим требованиям: система ограничений должна быть такой что:
Все ограничения записаны в виде уравнений.
Правые части уравнений неотрицательны bi≥0, i=
Система состоящая из r уравнении имеет r базисных уравнений
Целевая ф-ия удовлетворяет условиям:
Она содержит только свободные переменные
Обязательная минимизация ( случай нахождения мах сводится на задаче нахождения мин по формуле махf=-minf
Все слагаемые целевой ф-ии перенесены влево кроме b0
13. Матричная форма симплексного метода. Критерии оптимальности плана и его отсутствия. Симплексные преобразования.
В симплексной форме ЗЛП соответствует симплексная матрица состоящая из коэффициентов при неизвестных, правых частей уравнений и функций.
x1 |
x2 |
xi |
Xn |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
…. |
…… |
……… |
……… |
0 |
0 |
1 |
0 |
…. |
….. |
…. |
….. |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
Базисное решение
=(в1,в2,….,в0,0…,0)
и базисное значение целевой функции.
При этом мы каждый раз будем получать
новую симплексную матрицу. По ней можно
определить является ли базисное решение
оптимальным с помощью следующего
критерия.
Критерий оптимальности плана.
Если в последней сторке (целевой строке) симплексной матрицы, все элементы положительны без учеты последнего в0, то соот-ии этой матрице на опорный план оптимален.
Критерий отсутствия оптимальности. Если в симплексной матрице имеется столбец в котором последний элемент Cs>0 а все остальные элементы не положительны то ЗЛП не имеет оптимального плана minf=-∞.
Если в симплексной матрице не выполняется оба критерия то в необходимо перейти к следующей матрице с помощью разрешающего элемента. ais >0. A)определяется разрешающий столбец по наибольшему из положительных элементов целевой строки. Cs=max(Cj). Целевая строка выбирается по наилучшему значению отношения элемента последнего столбца к соответствующему элементу S-го столбца. Bi/ais=min (bk/aks), aks>0.
Б) На пересечении разрешающего столбца и разрешающей строки и находится разрешающий элемент. Ais>0
Когда разрешающий элемент ais производят симплексные преобразование матрицы:
Все элементы разрешающей строки делятся на разрешающий элемент.
Все элементы разрешающего столбца кроме разрешающего элемента заменяют 0.
Все остальные элементы матрицы заменяют по правилу прямоугольника.
