Реферат Курсовая Конспект
Алгоритм симплексного метода решения задач линейного программирования - раздел Образование, Принятие решений в условиях неопределенности. (Егорова) Для Того, Чтобы Решить Задачу Симплексным Методом Необходимо Выполнит...
|
Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:
1. Привести задачу к каноническому виду
2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения
Симплексный метод включает в себя:
1. Нахождение начального опорного решения;
2. Способ перехода от одного опорного решения к другому, на котором целевая функция ближе к оптимальности;
3. Критерий оптимальности (этот критерий позволяет остановить поиск решений).
1.Предполагая, что заданная запись в канонической форме, т.е. в форме равенств :
F(x) = c1x1 + …+ cnxn → max
a11x1+a12x2+…+a1nxn=b1
a21x1+a22x2+…+a2nxn=b2
am1x1+am2x2+…+amnxn=bn
Для нахождения начального опорного решения применяем метод Гаусса и приводим систему ограничений к разрешенной системе.
После приведения к разрешенной системе получим:
x1+ … a1m+1xm+1+… a1kxk+… a1nxn=b1
x2+… a2m+1xm+1+… a2kxk+ … a2nxn=b2
xm+ amm+1xm+1+… amkxk+… 2mnxn=bm
Ā1= (10...0), Ā2=(01..0), Ām=(00..1)
X1= (x1,x2,x3)
X1= (b1,b2,bm)
Можно доказать, что эти вектора независимы, таким образом мы выясним, как найти начальное опорное решение.
2.Возьмем столбец с номером k и на этом столбце выберем aek (разрешенный элемент)
Применим метод Жордана:
а ) Делим строку L на aek
b'e = be/ aek ,треб.aek>0
b) далее получаем 0 для другого элемента этого столбца
b'i = bi – be/aek * aik ≥0 => bi/aik ≥be/aek .
Из этого неравенства выводим критерий выбора е , при условии, что знаем как выбрать k
min= bi/aik
Рассмотрим способ выбора столбца k.
Для этого 1-ое решение будем сравнивать с новым 2-ым решением .
F(X2)= Ʃ cibi – be/aek (Ʃ ciaik – ck)
Обозначаем Ѳk= be/aek
∆k = Ʃ ciaik – ck
Называется оценкой разложения вектора услов. Ak по базису опорного решения.
F(X2) = F(X1)- Ѳk*∆k
Если оценка меньше 0 ( ∆k < 0), то отсюда вывод:
Утверждение 1. Если в з.л.п. хотя бы для одного вектора условий оценка разложений отрицательная, то опорное решение может быть улучшено!
Утверждение 2. Критерий выбора k: выбираем из условий max{-Ѳk*∆k}, другими словами, перебираем все отрицательные оценки и берем наибольшее значение по модулю.
Утверждение 3. Опорное решение является оптимальным, если все оценки не отрицательны.
Оптимальное решение является единственным, если для любого вектора условий, не входящего в базис, оценка отлична от 0.
– Конец работы –
Эта тема принадлежит разделу:
При решении социально экономических задач приходиться принимать противоречивые интересы относящиеся к различным лицам и организациям В таких... Теория игр изучает процессы принятия оптимальных решений это раздел... Математическая теория игр была разработана американским уч ным Джордоном Неймоном и Марген Штеймах в году как...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм симплексного метода решения задач линейного программирования
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов