20551

Симплексный метод решения задач линейного программирования

Доклад

Математика и математический анализ

Запишем систему уравнений 5 в векторной форме: 6 где Aj B – вектор a элемент матрицы 1. Таким образом нулевые значения переменных удовлетворяют6 Векторы Аjj=n1nmможет служить базисом в mмерном пространстве. Любой небазисный вектор можно разложить по векторам базиса. Разложим некий небазисный вектор Ak по векторам базиса: Умножим 8 на положительную константу и вычтем 8 из 7 произвольная величина ее можно выбрать настолько малой что независимо от значения выражение в скобках будет всегда больше нуля так как 0...

Русский

2013-07-31

102.5 KB

7 чел.

Симплексный метод решения задач линейного программирования.

Симплексный метод или метод последовательного улучшения плана позволяет известному базисному решению построить другое базисное решение, для которого значение линейной формулы R > чем для исходного. Запишем систему уравнений 5 в векторной форме:  

   (6)

где Aj, B – вектор

a- элемент матрицы

1. Предположим, что известно какое-нибудь базисное решение, в котором m- переменных отличных от 0. . Таким образом нулевые значения переменных удовлетворяют(6)  Векторы Аj(j=n+1,…,n+m)может служить базисом в m-мерном пространстве. Любой небазисный вектор можно разложить по векторам базиса.

2. Разложим некий небазисный вектор Ak  по векторам базиса:

Умножим (8) на положительную константу  и вычтем (8) из (7)  

- произвольная величина ее можно выбрать настолько малой, что независимо от значения   выражение в скобках будет всегда больше нуля так как >0 (по определению) обозначим:  Для вектора Ak :yk=. При =0 будем иметь исходное базисное решение. Для получения другого базисного решения нужно взять>0. если коэффициенты вектора Ак - отрицательные, то получить новое базисное решение невозможно. В этом случае нужно взять другой небазисный вектор и разложить его по векторам базиса. Если и его коэффициенты будут меньше нуля, то следует разлагать следующий небазисный вектор до тех пор пока не получим разложение, в котором хотя бы одна переменная будет положительной.

3. Пусть не все коэффициенты  вектора Ак отрицательны следовательно при непрерывном возрастании , начиная от 0, первой обратиться в 0 та переменная (), для n-ой

Отношение будет минимальным и это отношение нужно принимать за  :

4. Допустим, что минимальное значение получается при l=1 то есть для первого из последовательности переменных : n+1,…..,n+m, то есть = следовательно при данном значение  (из(10)) будет равно 0 Другие же значения будут 0  для всех j=n+2,…,n+m. yn=. Вместо исходного базисного решения получим новое решение:

На основе нового базисного решения уравнения(9) запишется в виде. Сравнивая (11) с (7) приходим к выводу что в исходном базисе векторов Aj (j=n+1,..,n+m) . один из них Аn+1 заменим на вектор Аk и новое базисное решение удовлетворяет уравнению (11) Однако,  до сих пор не ясно как изменяется значение критерия при переходе к базисному решению. Подставим в выражение критерия исходное базисное решение следовательно  При новом базисном решении:  приращение

Если >0 при переходе к новому базисному решению, то этот переход целесообразен. В результате него в базисе вводиться небазисный вектор и образуется новый базис, по которому можно разложить следующий небазисный вектор и если снова получим  >0, то строим новый базис и по нему разлагаем следующий небазисный вектор и т.д. до тех пор пока замена базисных векторов небазесными приводит к увеличению критерия. Из (12) следует, что  >0 всегда когда и поэтому решение о переходе к новому базису можно проверить до определения при известных коэффициентах разложения вектора Ak.


 

А также другие работы, которые могут Вас заинтересовать

33953. Определение и формы выражения относительных показателей 11.17 KB
  Определение и формы выражения относительных показателей Относительные показатели представляют собой результат деления одного абсолютного показателя на другой и выражают соотношение между количественными характеристиками соц. Поэтому по отношению к абсолютным показателям относительные показатели являются производными вторичными. составляют относительные величины интенсивности.
33954. ДИВЕРТИКУЛ МЕККЕЛЯ 22 KB
  его стенка содержит все слои кишки. Клиническая картина В 95 случаев протекает бессимптомно Клиническая картина возникает при присоединении осложнений У детей возникает пептическое изъязвление близлежащей слизистой оболочки подвздошной кишки что нередко является причиной массивного кишечного кровотечения У взрослых Острый дивертикулит. Если в ходе операции обнаружен интактный червеобразный отросток необходима ревизия подвздошной кишки примерно на протяжении 100 см от илеоцекального угла Непроходимость кишечника вследствие...
33956. Механическая кишечная непроходимость. Классификация. Этиология. Патогенез. Клиника. Дифдиагноз и лечение. Причины смерти при механической непроходимости 46.5 KB
  Причины смерти при механической непроходимости. К сочетанной механической непроходимости кишечника относят инвагинацию внедрение одной кишки в другую. При этом подчеркивается только этиологический момент возникновения непроходимости наличие спаек в брюшной полости которые могут быть результатом хирургических вмешательств или воспалительных заболеваний органов брюшной полости. При острой обтурационной непроходимости в кишках выше места препятствия начинают скапливаться...
33957. АБСЦЕСС ПОДДИАФРАГМАЛЬНЫЙ 23.5 KB
  При расположении абсцесса близко к передней брюшной стенке болевой синдром более выражен Тошнота икота Вынужденное положение больного на спине на боку или полусидя Температурная кривая носит гектический характер Озноб потливость При длительном течении пастозность кожи выбухание межрёберных промежутков в зоне локализации абсцесса обычно IXXI справа Тахикардия Одышка При пальпации ригидность мышц верхних отделов брюшной стенки и болезненность по ходу межрёберных промежутков Симптомы раздражения брюшины как правило...
33958. Организация труда исследователя 58.5 KB
  Правильная организация труда исследователя является одним из важнейших условий эффективности НИР и успешно завершения предпринятого исследования. Научное творчество - это своеобразный и очень сложный вид человеческой деятельности. Немало специальных исследований и книг посвящены вопросам организации труда исследователя.
33961. Апендикс 26.5 KB
  Илеоцекальный отдел кишечника расположен на границе тонкой кишки с толстой и включает в себя терминальный отдел подвздошной кишки слепую кишку червеобразный отросток и баугиниеву заслонку. В месте впадения тонкой кишки в толстую расположен илеоцекальный клапан баугиниева заслонка представляющая собой две складки слизистой оболочки которые препятствуют рефлюксу содержимого из толстой кишки в тонкую Илеоцекальный отдел кишечника получает артериальное кровоснабжение через подвздошноободочную артерию а. Далее лимфатические сосуды идуг...