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.


 

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

24649. Порівняння – основний метод економічного аналізу 25 KB
  Порівняння це один із самих розповсюджених аналіз будь якого показника починаючи із порівняння звітних даних з плановими за попередній період з базисним показниками аналітичних підприємств конкурентів; аналіз порівняння до і після впровадження інвестицій порівняння якісних ознак фактично випущеної продукції зі стандартами і технічними умовами що дає можливість визначити.
24650. Методика аналізу обсягу випуску та реалізації продукції 28.5 KB
  Методика аналізу обсягу випуску та реалізації продукції. Аналіз випуску продукції передбачає загальну оцінку виконання плану оцінку впливу факторів на його величину аналіз ритмічності якості продії і її конкурентоспроможності оновлення продукції виконання плану з номенклатури і асортименту. Випуск продукції можна аналізувати у натуральному і вартісному виразі: 1. Для оцінки ритмічності і випуск продукції здійснюється за питомою вагою виробн продії в кожній декаді до місячного випуску і за допомогою узагальнюючого показника коефіцієнтів...
24651. Методика аналізу якості продукції 33 KB
  Методика аналізу якості продукції. Показники якості продукції є одними з найважливіших показників діяльності підприємства. Якість продукції залежить від багатьох факторів таких як: техніка і технологія впровадження іновацій організація виробництва і праці організація роботи служби матеріально технічного постачання трудова дисципліна та ін. Якість продукції впливає на обсяг товарної і реаліз.
24652. Аналіз динаміки та структури основних фондів 35 KB
  Характеристику руху о з дають коефіцієнти оновлення і вибуття Коефіцієнт оновлення=вартість прибулих о з за звітний період розділити на первісну вартість о з на кінець звітного періоду Показує яку частку від наявності на кінець звітного періоду складають нові о з Коеф вибуття= вартість вибулих о з за звітний період розділити на первісну вартість о з на початок звітного періоду Показує яка частина о з з якими підприємство починало свою діяльність у звітному році вибула через зношеність та інші причини. Технічний стан о з характеризується: Коеф...
24653. Аналіз ефективності використання основних фондів 26.5 KB
  Аналіз ефективності використання основних фондів. Під раціональним та найповнішим використанням діяючих промисловиробничих основних засобів розуміють той максимальний економічний ефект який отримує суспільство за певний період у вигляді відповідного обсягу та якості продукції. Економічна ефективність використання основних засобів визначається відношенням економічного ефекту одержаного на підприємстві за відповідний період до витрат необхідних для створення основних засобів. Для характеристики ефективності використання основних засобів...
24654. Оцінка забезпеченості підприємства трудовими ресурсами 31.5 KB
  Аналізуючи питання забезпеченості робочою силою потрібно пам'ятати що в сучасних умовах внаслідок помітних скорочень обсягів виробництва підприємства більше стикаються не з проблемою недостачі а з наявністю зайвої робочої сили необхідністю скорочення робочих місць і водночас збереження кваліфікованих кадрів на майбутнє. Із питанням забезпечення робочою силою тісно пов'язане питання закріплення кадрів на підприємстві. При цьому вивчають загальні показники прийняття та звільнення робітників і службовців розраховують коефіцієнти обороту...
24655. Аналіз ефективності використання робочої сили 24.5 KB
  прийому = Чпр сер Ч Коеф вибуття = Чвир сер Ч Коеф заг обор = Чпр Чвир сер Ч Коеф пот кадрів = Ч виб за власним бажанням сер Ч.
24656. Аналіз продуктивності праці 29.5 KB
  Розрахунок продуктивності праці: ПП = V серЧ V обсяг виробництва продукції сер Ч середньооблікова чисельність персоналу для окремих цехів: ПП = Vнат сер Ц сер Ч Vнат обсяг в натуральних одиницях сер Ц середньооблікова ціна Оцінка впливу обсягу виробництва продукції дельта ППв дельта ППв = Vф сер Цпл сер Чпл Пл. сер Цпл сер Чпл Оцінка впливу середньооблікової чисельності робітників дельта ППч = Vф чер Цпл сер ЧФ Vф сер Цпл сер Чпл Оцінка впливу середньої оптової ціни дельта ППсер ц = Vф сер Цф сер Чф Vф сер Цпл...
24657. Аналіз ефективності використання матеріальних ресурсів 25.5 KB
  Аналіз використання матеріалів здійснюється за наступними узагальнюючими показниками: матеріаловіддача зняття продукції із гривні витрат на матеріали це відношення обсягу випущеної продукції до загальної суми матеріальних витрат; матеріалоємність сума матеріальних витрат на випуск однієї гривні продукції це відношення загальної суми матеріальних витрат на обсяг виготовленої продукції. У процесі аналізу можна використати також допоміжні показники рівня використання матеріальних ресурсів: коефіцієнт використання матеріалів рівень...