Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
17 Симплексный и двойственный симплекс -метод.
Симплекс-метод - один из способов решения ЗЛП , т.е. задач вида: max С1Х1+ С2 Х2 +…+ Сn Хn (1) при ограничениях
А11 Х1 + … + А1n Хn = А10,
А21 Х1 + … + А2n Хn = А20,
…………………………….
Аm1 Х1 + … + А1n Хn =Аm0,
Xi≥0 (3),
Он основан на последовательном переборе опорных точек множества до пустимых решений зада чи.
Алгоритм метода:
1.выбирается базис В таким образом, чтобы раз ложение А0 =( А10 , А20…… Аm0) было неотрицатель ным. Тогда n-мерный вектор Х0=( Х1 , Х2…… Хm, 0,….,0) будет опорным планом(допустимым ре шением) ЗЛП. Значение функции на этом плане получается подстановкой Х0 в (1) - F(X0). Обозначим ∆j=Сsi Xsi – Cj – оценки векторов условий.
2.Проверка на оптималь ность: если все оценки векторов условий ∆j ≥0, то план оптимальный. Тогда процесс прекраща ется.
3.Выявление столбцов Аj, таких, что ∆j<0 и Хij ≤0 для всех i. Тогда задача не разрешима в силу неогра ниченности линейной фор мы сверху.
4.Если всем векторам Aj соответствуют ограничен ные ребра, то выбирается минимальная оценка ∆k = min ∆j<0 и переход к сле дующей итерации.
5. Выбор разрешающего столбца Аsl : t0 = min {Xsi/Xik}= Xsl/Xlk . Вектор Аsl подлежит исключению из базиса, а вектор Ак-включению в базис.
6. Преобразование таблицы по рекурентным формулам: Хlj(1)= Хlj(0) / Хlk(0), Хlj(1)= Хlj(0) - Хlj(1) *Xik(0) (il).
7. Переход к шагу 2. процесс происходит до тех пор, пока не будет по лучен оптимальный план, либо не будет установлена неразрешимость исследу емой задачи.