Теорема об оценках

т. е лин ф-я 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.