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.


 

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

84155. Культура и духовная жизнь общества. Культура как определяющее условие становления и развития личности 31.83 KB
  Культура как определяющее условие становления и развития личности. Культура это сумма материальных творческих и духовных достижений народа или группы народов. В широком смысле культура это уровень материального и духовного развития общества. В частных смыслах культура это и некие вечные духовные ценности и степень образованности общества и его политическая культура и его бытовая культура и материальная культура и нравственное или эстетическое развитие народа и т.
84156. Аналитика внутреннего мира человека: проблема счастья, смысл жизни, проблема смерти и бессмертия. Творческая жизнедеятельность как выражение личностного начала 37.67 KB
  Внутренний мир человека это единый духовный опыт взаимодействия его личности как с внешними фактами бытия так и с собственным я. Таким образом внутренний мир человека дан ему непосредственно в прямом созерцании собственным сознанием собственных же процессов сознания. Поэтому для человека в его внутреннем мире одинаково очевидны и процессы сознания вызванные внешними фактами бытия и процессы сознания вызванные деятельностью его собственного я ведь для его сознания и те и эти процессы есть явления одной внутренней природы...
84157. Общественный прогресс. Противоречивый характер его содержания. Критерии общественного прогресса. Гуманизм и культура 34.4 KB
  Критерии общественного прогресса. Идея прогресса человеческого общества стала формироваться в философии с древнейших времен и опиралась на факты умственного движения человека вперед что выражалось в постоянном приобретении и накоплении человеком новых знаний позволяющих ему всё более понижать свою зависимость от природы. Таким образом идея общественного прогресса зародилась в философии на основе объективных наблюдений социальнокультурных преобразований человеческого общества. Поскольку философия рассматривает мир как целое то...
84158. Предмет философии и специфика философского мышления. Основные содержательные аспекты философского знания и главные мировоззренческие направления в его развитии 37.34 KB
  Основной особенностью философии её отличием от других видов знания является то что она пытается создать целостную картину мира стремится к максимальному обобщению результатов познания. Таким образом объектом изучения то есть предметом философии в самом широком не конкретном смысле является непосредственно сам мир как таковой. Главный метод философии состоит в том что она изучает не мир в целом то есть не мир как простую совокупность фактов и явлений у каждого из которых есть своя сущность а мир как целое то есть мир как единый...
84159. Общая характеристика античной философии. Ее космоцентризм. Основные натурфилософские школы и виднейшие их представители 63.92 KB
  Слово космос для эллинов не было названием какойлибо природной сферы окружающего мира наоборот этим термином древние греки характеризовали некую неприродную суть мира. Поэтому естественно что понимая мир как космос античные философы пытались выявить источники космической разумности порядка и гармонии мира. И начали они эти попытки с наиболее наглядной данности мира с окружающей природы. Именно на этом этапе древнегреческая мысль стала философией поскольку отказалась от мифологических объяснений возникновения мирового порядка из...
84160. Античная классика: моральная философия сократа; проблема «эйдосов-идей» в философии платона; Аристотель о материи и форме 42.93 KB
  Поэтому чувственно воспринимаемые вещи обязаны своим существованием только приобщением к идеям. Но в этом приобщении вещи не могут брать от идей всё их совершенство поскольку являясь миром вещей они не истинны а поэтому они бледные несовершенные копии этих идей. Они не верят тому из них кто сумев вырваться из подземелья и увидев реальные вещи возвращается к ним и говорит им о мире за пределами пещеры. В своём учении о материи и форме Аристотель пытается ответить на вопрос почему существуют вещи : 1.
84161. Общая характеристика средневековой философии. Ее основные направления и виднейшие представители. Теоцентризм средневековой философии 43.24 KB
  Так за счет чего же возникает эта реальная общность некоей группы единичных вещей Только за счет того что в каждой из единичной вещи растворено нечто реально общее которое и образует их реальную общность и это реально общее во всех единичных вещах есть универсалии; универсалии существуют после вещей в человеческом разуме как понятия как результат абстракции. В природе же их уже нет потому что в природе онтологически существуют только единичные вещи. Нет реально универсалий и в голове человека поскольку даже при всплывании из...
84162. Характеристика философии эпохи возрождения. Социально-исторические и научные предпосылки ее становления. Антропоцентризм и гуманизм в философии возрождения 40.06 KB
  Гуманизм то есть признание человека главной ценностью жизни. Антропоцентризм то есть тип мышления который центром и смыслом исследования содержит человека и его жизнь. Как возрождение приоритета человека в социальном укладе и в общем смысле жизни. Мировоззрение таким образом приобрело в эту эпоху ярко выраженный гуманистический характер где главной ценностью мира признавались личность человека его права на свободу и счастье.
84163. Характеристика философии нового времени (XVI-ХVIII). Ее основные направления и виднейшие представители (Бэкон, Декарт, Гоббс, Локк, Спиноза, Лейбниц, Беркли, Юм) 58.21 KB
  Активный процесс философского осмысления новых проблем и новых знаний пробудил интерес к разработкам в методологии познания. Исходя из этого опыт имеет три преимущества перед рациональными способами познания: 1. Следовательно опыт объективен в отличие от рационального познания и вследствие этого полученные из него знания имеют общепринимаемую обязательность. Потому что сами чувства которыми человек воспринимает природу это не чистый инструмент познания собирающий в себя сведения таковыми каковы они есть в природном виде.