![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Алгоритм симплекс-метода
Будем считать, что известна исходная К-матрица К(0) задачи линейного программирования, определяющая исходный опорный план В симплексном методе последовательно строят К-матрицы
Шаг 1. Вычисляем для столбцов Шаг 2. Если является оптимальным, а есть оптимальное значение линейной формы Шаг 3. Если
Направляющий элемент на S-й итерации метода есть элемент Шаг 4. Вычисляем компоненты вектора Шаг 5. Производим один шаг метода Жордана–Гаусса с направляющим элементом
Пример 3.3. Симплекс-методом решить ЗЛП:
Х1 + 2Х2 2Х1 + Х2 -Х1 + Х2 Х2 £2 (3.58) Х1
Х1 + 2Х2 + S1 = 6 2Х1 + Х2 + S2 = 8 (3.59) -Х1 + Х2 + S3 = 1 Х2 + S4 = 2 Целевая функция будет иметь вид Расширенная матрица системы линейных уравнений (3.59) является исходной К-матрицей К(0) ЗЛП, которая определяет исходный опорный план:
Результаты последовательных итераций симплекс-алгоритма удобно оформить в виде симплексной таблицы. Таблица 3.1
На второй итерации S = 2, все
определяемый К-матрицей К(2), оптимальный, Оптимальное значение линейной формы равно:
Пример 3.4. Симплекс-методом решить ЗЛП: max (2X1+X2) (3.60) X1-X2 X1 X1,2 Приводим ЗЛП к каноническому виду max (2X1+X2+0 S1+0S2) X1-X2+ S1=10 (3.62) X1+ S2=40 Результаты последовательных итераций записываем в симплекс-таблицу. Таблица 3.2
Из симплекс-таблицы при S = 2 следует, что согласно шагу 3 симплекс-алгоритма данная ЗЛП не имеет конечного решения, т.к. отрицательная симплекс-разность Итак,
3.5. Двойственный симплекс-метод (Р-Метод) Пример 3.5. Рассмотрим следующую ЗЛП: min(2Х1 + 4Х2) 3 Х1 + Х2 4 Х1 + 3 Х2 Х1 + 2 Х2 Х1,2 Приведем рассматриваемую ЗЛП к каноническому виду max (-2 Х1 -4 Х2) 3 Х1 + Х2 - S1 = 3 4 Х1 + 3 Х2 - S2 = 6 Х1 + 2 Х2 - S3 = 3 или max (-2 Х1 -4 Х2) - 3 Х1 - Х2 + S1 = - 3 - 4 Х1 - 3 Х2 + S2 = - 6 (3.64) Х1 + 2 Х2+ S3 = 3 Рассмотрим расширенную матрицу системы линейных уравнений (3.64):
Матрица
системы уравнений, причем
Так как все симплекс-разности матрицы При решении задачи симплекс-методом текущее базисное решение является допустимым, но неоптимальным. Эти соображения позволяют построить метод решения определенного класса ЗЛП. В этом методе, называемом двойственным симплекс-методом, на каждой итерации обеспечивается выполнение условия оптимальности текущего базисного решения, не являющегося допустимым. Критерием окончания процесса итераций является получение допустимого решения.
Дата добавления: 2014-12-29; Просмотров: 830; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |