Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
азисным переменным соответствует единичная матрица, то есть А = Сn-mEm. Так как А умножается на В-1, то В-1А = В-1(Сn-mEm) = В-1 С В-1, что соответствует матрице коэффициентов оптимальной таблицы. Следовательно, в оптимальной таблице в столбцах тех переменных, которые были базисными в НДБР, находится матрица В-1.
Матрица В-1 называется обращенный базис. В оптимальной таблице В-1 находится среди коэффициентов ограничений, стоящих в столбцах тех переменных, которые были базисными в исходной таблице.
Запишем теперь канонический вид задачи.
xn+I, I = - уравновешивающие переменные.
С1х1 +…+ Сnxn = F(x)
Умножим каждое ограничение на некоторое число , соответственно и сложим с выражением целевой функции, получим
х1(С1 + ) + … + хn(Cn + ) + + … + = F(x) +
. (1)
Значения можно подобрать таким образом, чтобы коэффициенты перед базисными переменными равнялись нулю. Без ограничения общности, например, первые m переменных являются базисными, тогда можно определить из системы
.
Если предположить, что подобрали таким образом, что перед базисными переменными коэффициенты равны нулю, а перед свободными - неотрицательны, то вид (1) будет соответствовать оптимальному виду таблицы. Следовательно, в оптимальной таблице коэффициенты в выражении целевой функции перед переменными, которые были базисными в исходной таблице, есть . Это и есть симплекс - множители. При этом,
.
Симплекс - множители - это такие числа , при умножении на которые каждого ограничения, соответственно, и сложении с выражением целевой функции будет получен такой вид целевой функции, что перед базисными переменными коэффициенты равны нулю, а перед свободными неотрицательны.
Замечание: если не все коэффициенты свободных переменных в выражении целевой функции неотрицательны, то это симплекс - множители промежуточного решения.
Обращенный базис и симплекс - множители позволяют использовать найденное решение ЗЛП, если происходят изменения условий задачи.
Пример.
2. Изменение значений правых частей ограничений
Правые части ограничений выражают ограниченные объемы ресурсов или минимальные нормы потребления и т.п. Предположим правые части ограничений изменились на . Другими словами, встает задача найти новый оптимальный план, при b = b + . Можно ли использовать результаты уже решенной задачи? Если задача была решена для прежнего значения b, то известными являются обращенный базис В-1 и симплекс - множители . При этом при определении В-1 и значения b никак не учитывались, эти значения влияют лишь на оптимальное значение целевой функции. Следовательно, новые значения целевой функции и переменных можно получить по формулам
F(x) = -
Замечание. Указанный прием можно использовать лишь при небольших изменениях в b, то есть базисное решение должно остаться допустимым (неотрицательным). Таким образом, если для базисных переменных получено хотя бы одно отрицательное значение, то решение задачи можно продолжить двойственным симплекс-методом.
Пример.
. Изменение значений коэффициентов целевой функции
Коэффициенты целевой функции выражают цены реализации, стоимость затрат и т.п. Если изменения произошли в коэффициентах целевой функции, можно ли воспользоваться решением задачи с прежними коэффициентами? То есть, если j = Cj + , а изменений в b не произошло, то и оптимальный план не изменится, а изменятся лишь оптимальные значения целевой функции и ее коэффициентов. В исходной таблице целевая функция имеет вид
F(x) = -C1x1 - C2x2 - … - Cnxn
Пусть в оптимальной таблице базисными оказались первые m переменных, следовательно, коэффициенты перед ними в оптимальной таблице должны быть равны нулю, исключим эти переменные из выражения целевой функции. Чтобы получить выражение целевой функции оптимальной таблицы в общем виде, используют оптимальную таблицу.
Умножим все уравнения системы соответственно на С1, С2, … , Сn и сложим с выражением целевой функции исходной таблицы в общем виде. Получим
х1 + … +0хm + = F(x) +
Полученное выражение представляет оптимальное выражение целевой функции. При этом оптимальность таблицы также определятся коэффициентами целевой функции. Заметим, что Сj не влияют на ограничения задачи. Если изменить Сj, то изменятся условия оптимальности:
если для Сj коэффициента целевой функции окажутся неотрицательными, то найденное решение сохранится, то есть если, , то решение не изменится
хб = хб, F(x) = - .
если хотя бы один коэффициент окажется меньше нуля, то следует перейти к другому базисному решению, то есть продолжить решение обычным симплекс-методом.
Пример.
4. Включение дополнительных переменных
Каждая переменная ЗЛП, если она не является уравновешивающей или искусственной, определяет план производства некоторой продукции, объем потребления и т.п. Предположим, поступило предложение выпускать новый вид продукции или использовать новую технологию. Стоит ли менять уже налаженное производство? Будет ли увеличение прибыли (сокращение расходов) весомым?
Пусть объем нового вида продукции хn+1, технологические коэффициенты известны
Р = (1(n+1), 2(n+1), … , m(n+1))T, предполагаемая прибыль от реализации единицы продукции Сn+1. Все остальные условия остаются прежними. Чтобы учесть эти изменения, не решая задачу с са