Симплексный метод решения задач линейного программирования (стр. 2 из 2)
разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы;
строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место;
в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1;
столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же;
строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же;
в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:
В результате получают новую симплекс-таблицу, отвечающую новому базисному решению. Теперь следует просмотреть строку целевой функции (индексную), если в ней нет отрицательных значений (в задачи на нахождение максимального значения), либо положительных (в задачи на нахождение минимального значения) кроме стоящего на месте
(свободного столбца), то значит, что оптимальное решение получено. В противном случае, переходим к новой симплекс таблице по выше описанному алгоритму.3.Алгоритм симплексного метода решения задач линейного программирования
Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:
1. Привести задачу к каноническому виду.
2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости Привести системы ограничений).
3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода.
4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается.
5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.
4.Пример решения задачи симплексным методом
Решение:
Приводим задачу к каноническому виду.
Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x6 с коэффициентом +1. В целевую функцию переменная x6 входит с коэффицентом ноль (т.е. не входит).
Получаем:
Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.
Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).
Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:
Δk = CбXk — ck
Где Cб = (с1, с2, ... , сm ) — вектор коэффициентов целевой функции при базисных переменных;
Xk = (x1k, x2k, ... , xmk ) — вектор разложения соответствующего вектора Ак по базису опорного решения;
Ск — коэффициент целевой функции при переменной хк.
Оценки векторов входящих в базис всегда равны нулю. Опорное решение, коэффиценты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу
Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце "Б" записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов соответствует номерам разрешенных неизвестных в уравнениях ограничениях. Во втором столбце таблицы "Сб" записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце "Сб" оценки единичных векторов, входящих в базис, всегда равных нулю.
В последней строке таблицы с оценками Δk в столбце "А0" записываются значения целевой функции на опорном решении Z(X1).
Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ1 = -2, Δ3= -9 для векторов А1 и А3 отрицательные.
По теореме об улучшении опорного решения, если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше.
Определим, введение какого из двух векторов приведет к большему приращению целевой функции.
Приращение целевой функции находится по формуле:
.Вычисляем значения параметра θ01 для первого и третьего столбцов по формуле:
Получаем θ01 = 6 при l = 1, θ03 = 3 при l = 1 (табл.1).
Находим приращение целевой функции при введении в базис первого вектора ΔZ1 = — 6*(- 2) = 12, и третьего вектора ΔZ3 = — 3*(- 9) = 27.
Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ03 достигается в первой строке (l = 1).
Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (табл.2)
Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.
Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (табл.3).
Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные
Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.
Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).
5.Заключение
Решение задач линейного программирования – это достаточно трудоемкий процесс, особенно при большом числе переменных и ограничений. Поэтому решать такие задачи целесообразно с применением ЭВМ. Табличный симплекс-метод хорошо приспособлен для программирования и машинного счета.
Существуют программные реализации симплекс-метода. В настоящее время появились интегрированные математические программные системы для научно-технических расчетов: Eureka, PCMatLAB, MathCAD, Derive Maple V, Mathematica 2, Mathematica 3 , и др.
Широкую известность и заслуженную популярность приобрели математические системы класса MathCAD, разработанные фирмой MathSoft (США). Это единственные математические системы, в которых описание математических задач дается с помощью привычных математических формул и знаков
6.Список используемой литературы
1. Ашманов, С.А. Линейное программирование / С.А.Ашманов. – М.: Наука, 1981. – 304 с.
2. Вентцель, Е.С. Исследование операций: Задачи, принципы, методология / Е.С.Вентцель. – М.: Высшая школа, 2001. – 208 с.
3. Гольдштейн, Е.Г. Линейное программирование: Теория, методы и приложения / Е.Г.Гольдштейн, Д.Б.Юдин. – М.: Наука, 1969. – 736 с.
4. Кофман, А. Методы и модели исследования операций / А.Кофман. – М.: Мир, 1966. – 523 с.
5. Силич, В.А. Системный анализ и исследование операций: учебное пособие / В.А. Силич, М.П. Силич. – Томск: Изд-во ТПУ, 2000. – 96 с.
6. Силич, В.А. Системный анализ экономической деятельности: учебное пособие / В.А.Силич. – Томск: Изд. ТПУ, 2001. – 97 с.
- Хэмди, А. Таха. Введение в исследование операций. пер. с англ. / А. Таха Хэмди. – М.: Издательский дом «Вильямс», 2007. – 912 с.