Теорема об оценках
т. е лин ф-я F приним макс знач в произв точке Х, явл-ся выпукл лин комбин-ей точек Х1,Х2,…,Хр, в которой ЦФ F принимает макс знач
26. Теорема об оценках
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче.
Третья теорема двойственности или теорема об оценках.
Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи математического программирования, точнее
Для этого в равенстве (2.36) дифференциалы заменим приращениями. ПолучимПри имеем Отсюда величина двойственной оценки численно равна изменению целевой функции при изменении соответствующего свободного члена ограничений на единицу. В прикладныхзадачах двойственные оценкиyf часто называются скрытыми, теневыми ценами или маргинальными оценками ресурсов.
Экономическая интерпретация
Таким образом относительная оценка i-ой дополнительной переменной дает величину прироста целевой функции на единицу увеличения элемента Bi вектора ограничений. Так как элемент Bi обычно представляет собой объем i-го ресурса то относительная оценка равная Yi называется оценкой ресурса (оценкой единицы i-го ресурса) ибо она представляет относительную ценность единицы дополнительного ресурса. Эти относительные оценки являются маргинальными оценками в том смысле что они действительны лишь при таком диапазоне изменения ресурсов Bi когда текущий базис остается оптимальным.
Маргинальная оценка ресурсов
Оценки ресурсов связаны скорее с ограничениями а не с переменными.
Однако они часто используются для вычисления оценочных или стоимостных показателей, связанных с переменными прямой задачи.
Маргинальная оценка остается постоянной только внутри некоторой окрестности существующего оптимума, соответствующей пределам, внутри которых текущий базис остается оптимальным как при увеличении так и при уменьшении объема ресурсов (объема закупок).
Маргинальные оценки действительны лишь при таком диапазоне изменения ресурсов Yi когда текущий базис остается оптимальным.
40. Признак неразреш-ти зад. в цел. числах
Если задача max(min)F=(1);(2);(3) явл-ся неразрешимой, то исходная задача max(min)F=(1); (2); (3); (4) тоже не имеет реш-ия.
8.Переход к канон. ф.:
Рассм. задачу:
Max(min)F= ∑Cj*xj (1)
∑ aijxj≤ bi, i=1,m1 (2)
∑ aijxj≥ bi, i=m1+1,m (3)
xj≥ 0, j=1,n (4)
Преобраз. к канонич. виду. Введём m дополнит. неотриц. перемен: xn+i ≥ 0, i=1,m. Чтобы нер-во (2) преобраз. в р-во, к лев. ч. прибавим дополнит. переменные xn+i ≥ 0, i=1,m1. Чтобы нер-во (3) преобраз. в р-во — вычтем доп. перемен. xn+i ≥ 0, i=m1+1,m. Нер-ва примут вид:
∑ aijxj + xn+i = bi, i=1,m1 (5)
∑ aijxj — xn+i = bi, i=m1+1,m (6)
Сист-у ур-ий (5)-(6) наз. Эквивалентной сист-е (2)-(3) с усл. Неотриц-сти дополнит. перем-ых. Они в Цф вводятся с коэф-тами= 0. В рез-те получим задачу в канонич. форме:
Max(min)F= ∑Cj*xj + ∑0*xn+I (7)
∑ aijxj + xn+i = bi, i=1,m1 (8)
∑ aijxj — xn+i = bi, i=m1+1,m (9)
xj≥ 0, j=1,n, xn+1≥ 0, i=1,m (10)
Теорема: Каждому допустим. реш-ию(x10, x20… xn0) задачи (1)-(4) соотв. Вполне определ. допуст-ое реш-е (x10, x20… xn0, xn+10… xn+m0) задачи (7)-(10) и наоборот, где, xn+i0 ≥0, i=1,m.
Т. к. дополнит. перем-е ввод-ся в ЦФ (7) с коэф-ами=0,то знач-я ЦФ (1)и (7) при соотв. допуст. реш-ях одинаковы. Следует, что данные ЦФ на мн-ве соотв. допуст. реш-й достиг. Экстрем. значи-я одновременно. Оптим. реш-ю (1)-(4) соотв. реш-е (7)-(10),т. е. исх. задачи и её канонич. ф. эквивалентны.
)
12. Геом интерпр-ия задачи ЛП с несколькими переменными.
Перейдем к геометрической интерпретации ЗЛП с несколькими переменными.
max F = , (1)
bi, (i=), (2)
xj0, (j=). (3)
Множ-во реш Х = (х1,х2,…,хn), компоненты кот удовл-ют огранич-ю — равенству ai1x1 + ai2x2 +… + ainxin = bi, (i=), геом-ски пред-ют собой гиперплоскость n-мерного пространства. Это выпуклое множ-во.
Множ-во реш Х = (х1,х2,…,хn), ком-ты кот удовл-ют нер-ву ai1x1 + ai2x2 +… + ainxinbi, (i=),образ полупрос-во n-мерного простр-ва, кот также явл выпуклым множ-вом.
Множ-во реш, удовл-их системе огранич задачи ЛП (2), (3) предст собой пересечение конечного числа полупространств и поэтому явл выпуклым. Теорема:Множ-во реш ЗЛП выпукло (если оно не пусто). Множ-во реш задачи ЛП в практически важных случаях чаще всего предст-ет собой либо выпуклый многогранник, либо выпуклую многогранную область. ЦФ (1) геом-ки можно рассм как семейство паралл гиперплоскостей с1×1 + с2×2 +… + сnxn =F, каждой из кот соот-ет опред знач параметра F. Вектор = (с1; с2; …;сn), перпенд-ый к гиперплоскости F=const, указ направл наискорейшего возраст функции F. С учетом сказ задача (1)-(3) геом-ки свод. к нахождению точки Х* = (х1*,х2*,…,хn*) многогранника, опред нерав-ми (2), (3), через кот проход гиперплоскость семейства (1), соот-щая наиб знач F. Граф методом можно решить ЗЛП с n>2 перем, если в ее канон-ой записи число неизв n и число линейно-независ векторов m связ соотнош-ем n-m2.