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.


 

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

28654. Государственный строй России в начале XVIII в. Образование Российской империи. Реформы центральных органов государственного управления. Сенат. Синод. Коллегии 13.76 KB
  Реформы центральных органов государственного управления. Социальноэкое развитие рост сопротивления крестьянства тяжёлые войны диктовали необхть серьёзных реформ госго аппарат проведение котх привело к созданию централизованной системы органов управления. Претерпела изменения также система местного управления. В губерниях и провинциях было учреждено большое число различных должностных лиц ведавших отдельными вопросами управления.
28655. Реформы Петра I: военная, судебная, губернская и др 15.32 KB
  Император обозначил задачи коте возлагались на полицию: борьба с угой преступтью охрана общго порядка обеспече санитарной и пожарной безопти борьба с нищенством проституцией пьянством азартными играми контроль за соблюдением паспортного выдавались на 3 г режима и ловля беглых и беспаспортных. стало вводиться новое территориальное деление госва: Россия была разделена на 8 губерний по котм расписали все уезды и города. Во главе судебной системы стоял монарх котй решал самые важные госые дела. По его инициативе возникли...
28656. Разложение феодально-крепостнического строя и развитие буржуазных отношений в первой половине XIX в. Изменение в общественном строе 14.26 KB
  Они обладали монопольным правом на владение крепостными людьми. В разви правового положя духва необхо отметить 2 след. было предоставлено право покупать земли. о вольных хлебопашцах помещики получили право отпускать своих крестьян на волю за установленный самими помещиками выкуп.
28657. Кризис феодально-крепостнического строя в России и падение крепостнического права в 60-е гг. XIX в. Развитие капитализма в России 13.14 KB
  Посессионная промсть окончательно показала свою экую несостоятельность в силу чего по инициативе самих заводчиков была перестроена на новый лад. Вотчинная промсть основанная на труде крепостных крестьян также приходила в упадок. В то же время активно развивалась капиталистичя промть купеческая и крестьянская. Рост капиталистой промти в стране требовал все больше и больше свободных рабочих рук.
28658. Крестьянская реформа 1892 г. Личное освобождение крестьян. Земельные наделы. Выкупы. Крестьянское самоуправление. Общественный строй России 2-ой половины XIX в. 15.01 KB
  Для разработки проекта реформы в 1857 г. В губерниях обсуждением проекта реформы занимались дворянские комитеты их предложения обрабатывали редакционные комиссии Я. Текущую деятть по подготовке реформы возглавлял зам. Статус крестьянина последовательно менялся в ходе осущния реформы: первоначально помещик сохранял право собстти на земли полученные крестьянами в резте реформы за коте последние меннообязанными и фактически зависели от помещика.
28659. Буржуазные реформы 60-70-х гг. XIX в.: земская, городская, судебная, финансовая и военная 15.05 KB
  Земская реформа. В 1864 г. были изданы Положения о губернских и уездных земских учреждениях. Роль распоряди-х органов вып-ли губернские и уездные земские собрания, члены кот-х избирались по 3м избирательным куриям: к 1й относились уездные помещики, крупные торговцы и промышленники
28661. Революционная ситуация 1879-1881 гг. Крепостническая реакция и контрреформы 80-90-х гг. XIX в. 14.17 KB
  Дознание по таким делам осуществлялось корпусом жандармов. все наиболее важные дела по политим преступлениям стали рассмся Особым присутствием сената с участием сословных представителей. из компетенции суда присяжных были выведены дела о печати в 1874 г. из ведения общих судов дела о противозаконных сообществах и участии в них в 1878 г.
28662. Предмет и метод истории и права России 12.37 KB
  История государства и права России изучает политические и правовые институты существовавшие в процессе исторического развития Российского государства. История государства и права России рассматривает конкретные политические и правовые явления прежде всего фактический материал для установления закономерностей общих поступательных тенденций развития российского государства и права. В этом история государства и права неразрывно связана и с общей историей России и с теорией государства и права. Отличия состоят в том что история изучает более...