К канонической форме

Каноническая форма введена для обоснования метода поиска оптимального решения, но экономические задачи первоначально записываются в общей или симметричной форме. Покажем, что путем эквивалентных преобразований всегда можно перейти к канонической форме.

Преобразование целевой функции. Задачу поиска минимума легко заменить задачей поиска максимума. Если x * – точка минимума функции

, то для функции она будет точкой максимума.

Очевидно, что поиск максимума можно заменить поиском минимума и что эти утверждения справедливы и для функции n переменных:

.

0

Рис. 2.1

Замена неравенства типа «меньше или равно» на равенство. Для каждого ограничения типа введем свою дополнительную неотрицательную переменную . Если вектор x удовлетворяет исходному ограничению, то всегда можно подобрать ее значение так, чтобы выполнялось равенство

Если это равенство выполняется при некотором неотрицательном , то будет выполняться и рассматриваемое ограничение.

Ограничения типа «меньше или равно» были использованы при построении модели оптимального планирования производства. Заменяя их равенствами, получим:

Эти условия часто называют «ограничения-равенства», так как равенствами они являются только по форме, а по содержанию – ресурсными ограничениями. Каждое из них содержит свою дополнительную переменную , где (). Иногда такие переменные называют остаточными, поскольку их значения показывают величины неиспользованных ресурсов. Если продажа (сдача в аренду) свободных ресурсов не предполагается, то в целевую функцию модели дополнительные переменные войдут с нулевыми коэффициентами, иначе говоря, функционал не изменится.

Замена неравенства типа «больше или равно» на равенство выполняется аналогично. От левой части каждого ограничения типа отнимем дополнительную неотрицательную переменную , чтобы обеспечить выполнение равенства Если это равенство выполняется при некотором неотрицательном , то выполняется и исходное ограничение. Такие ограничения были использованы для построения модели формирования минимальной продовольственной корзины. После замены неравенства «больше или равно» равенством получим:

В этой модели содержательный смысл дополнительных переменных в том, что они показывают превышение содержания отдельных веществ в рационе сверх заданных минимальных величин. Поэтому их иногда называют избыточными. Очевидно, что в целевую функцию модели они войдут с нулевыми коэффициентами. При расчете подобной модели обеспечение норм по белкам и витаминам приведет, вероятно, к избыточной насыщенности.

Замена переменных любого знака на неотрицательные выполняется путем замещения их разностью неотрицательных переменных. Действительно, такую переменную можно представить как , где и неотрицательные переменные.

Итак, доказано, что от любой формы записи линейной модели можно перейти к канонической форме. Справедливо и обратное, равенство эквивалентно двум неравенствам с противоположными знаками: равносильно и .

Date: 2016-07-25; view: 372; Нарушение авторских прав