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.


 

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

60861. Построение трехмерной сцены 94.5 KB
  Более светлые и тонкие линии сетки называются главными mjor lines а самые светлые и тонкие вспомогательными minor lines как показано на рис. По умолчанию главной является каждая десятая линия сетки. Под шагом линий сетки понимается расстояние между вспомогательными линиями вы раженное в текущих единицах измерения. По умолчанию шаг сетки равен 10 системным единицам то есть 10 дюймам.
60862. Використання технології програми „Intel Навчання для майбутнього” для створення сучасних навчальних інформаційних ресурсів на уроках технології 995 KB
  Змінюються цілі і завдання що постали перед сучасною освітою в інформаційному суспільстві особистісноорієнтована система навчання поступово приходить на зміну традиційній. Традиційні методи навчання замінюються інноваційними що передбачають зміну акцентів в навчальній діяльності спрямованій на інтелектуальний розвиток учнів за рахунок зменшення долі репродуктивної діяльності використання завдань для перевірки різних видів діяльності учнів збільшення завдань для пояснення навколишнього світу тощо. Програма IntelНавчання для...
60863. ГОТУЄМОСЬ ДО ДПА 50.5 KB
  Атестаційні контрольні роботи з української мови містять сім завдань серед яких: три тестових завдання закритого типу що передбачають вибір однієї правильної відповіді з трьох запропонованих варіантів...
60864. Сохранение энергии. Интегрированный урок (английский язык и страноведение) в теме: «Наука и технический прогресс» 117 KB
  Развитие навыков чтения с извлечением информации и общего понимания текста Понимание аудио и видео роликов по теме эффективность энергии. Для этого предлагается просмотреть видео эпизод...
60867. Україна – наш спільний дім. Моя Батьківщина 2.3 MB
  Україна золотий чарівний край наша рідна країна. Так сподобалася Богові та місцина що Він став часто сюди навідуватися зі словами: Рушаймо у край Кажуть що з того і пішла назва нашої держави Україна.