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.


 

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

46396. Проблема промислової безпеки. Дії населення в очагах хімічної поразки 86 KB
  Проблема промислової безпеки значно загострилась з появою крупномасштабных хімічних виробництв в першій половині нашого сторіччя. Основу хімічної промисловості склали виробництва безперервного циклу, продуктивність яких не має, по суті, природних обмежень. Постійне зростання продуктивності зумовлене значними економічними перевагами великих настанов
46398. Бухгалтерський облік 664.71 KB
  Навчальними планами підготовки фахівців економічного спрямування кваліфікації «спеціаліст з обліку і аудиту» та «магістр з обліку і аудиту» у 9 семестрі передбачене вивчення дисципліни «Організація обліку». Поряд з аудиторними заняттями під час її опанування передбачається самостійна робота студентів, яка є невіддільною складовою навчального процесу.
46399. Модеми 26.5 KB
  За конструктивним виконанням модеми бувають вбудованими (вставляються в системний блок комп'ютера в один із слотів розширення) і зовнішніми (підключаються через один із комунікаційних портів, маючи окремий корпус і власний блок живлення). Однак без відповідного комунікаційного програмного забезпечення, найважливішою складовою якого є протокол, модеми не можуть працювати. Найбільш поширеними протоколами модемів є v.32 bis, v.34, v.42 bis та інші
46400. Массивы. Объекты. Ресурсы. Тип 65.5 KB
  Массив в PHP представляет собой упорядоченную карту – тип, который преобразует значения в ключи. Этот тип оптимизирован в нескольких направлениях, поэтому его можно использовать его как собственно массив, список (вектор), хеш-таблицу (являющуюся реализацией карты), стэк, очередь и т.д.
46401. Методичні вказівки. Сервіс і діагностика машин 945 KB
  Параметри технічного стану двигуна в цілому Діагностичний параметр Прямий структурний Непрямий що функціонально залежить від структурного Ефективна потужність двигунів: Зміна частоти обертання колінчастого вала при послідовному відключенні з роботи кожного з циліндрів с1 хв.1 Автомобільних – за СТ СЕВ 765 – 77 Характеристики вібрації шуму або звуку м с2 м с дБ Тракторних – за ГОСТ 18509 – 80 Максимальний крутний момент колінчастого вала Нм Прискорення частоти обертання колінчатого вала при розгоні без навантаження с2 Тиск...
46402. Розрахунок деталі ”Вал-шестерня” 2.3 MB
  Деталь ”Вал-шестерня” входить до фартуха токарно-револьверного верстату моделі 1Г340ПЦ, і призначений для переміщення фартуха у повздовжньому напрямку.
46403. Составление программ циклической структуры 64 KB
  Изучить основные операторы для организации циклов. Разработать алгоритм решения задачи. Составить программу решения задачи. Вычислить на ЭВМ значение интеграла на отрезке. Число разбиений отрезка интегрирования равен 100, метод интегрирования – метод трапеций.
46404. Психологічні умови попередження та врегулювання конфліктів у військовому колективі 158.5 KB
  Життєвий цикл конфлікту. Найважливіші з них: предмет конфлікту його об’єкт суб’єкти конфліктна ситуація інцидент структура. Виникнення спірної ситуації Сприйняття ситуації як конфліктної хоч би однією із сторін ні так Наявність конфліктної ситуації Виникнення інциденту ні так Розгортання конфлікту Відсутність конфлікту Рис. Конфліктна ситуація – це основна умова виникнення конфлікту на підставі порушення балансу інтересів учасників взаємодії.