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.


 

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

84419. АНАЛИЗ ГОСУДАРСТВЕННОГО БЮДЖЕТА УКРАИНЫ 101.31 KB
  Первый заместитель главы администрации президента Ирина Акимова недавно заявила что объём теневой экономики в Украине составляет около 500 млрд грн. Запланирован рост по следующим статьям доходов бюджета: собственные поступления бюджетных учреждений 41 млрд грн или 244...
84420. Формы правления 75.5 KB
  Форма государственного правления - это организация вышестоящих органов государственной власти, характер и принципы их взаимодействия с другими органами государства, с политическими партиями, классами и социальными группами.
84421. Повышение эффективности улучшения работы пенсионных фондов 263 KB
  Актуальностью моей темы исследования заключается в том что, финансовая система сегодня является предметом дискуссий и обсуждений. В качестве проблем современного общество, которое призвана решать финансовая система, можно назвать: недостаточные темпы развития экономики...
84422. Страховой договор и страховое обязательство в гражданском праве России 73.16 KB
  Актуальность данной курсовой работы состоит в том, что идея страхования неразрывно связана с его универсальным значением как средства, способного устранить или, во всяком случае, сделать менее имущественно ощутимым (минимизировать) неблагоприятный результат воздействия отдельных обстоятельств...
84423. СУСПІЛЬНО-ГЕОГРАФІЧНІ ОСОБЛИВОСТІ ВІДТВОРЕННЯ НАСЕЛЕННЯ СВІТУ 135.98 KB
  Важливість і значущість питання, яке ми дослідили в цій роботі, в наші дні визнана усіма державами, що усвідомили небезпеку швидкого росту світового населення, особливо в країнах, що розвиваються, відстала економіка і нерозвинена соціальна сфера яких не в змозі обернути цей ріст на благо свого розвитку.
84425. Экспериментальное изучение самооценки в подростковом возрасте 332 KB
  Подростковый возраст — стадия онтогенетического развития между детством и взрослостью (от 11 до 17 лет), характеризующаяся качественными изменениями, связанными с половым созреванием и вхождением в зрелую жизнь.
84426. Проектирование приспособления для механической обработки детали «корпус» изделия ПУ 98.64 KB
  В машиностроении широко применяется разнообразная технологическая оснастка. Затраты на её изготовление и эксплуатацию составляют до 15-20% от себестоимости продукции, а стоимость и сроки подготовки производства в основном определяются величиной затраты труда и времени на проектирование...
84427. Управление рыночной экономикой 81.9 KB
  На какой бы ступени исторического развития ни находилось человеческое общество, люди, чтобы жить, должны иметь пищу, одежду, жилищные и другие материальные блага. Необходимые человеку средства существования должны быть произведены. Их изготовление совершается в процессе производства.