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.


 

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

67867. О ГРАЖДАНСКО-ПРАВОВОМ СОДЕРЖАНИИ ПОНЯТИЯ «МЕДИЦИНСКАЯ УСЛУГА» 97.5 KB
  Понятие услуги имеет принципиальное значение для определения существенного условия гражданских правоотношений складывающихся в сфере медицинского обслуживания их предмета. Услуги по определению К. Маркса представляют собой особую потребительскую стоимость поскольку...
67868. ФОРМЫ (ВИДЫ) ОГРАНИЧЕНИЙ ОСНОВНЫХ ПРАВ И СВОБОД И ИХ КОНСТИТУЦИОННО-ПРАВОВОЕ ЗАКРЕПЛЕНИЕ 95.5 KB
  Малько применимая к характеристике видов общеправовых ограничений не годится для анализа видов конституционно-правовых ограничений или может быть использована частично. Виды ограничений он классифицирует по следующим основаниям признакам: по способу формулирования в законе на прямые...
67869. МЕСТО ПРАВА НА ЛИЧНУЮ НЕПРИКОСНОВЕННОСТЬ В СИСТЕМЕ ОСНОВНЫХ ПРАВ И СВОБОД ЧЕЛОВЕКА И ГРАЖДАНИНА В РОССИЙСКОЙ ФЕДЕРАЦИИ 167 KB
  Право на личную неприкосновенность занимает одно из ведущих мест в системе личных конституционных прав и свобод человека. Личные права и свободы составляют первооснову правового статуса человека и гражданина являются важнейшим элементом всей системы прав и свобод и во многом характеризуют...
67870. СОДЕРЖАНИЕ ПРИНЦИПОВ НОРМАТИВНО-ПРАВОВОГО РЕГУЛИРОВАНИЯ НАЛОГОВЫХ ОТНОШЕНИЙ 106 KB
  Принципы регулирования налоговых правоотношений это основополагающие и руководящие идеи ведущие положения определяющие начала правового регулирования налогообложения. Поэтому основные принципы налоговых правоотношений одновременно выступают принципами налогового права.
67871. ФОРМИРОВАНИЕ ЗАКОНОДАТЕЛЬНОГО ОРГАНА ЯПОНИИ 65.5 KB
  По Конституции обе палаты обладали одинаковыми правами. Однако на практике палата пэров играла большую роль, т.к. она состояла из членов императорской фамилии, титулованной аристократии и финансовой знати. Влиятельность ее была гораздо выше...
67872. ПРАВОВОЙ СТАТУС И МЕСТО В СИСТЕМЕ ТАМОЖЕННЫХ ОРГАНОВ СЛУЖБЫ КОНТРОЛЯ СОБЛЮДЕНИЯ ЗАКОНОДАТЕЛЬСТВА В ТАМОЖЕННОМ ДЕЛЕ ФТС 114.5 KB
  В общем виде систему таможенных органов можно представить как обусловленную функциональной общностью единством целей и задач непосредственное осуществление таможенного дела совокупность таможенных органов. Она объединена функциональным единством органов...
67873. КОНСТИТУЦИОННЫЕ ГАРАНТИИ ПРАВ И СВОБОД ЧЕЛОВЕКА И ИХ ВЛИЯНИЕ НА ФОРМИРОВАНИЕ УГОЛОВНОЙ ПОЛИТИКИ РОССИЙСКОГО ГОСУДАРСТВА 134 KB
  Уголовная политика является составной частью социальной политики любого государства. С содержательной стороны она представляет собой такое направление политики которое определяется программой борьбы с преступностью и причинами ее порождающими...
67874. СОВРЕМЕННЫЕ ТЕНДЕНЦИИ ИЗМЕНЕНИЯ ЗАКОНОДАТЕЛЬСТВА ОБ АДВОКАТУРЕ РОССИИ 94 KB
  Адвокаты впервые получили «собственный» федеральный закон, на основе которого создана общероссийская некоммерческая организация — Федеральная палата адвокатов России, объединившая региональные адвокатские палаты; помимо традиционных юридических консультаций и коллегий адвокатов признан...
67875. ПРЕДВАРИТЕЛЬНЫЕ ЗАМЕЧАНИЯ К РЕГЛАМЕНТУ ПАЛАТЫ ОБЩИН ПАРЛАМЕНТА ВЕЛИКОБРИТАНИИ 2.86 MB
  По заказу редакции журнала Право и жизнь был подготовлен юридически точный но неофициальный перевод Регламента палаты Общин Парламента Великобритании. Иными словами Регламент не связан с каждым созывом палаты Парламента как в России а является стабильным несмотря на многочисленные...