Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм симплекс-метода
Будем считать, что известна исходная К -матрица К (0) задачи линейного программирования, определяющая исходный опорный план В симплексном методе последовательно строят К -матрицы ЗЛП, пока не выполнится критерий оптимальности или критерий, позволяющий убедиться в отсутствии конечного решения. Рассмотрим алгоритм S -й итерации симплексного метода. В начале S -й итерации имеем К -матрицу задачи линейного программирования, определяющую опорный план Шаг 1. Вычисляем для столбцов матрицы симплекс-разности и находим номер k из условия . Шаг 2. Если , то опорный план является оптимальным, а есть оптимальное значение линейной формы , иначе переходим к шагу 3. Шаг 3. Если aik ( S -1) , , то ЗЛП не имеет конечного решения, иначе находим номер l из условия Направляющий элемент на S -й итерации метода есть элемент . Шаг 4. Вычисляем компоненты вектора : Шаг 5. Производим один шаг метода Жордана-Гаусса с направляющим элементом . Присваиваем переменной S алгоритма значение S +1 и переходим к шагу 1.
Пример 2.9 Симплекс-методом решить ЗЛП: (2.71) Х1+2Х2 6 2Х1+Х2 8 -Х1+Х2 1 (2.72) Х2 2 Х1 0 Х2 0. Приводим систему линейных неравенств (2.72) к каноническому виду, вводя в каждое неравенство дополнительную переменную , где . Получим систему линейных уравнений: Х1+2Х2+S1=6 2Х1+Х2+S2=8 (2.73) -Х1+Х2+S3=1 Х2+S4=2 Целевая функция будет иметь вид f()=3X1+2X2+0 S1+0 S2+0 S3+0 S4 Расширенная матрица системы линейных уравнений (2.73) является исходной К -матрицей К (0) ЗЛП, которая определяет исходный опорный план: , , . Результаты последовательных итераций симплекс-алгоритма удобно оформить в виде симплексной таблицы. Таблица 2.2.
На второй итерации S= 2, все , следовательно, опорный план , определяемый К -матрицей К (2), оптимальный, Оптимальное значение линейной формы равно: Пример 2.10. Симплекс-методом решить ЗЛП: max (2X1+X2) (2.74) X1-X2 10 X1 40 (2.75) X1, 2 0 Приводим ЗЛП к каноническому виду max (2X1+X2+0 S1+0S2) X1-X2+ S1=10 (2.76) X1+ S2=40 . Результаты последовательных итераций записываем в симплекс-таблицу. Таблица 2.3
Из симплекс-таблицы при S=2 следует, что согласно шагу 3 симплекс-алгоритма данная ЗЛП не имеет конечного решения, т.к. отрицательная симплекс-разность соответствует столбцу , все элементы которого неположительны. Итак, .
|