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.


 

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

17669. Наближення дифракції Френеля і Фраунгофера в теорії дифракції 20.48 KB
  Наближення дифракції Френеля і Фраунгофера в теорії дифракції При вивченні дифракційних явищ в оптиці виникають деякі труднощі які не завжди мають точне розв’язання тому доводиться користуватися деякими наближеннями. Між дифракційними явищами Френеля та Фраунгофер
17670. Наближення Релея-Джинса і Віна формули Планка 16.21 KB
  Наближення РелеяДжинса і Віна формули Планка. Формула Планка: Наближення РелеяДжинса працює для малих частот або великих температур. Тобто виконується умова тоді можна розкласти експоненту в ряд: . Підставивши назад в формулу Планка отримаємо формулу РелеяДжинс
17671. Нелінійна поляризація класифікація нелінійних явищ 25.01 KB
  Нелінійна поляризація: класифікація нелінійних явищ. В оптиці взагалі кажучи можна говорити про багато параметричних явищ які в широкому розумінні можна віднести до нелінійних. До них наприклад можна віднести ефект Керра в якому під дією сильного електричного поля
17672. Обмін енергією між нелінійною поляризацією і електромагнітним полем 23.58 KB
  Обмін енергією між нелінійною поляризацією і електромагнітним полем. При распространении света в среде все такие явления связаны прежде всего с нелинейной зависимостью вектора поляризации среды Р от напряженности электрического поля Е световой волны. Среду мы будем п
17673. Одноосні кристали звичайні та незвичайні хвилі 46.76 KB
  Одноосні кристали звичайні та незвичайні хвилі. Оптически одноосными кристаллами называются кристаллы у которых свойства обладают симметрией вращения в некотором избранном направлении – оптической оси кристаллав более узком смысле: 2 главных значения диэлектрическ...
17674. Однофотонна інтерференція 18.6 KB
  Однофотонна інтерференція. Якщо розглядати випромінення на рівні окремих фотонів тобто з дуже малою інтенсивністю то також можна отримати інтерференційну картину але її природа буде дещо іншою. При проходженні окремих фотонів через щілину вони дифрагуватимуть і у...
17675. Оптичний резонатор лазера подовжні та поперечні моди 23.72 KB
  Оптичний резонатор лазера: подовжні та поперечні моди Оптичний резонатор коливальна система утворена сукупністю дзеркал в якій можуть збуджуватися і підтримуватися слабо затухаючі електромагнітні коливання оптичних і СВЧнадвисокі частоти діапазонів з випроміню
17676. Оптичний хвилевід. Числова апертура 32.31 KB
  Оптичний хвилевід. Числова апертура Оптичний хвилевід – пристрій для передавання інформації оптичним методом через оптичні волокна. В центрі такого волокна знаходиться гірська порода – кернпоказник заломлення який оточений полімерною оболонкою . Числова апертур
17677. Побудова Гюйгенса для анізотропних кристалів 279.35 KB
  Побудова Гюйгенса для анізотропних кристалів. Проходження світла крізь анізотропну речовину оптичні властивості якої в різних напрямках не однакові супроводжується рядом світлових явищ. Особливості цих явищ в анізотропних середовищах пов’язані з тим що індукований...