- •Глава 4. Линейное программирование
- •4.1. Постановка задачи
- •В общем случае модель задачи лп имеет вид
- •4.2. Примеры задач линейного программирования
- •Задача составления рациона или как экономно питаться
- •4.2.2. Задача оптимального планирования
- •4.2.3. Сбалансированная транспортная задача
- •4.2.4. Общая распределительная задача
- •4.2.5. Задача планирования работы оборудования
- •4.2.6. Игра двух лиц с нулевой суммой как задача линейного программирования
- •4.2.7. Резюме
- •4.3. Формы записи задач линейного программирования и способы приведения к ним
- •4.3.1. Каноническая форма задач лп
- •4.3.2. Стандартная форма задачи лп
- •4.4. Упрощение модели
- •4.5. Основные понятия лп. Свойства задач лп
- •4.6. Геометрия задач лп
- •4.7. Выделение вершин допустимого множества
- •4.8. Методы решения задач лп
- •4.9. Симплекс-метод
- •4.9.1. Харатеристика метода
- •4.9.2. Переход от одного базисного решения к другому
- •4.9.3. Признак оптимальности. Основные этапы симплекс-метода
- •4.9.4. Построение начального базисного решения
- •4.9.5. Связь между параметрами последовательных итераций
- •4.9.6. Алгоритм симплекс-метода
- •4.9.7. Примеры
- •4.9.8. Учет двусторонних ограничений
- •4.10. Модифицированный алгоритм
- •4.11. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.2. Интерпретация двойственной задачи
- •4.11.3. Запись двойственной задачи в общем случае
- •4.11.4. Теоремы двойственности
- •4.11.5. Двойственный симплекс-метод
- •4.12. Параметрический анализ
- •4.12.1. Параметрирование вектора ограничениий
- •4.12.2. Параметрирование коэффициентов линейной формы
- •4.13. Задания для самостоятельной работы
4.12.2. Параметрирование коэффициентов линейной формы
Здесь рассмотрим три варианта параметрирования, отличающихся своими возможностями.
1. Коэффициенты критерия изменяются линейно от параметра:
C()=C+V,
а вектор V задается аналогично случаю изменения ресурсов.
Тогда задача параметрирования имеет вид:
(С+V)TXmax
AX B
X 0.
Запишем соответствующую двойственную задачу:
BTUmin
ATU C+V
U 0
Очевидно, что она представляет собой задачу параметрирования вектора ограничений, решение которой может быть получено вышеописанным методом. В результате найдем диапазон изменения параметра (0 < ), в котором базис двойственной задачиостается неизменным. В строке Z оптимальной таблицы двойственной задачи находятся переменные прямой задачи (двойственные к двойственной). Но значенияzjзависят только от базиса, поэтому в найденном диапазоне оптимальное решение также не меняется. Изменяться будет только критерий. При достижении критического значения произойдет смена базиса (оптимальной вершины), а значит, и оптимального решения прямой задачи. Проследить дальнейшее изменение решения можно после повторного решения двойственной задачи с векторм
Такое поведение следует и из геометрических представлений (рис. 4.14). Изменение коэффициентов линейной формы изменяет наклон линии уровня критерия, но не влияет на допустимое множество. При наличии критических значений изменение коэффициентов приводит к скачкообразному изменению оптимального решения – переходу из вершины в вершину (смежную).
2. Для небазисных переменных весьма просто можно определить диапазон изменения Cj, в котором оптимальное решение остается неизменным.
Действительно, пока при изменения Cj все Δj 0 оптимальное решение исходной задачи сохраняет свой статус. Так как
Δj = Zj-Cj,
то уменьшение Cj не может изменить знак оценки. Поэтому интерес представляет увеличение Cj. Пусть + j, j .0. Тогда
Δ’j = Zj – Cj - j = Δj - j 0.
Отсюда следует, что при j Δj исходное решение остается оптимальным.
3. Этот вариант основан на формуле вычисления относительных оценок в модифицированном симплекс-методе:
.
Она позволяет исследовать влияние изменения любых коэффициентов Сj.В общем случае эти коэффициенты являются некоторыми функциями параметра: Cj(). Тогда условия оптимальности запишутся в виде
Здесь обратная матрица соответствует оптимальному базису. Пока при изменении коэффициентов (т.е. ) эти неравенства выполняются, оптимальное решение не изменяется. Значение , при котором хотя бы одно из условий становится равенством, и будет критическим. Практически оно находится так: каждое условие записывается как равенство и определяются его корни; из всех корней выбирается наименьшее положительное. Это и будет
Очевидно, что данный вариант параметрирования пригоден как для линейных, так и нелинейных зависимостей от параметра. Однако в последнем случае его применение ограничено возможностью нахождения корней нелинейного уравнения.
Пример 4.8. Пусть ожидается изменение коэффициентов критерия в примере 4.2 (разд. 4.9.7) по закону:C1()=7 - 2, C2()=5 + . Необходимо определить критическое значение , если таковое имеется.
В оптимальной симплекс-таблице базисные индесы расположены в следующем порядке: 6, 2, 5, 1. Значит, Вычисляем:
Из условий оптимальности Δ30, Δ4 0 записываем уравнения
Первое уравнение имеет отрицательный корень, корень второго равен 11/8. Таким образом, До этого значения оптимальное решение не изменяется, при =11/8 имеем альтернативные оптимальные решения (линии уровня L()=34/8x1 + 51/8x2=Const параллельны границе2x1 + 3x2=19), а при >11/8 оптимальное решение переместится в вершину В (рис. 4.3).▲
Как отмечалось выше, параметрические решения могут быть получены также при одновременном изменении правых частей и коэффициентов критерия по линейной зависимости от одного параметра
при линейном изменении столбца условий Aj+Vj или строки ai+Vi.
В других случаях изменения модели поведение оптимального решения определяется решениями задачи одним из методов ЛП при разных значениях изменяемых параметров модели.