Математическое обеспечение оптимизационных моделей

Рассмотрим основные положения математического обеспечения оптимизационной модели на простейшей задаче математического программирования – задаче линейного программирования, особенность которой состоит в том, что целевая функция и функции ограничений имеют вид линейной функции.

Стандартная формулировка общей задачи линейного программирования выглядит так: требуется найти экстремальное значение показателя эффективности (целевой функции)

(3.1.7)

при линейных ограничительных условиях, накладываемых на элементы решения:

(3.1.8)

………………………………………

, (3.1.9)

где а_ij, b_i, c_j — заданные числа.

Вектор =(х₁, х₂, …, х_n) (набор управляющих переменных) называется допустимым решением, или планом задачи, если он удовлетворяет систе­ме ограничений (3.1.8) и (3.1.9). А допустимое решение =(х₁, х₂, …, х_n), кото­рое доставляет максимум или минимум целевой функции (3.1.7), называется оптимальным планом (оптималь­ным поведением, или просто решением) задачи линейного программирования. Оптимальное решение может быть не единственное. Возможны случаи, когда оно и не существует.

Геометрическая интерпретация и графический метод решения задачи линейной оптимизации. Чтобы понять сущность получения оптимального плана, рассмотрим графический метод решения задачи линейного программирования на примере модели с двумя переменными

f =С₁х₁ +С₂х₂ → max (3.1.10)

а₁₁х₁ + а₁₂х₂ ≤ b₁

а₂₁х₁ + а₂₂х₂ ≤ b₂ (3.1.11)

_{…………………………….}

а_m1х₁ + а_m2х₂ ≤ b_m

х₁ ≥ 0, х₂ ≥ 0 (3.1.12)

Геометрически задача линейной оптимизации (3.1.10)-(3.1.12) пред­ставляет собой поиск такой точки многогранника решений (3.1.11)-(3.1.12), координаты которой доставляют линейной функции (3.1.10) наи­большее (наименьшее) значение, причем допустимыми ре­шениями являются все точки многогранника решений.

Гра­фический метод решения состоит из следующих этапов.

Этап 1. Сначала на координатной плоскости Ох₁х₂ стро­ится допустимая многоугольная область (область допусти­мых решений, область определения), соответствующая огра­ничениям (3.1.10)-(3.1.12). На координатной плоскости Ох₁х₂ линейное уравнение вида а_ijх_j+а_ijх_j=b_i изображается прямой, а линейное неравенство а_ijх_j+а_ijх_j ≤ b_i или а_ijх_j+а_ijх_j ≥ b_i является полуплоскостью. Условия неотрицательности определяют полуплос­кости соответственно с граничными прямыми х₁=0 и х₂=0. Если система ограничений совместна, то полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая яв­ляется выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых составляют решение данной системы. Совокупность этих точек называют многоугольником решений. Это может быть точка, отрезок, луч, замкнутый многоугольник, неограниченная многоугольная область. Далее строится вектор-градиент линейной функ­ции = (С₁, С₂). Этот вектор показывает направление наискорейшего возрастания целевой функции. Начало вектора находится в точке с координатами (0; 0), а вершина― в точке с координатами (С₁, С₂). Для удобства можно строить век­тор, пропорциональный вектору . В какой-нибудь точке, принадлежащей допус­тимой области строится прямая семейства f =const, которая всегда будет проходить перпендикулярно вектору-градиенту.

Этап 2. Прямая f =const, перпендикулярная век­тору-градиенту, передвигается в направлении этого вектора в случае максимизации функции до тех пор, пока не покинет пределов многоугольной области. Предельная точка (или точки) области при этом движении и является точкой мак­симума целевой функции.

Этап 3. Для нахождения координат точки максимума достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f =B, найденное в получаемой точке, является максимальным. И затем останется выписать ответ, который будет иметь вид: ^* = (а₁, а₂), f_max = В.

В случае минимизации целевой функциипрямую f =const надо перемещать в направлении, противоположном вектору-гра­диенту (по направлению вектора-антиградиента). Ясно, что если прямая при своем движении не по­кидает допустимой области, то соответствующий максимум или минимум целевой функции не существует.

Пример 3.1.1. Фирма выпускает два вида древесно-стружечных плит ― обычные и улучшенные. При этом производятся две основные операции ― прессование и отделка. Требуется указать, какое количество плит каждого типа можно изготовить в течение месяца так, чтобы обеспечить максимальный доход при следующих ограничениях на ресурсы (материал, время, затраты):

Таблица

Исходные данные по имеющимся ресурсам (пример 3.1.1)

Если за каждые 100 обычных плит фирма получаем доход, равный 80 ден.ед., за каждые 100 плит улучшенного вида ― 100 ден.ед.

Решение.

Перейдем к построению математической модели поставленной задачи. Введем следующие обозначения. Пусть

х₁ ― количество партий в 100 плит обычного вида, изготавливаемых в течение месяца,

х₂ ― то же для плит улучшенного качества.

Тогда ожидаемый доход модно записать так:

f = 80 х₁ + 100 х₂ → max. (3.1.13)

Для изготовления х₁ партий в 100 плит обычного вида и х₂ партий в 100 плит улучшенного вида требуется 5 х₁ + 10 х₂ килограммов дерева. Ясно, что полученное число не может превосходить количество материала, имеющегося в наличии, т.е. 1000 кг. Тем самым, ограничение на материал имеет вид: 5 х₁ + 10 х₂ ≤ 1000.

Подобным же образом рассчитывается ограничения на время изготовления и затраты:

прессование: 4 х₁ +6 х₂ ≤ 900,

отделка: 4 х₁ +4 х₂ ≤ 600,

затраты: 30 х₁ +50 х₂ ≤ 6000.

Наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объемы выпуска плит: х₁ ≥ 0, х₂ ≥ 0.

Итак подведем итог: требуется найти такие значения х₁ и х₂, подчиненные условиям

5 х₁ + 10 х₂ ≤ 1000,

4 х₁ + 6 х₂ ≤ 900,

4 х₁ + 4 х₂ ≤ 600, (3.1.14)

30 х₁ +50 х₂ ≤ 6000,

х₁ ≥ 0,

х₂ ≥ 0,

для которых

f = 80 х₁ + 100 х₂ → max.

Итак, соотношения (3.1.13) – (3.1.14) и есть математическая модель задачи поставленной в данном примере.

Решим эту задачу графическим методом.

Ограничения х₁ ≥ 0, х₂ ≥ 0 означают, что область решений будет лежать в первой четверти декартовой системы координат. Отметим эту область на рис. 3.1.1.

Этап 1. Определим множество решений первого нера­венства. Оно состоит из решения уравнения 5 х₁ + 10 х₂ = 1000 и строгого не­равенства 5 х₁ +10 х₂ < 1000. Решением уравнения служат точки прямой 5 х₁ + 10 х₂ = 1000. Построим прямую по двум точкам (0; 100) и (200; 0), которые легко получить в результате последовательного обнуления одной из переменных: пусть х₁=0, тогда х₂= (1000 — 5*0)/10 = 100, пусть х₂=0, тогда х₁= (1000- 10*0)/5 = 200.

На рисунке обозначим эту прямую цифрой I. Множество решений строгого неравенства — одна из по­луплоскостей, на которую делит плоскость построенная пря­мая. Какая из них является искомой, можно выяснить при помощи одной контрольной точки. Если в произвольно взя­той точке, не принадлежащей прямой, неравенство выпол­няется, то оно выполняется и во всех точках той полуплос­кости, которой принадлежит контрольная точка, и не вы­полняется во всех точках другой полуплоскости. В качестве такой точки удобно брать начало координат. Подставим ко­ординаты (0; 0) в неравенство, получим 5*0+10*0 = 0 < 1000, т.е. оно вы­полняется. Следовательно, областью решения неравенства служит нижняя полуплоскость.

Аналогичным образом построим области решения трех других неравенств

4 х₁ +6 х₂ ≤ 900,

(0; 150) и (225; 0) на рисунке прямая II и берется нижняя полуплоскость;

4 х₁ +4 х₂ ≤ 600,

(0; 150) и (150; 0) на рисунке прямая III и берется нижняя полуплоскость;

30 х₁ +50 х₂ ≤ 6000,

(0; 120) и (200; 0) на рисунке прямая IV и опять берется нижняя полуплоскость.

Внутренняя часть и является общей областью для всех неравенств. Это и будет область допустимых решений рассмат­риваемой задачи в виде замкнутого четырехугольника.

Этап 2. Для определения направления движения к оп­тимуму построим вектор-градиент , координаты которого (80; 100). Чтобы построить этот вектор, нужно соединить точку (80; 100) с началом координат. При макси­мизации целевой функции необходимо двигаться в направ­лении вектора-градиента. Для удобства можно строить век­тор, пропорциональный вектору (grad). Приравняем целевую функцию постоянной ве­личине а: 80х₁+ 100х₂ = а. Пусть а=3200, вычис­лим координаты двух точек, удовлетворяющих соответст­вующему уравнению 80х₁ + 100х₂ = 3200. В качестве одной из этих точек удобно взять точку (40; 0), в качестве второй точки возьмем точку (0; 32). Через эти две точки проведем линию уровня (пунктирная прямая f(x) на рис. 3.1.1).

В нашем случае движение линии уровня будем осущест­влять до ее пересечения с крайней точкой (пунктирная прямая f(max)), далее она выходит из области допустимых решений. Следовательно, именно в этой точке достигается максимум целевой функции.

Этап 3. Найдем координаты этой точки, решив систему уравнений прямых пересечения в данной точке.

5 х₁ + 10 х₂ = 1000, х₁ = 100

4 х₁ +4 х₂ = 600, х₂ = 50

Вычислим значение целевой функции в данной точке, подставив найденные значения в выражение f = 80х₁ + 100х₂. Отсюда лег­ко записать решение исходной задачи линейной оптимизации:

х₁ = 100, х₂ = 50, f_max = 13000.

Ответ: ^* = (100; 50), f_max = 13000. Чтобы обеспечить максимально возможный доход равный 13000 ден.ед., фирме необходимо изготавливать в течение месяца 100 партий обычных плит и 50 партий плит улучшенного качества.

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

Рис 3.1.1. Графическое решение задачи.

Симплексный метод решения задачи линейной оптимизации. Трудность решения задачи линейного программирования заключается в том, что не все модели задач можно свести к равносильным моделям с двумя переменными, а с большим количеством ― практически невозможно решить.

Наиболее распространенным методом решения задач линейного программирования является так называемый симплекс-метод. Из геометрической интерпретации задача линейной оптимизации видно, что экстремум функции достигается в угловой точке выпуклого многогранника, т.е. в области допустимых решений. Поэтому в основу симплекс-метода положена идея рассмотрения только крайних точек (вершин) многогранника, а не все бесконечное множество его точек.

Симплексный метод это универсальный метод решения или метод последовательного улучшения планов. Суть этого метода заключается в том, что вначале получают допустимый вариант, удовлетво­ряющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение), оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций).

Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения метода Жордана-Гаусса для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная задача. Результат каждой итерации (включая данные задачи) удобно записывать в виде симплексной таблицы (вид которой представлен при решении задачи примера 3.1.2). Направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи.

Предположим, что в симплексной таблице содержится некоторый опорный план (см. пример 3.1.2). Через конечное число шагов либо будет найден оптимальный план задачи, либо будет установлено неразрешимость задачи. Перебор опорных планов осуществляется в процессе перехода от одного базиса системы переменных к другому базису. При этом приходится определять переменные, участвующие в преобразовании базиса. Переменная, включаемая в базис в задаче максимизации, определяется по отрицательному коэффициенту в строке целевой функции симплексной таблицы. Если таких коэффициентов несколько, то выбирают максимальный по модулю. Такую переменную называют разрешающей, а столбец коэффициентов при ней разрешающим. Для выбора переменной исключаемой из базиса составляют симплексные отношения: это отношение свободного коэффициента к элементу такого же знака разрешающего столбца. Наименьшее из них и указывает уравнение (разрешающее), в котором содержится исключаемая переменная. После выбора разрешающего столбца и разрешающей строки определяется на их пересечении разрешающий элемент и осуществляется преобразование модели задачи к новому базису.

Симплексное преобразование после выбора разрешающего элемента при табличных записях выполняется по следующим правилам:

1) Разрешающий элемент (a_rk) заменяют обратной величиной (т.е. 1/а_rk);

2) Остальные элементы разрешающей строки делятся на разрешающий элемент (а^'_rj = , j = );

3) Остальные элементы разрешающего столбца делятся на разрешающий элемент и знак меняется на противоположный (a^'_ik = — , i = );

4) Остальные элементы таблицы преобразовываются по правилу прямоугольника: искомый элемент равен разности произведений элементов главной и побочной диагоналей, деленной на разрешающий элемент (по воображаемому прямоугольнику пересчета) (a^'_ij = , i = , j = , i r, j k).

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

Признак оптимальности задачи максимизации: Если все оценки индексной строки не отрицательны, то соответствующий план является оптимальным в задаче максимизации.

Признак оптимальности задачи минимизации: Если все оценки индексной строки не положительны, то соответствующий план является оптимальным в задаче минимизации.

В тех случаях, когда затруднительно найти первоначальный опорный план канонической формы задачи линейного программирования применяется метод искусственного базиса (М – метод).

Решим симплексным методом следующую задачу.

Пример 3.1.2. Предприятие выпускает четыре вида продукции П₁, П₂, П₃ и П₄. Для производства продукции оно располагает тремя ресурсами, запасы которых ограничены величинами 35, 30 и 40 единиц. Цена единицы готовой продукции соответственно равна 14, 10, 14 и 11 ден.ед. Удельные затраты на единицу продукции и цена единицы готовой продукции заданы в виде таблицы:

Таблица

Удельные затраты на единицу продукции (пример 3.1.2)

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

Решение: Составим математическую модель задачи. Пусть х₁, х₂, х₃ и х₄ ― искомые объемы производства продукции, а через f ― доход предприятия от производства и реализации всей продукции, который с учетом введенных обозначений определяется следующей функцией:

f = 14х₁+ 10х₂+ 14х₃+ 11х₄ → max. (3.1.15)

Ограничения по используемым ресурсам примут вид:

4х₁+ 2х₂+ 2х₃+ 3х₄ ≤ 35,

х₁+ х₂ + 2х₃+ 3х₄ ≤ 30, (3.1.16)

3х₁+ х₂+ 2х₃+ х₄ ≤ 40.

По смыслу задачи объемы производства продукции не могут быть отрицательными, поэтому

х_j ≥ 0, (j= . (3.1.17)

Введем в рассмотрение возможные остатки ресурсов: х₅, х₆, х₇, или приведем модель задачи к каноническому виду и получим:

f = 14х₁+ 10х₂+ 14х₃+ 11х₄ → max

4х₁+ 2х₂+ 2х₃+ 3х₄ + х₅ = 35,

х₁+ х₂ + 2х₃+ 3х₄ + х₆ =30, (3.1.18)

3х₁+ х₂+ 2х₃+ х₄ + х₇ = 40.

х_j ≥ 0, (j=

Нам необходимо выделить начальный базис системы, т.е. выделить базисные переменные. Базисных переменных должно быть столько, сколько ограничений системы линейных уравнений, т.е. в нашем случае их должно быть три. Наши дополнительные переменные х₅, х₆, х₇ и будут базисными, так как им соответствуют единичные векторы, которые образуют базис в трехмерном пространстве. Выразим эти переменные и получим:

х₅ = 35 — (4х₁+ 2х₂+ 2х₃+ 3х₄),

х₆ = 30 — (х₁+ х₂ + 2х₃+ 3х₄), (3.1.19)

х₇ = 40 – (3х₁+ х₂+ 2х₃+ х₄).

Итак у нас х₅, х₆, х₇ базисные переменные, а х₁, х₂, х₃ и х₄ будут свободными переменными. Приравнивая свободные переменные нулю мы получим х₅ =35, х₆ =30, х₇ =40. Имеем некоторый допустимый план задачи = (0; 0; 0; 0; 35; 30; 40). Этот план удовлетворяет одновременно всем ограничениям задачи и следовательно является опорным планом. Занесем условия задачи в симплексную таблицу. Первый столбец ─ столбец базисных переменных (БП ─ х₅, х₆, х₇); второй столбец ─ столбец свободных коэффициентов (1); далее идут столбцы свободных переменных (СП) ─ таких переменных в нашей задаче четыре (х₁, х₂, х₃ и х₄), они всегда записываются в (СП) со знаком " -". Чтобы правильно вписать коэффициенты в данную таблицу, надо придерживаться следующего правила: в соответствующей строке записываем числа так, чтобы при умножении их на соответствующее значение в " шапочке" таблицы мы получили бы выражения вида (3.1.19) и (3.1.15).

Таблица 3.1

БП		СП
- х1	- х2	- х3	- х4
х5 =					3
х6 =
х7 =
f =		-14	-10	-14	-11

При решении задачи максимизации в строке целевой функции в столбцах свободных переменных не должно быть отрицательных коэффициентов. Мы видим, что в нашем случае, в столбцах свободных переменных в индексной строке присутствуют отрицательные коэффициенты, поэтому данный опорный план не является оптимальным. Будем улучшать его, переходя от одного базиса системы к другому. Выберем разрешающий столбец, как столбец, соответствующий наибольшей по модулю отрицательной оценке, т.е. max {│ -14│; │ -10│; │ -14│; │ -11│ } = 14.

Из двух одинаковых оценок выберем одну, например, столбец соответствующий свободной переменной х₁, он и будет разрешающим столбцом. Затем находим разрешающую строку по наименьшему симплексному отношению: min { } = .

На пересечении разрешающего столбца и разрешающей строки находим разрешающий элемент, выделяем его (мы выделили ячейку, в которой находится разрешающий элемент, равный 4). Строим следующую симплексную таблицу, меняя две переменные х₁ и х₅ местами и пересчитываем элементы по правилам симплексных преобразований.

Таблица 3.2

БП		СП	min
- х5	- х2	- х3	- х4
х1	35/4	1/4	2/4	2/4	3/4	35*4/4*2=35/2
х6	85/4	-1/4	2/4	6/4	9/4	85*4/4*6=85/6
х7	55/4	-3/4	-2/4	2/4	-5/4	55*4/4*2=55/2
f	490/4	14/4	-12/4	-28/4	-2/4

Анализируя полученные результаты, мы видим, что пока ещё не получен оптимальный план, так как не все оценки строки целевой функции принимают неотрицательные значения. Повторим наши преобразования, выбрав разрешающий элемент, равный 6/4. В результате получим следующую таблицу.

Таблица 3.3

БП		СП	min
- х5	- х2	- х6	- х4
х1	10/6	2/6	2/6	-2/6		(10/6)/(2/6)=10/2
х3	85/6	-1/6	2/6	4/6	9/6	(85/6)/(2/6)=85/2
х7	40/6	-4/6	-4/6	-2/6	-12/6	─
f	1330/6	14/6	-4/6	28/6	60/6

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

Таблица 3.4

Итак, в индексной строке последней таблицы нет ни одного отрицательного элемента, следовательно, содержащийся в ней план является оптимальным. Выпишем его, зная, что значения базисных переменных находится в столбце свободных коэффициентов, а все свободные переменные равны нулю. ^*=(0; 5; 12, 5; 0; 0; 0; 10). Значение целевой функции f_max равно 225. Но наша задача с экономическим содержанием, поэтому проанализируем данные результаты и запишем ответ.

Ответ: Предприятию по оптимальному плану следует производить 5 единиц продукции вида П_2, 12, 5 единиц продукции вида П₃, продукции П₁ и П₄ выпускать не следует, при этом ресурсы Р₁ и Р₂ будут израсходованы полностью, а ресурс Р₃ останется в количестве 10 единиц. Выручка предприятия при этом составит 225 ден.ед.

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

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

С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной.

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

Решение: Обозначим эти оценки за единицу каждого вида ресурса соответствен­но через у₁; у₂ и у₃ (Р₁, Р₂, Р₃). Эти оценки для упрощения иногда называют внутренними ценами на ресурсы в условиях данного производства (теневыми ценами). Т.е. они представляют объективно необходимые затраты на производство продукции в данных условиях.

Понятно, что при их определении следует руководствоваться следующими соображениями:

1. Оценка ресурсов, затрачиваемых на выпуск единицы готовой продукции должна быть не меньше оценки единицы готовой продукции, т.е.

П₁: 4у₁ + у₂ + 3у₃ ≥ 14

П₂: 2у₁ + у₂ + у₃ ≥ 10 (3.1.20)

П₃: 2у₁ + 2у₂ + 2у₃ ≥ 14

П₁: 3у₁ + 3у₂ + у₃ ≥ 11

2. Оценки по их смыслу должны выражаться не отрицательными чис­лами, т.е.

у_i ≥ 0, i = (3.1.21)

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

φ = 35 у₁ + 30 у₂ + 40 у₃ → min (3.1.22)

Итак, получили модель задачи:

φ = 35 у₁ + 30 у₂ + 40 у₃ → min

4у₁ + у₂ + 3у₃ ≥ 14

2у₁ + у₂ + у₃ ≥ 10 (3.1.23)

2у₁ + 2у₂ + 2у₃ ≥ 14

3у₁ + 3у₂ + у₃ ≥ 11

у_i ≥ 0, i = .

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

Используя данное соответствие из таблицы 3.6. находим значения двойственных переменных:

у₁ ~ х₅ → у = 3; у₂ ~ х₆ → у = 4; у₃ ~ х₇ → у = 0;

у₄ ~ х₁ → у = 2; у₅ ~ х₂ → у = 0; у₆ ~ х₃ → у = 0;

у₇ ~ х₄ → у = 10.

Таким образом, можно записать оптимальный план двойственной задачи: = (3; 4; 0; 2; 0; 0; 10), φ _min = 225.

Задача (3.1.20) — (3.1.22) называется двойственной к задаче (3.1.15) — (3.1.17). Эти две задачи представляют собой числовой пример пары симметричных двойственных за­дач. Система двойственных оценок (у_i) тесно связана с конкретными условиями данного производства. С изменением этих условий меняется и система этих оценок.

В общем виде модели двойственных задач имеют сле­дующий вид:

Прямая или исходная	Двойственная
f = → max (I)	φ = → min (I`)

Любую задачу внутри двойственной пары можно назвать прямой или исход­ной, тогда другая будет двойственной к ней.

Анализируя модели задач двойственной пары, можно сделать следую­щие выводы о связях, существующих между элементами модели задач двой­ственной пары:

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

2. Матрицы коэффициентов при переменных в двойственных задачах взаимно транспортированы.

3. Каждому ограничению ─ неравенству в двойственной задаче отвеча­ет неотрицательная переменная, а каждому ограничению равенству ─ пере­менная произвольного знака и наоборот: каждой неотрицательной перемен­ной ─ ограничение неравенство, а каждой переменной произвольного знака ─ ограничение равенство. При этом в задаче максимизации ограничения-неравенства имеют смысл«≤», ав задаче минимизации ─ «≥».

4. Если в прямой задаче функция целевая максимизируется, то в двойственной минимизируется и наоборот.

Основные утверждения о взаимодвойственных задачах содержатся в следующих теоремах, называемых теоремами двойственности.

Теорема 1 (основная).

Теорема 2 (о дополняющей нежесткости).

Для того, чтобы планы * и * пары двойственных задач были оптимальными, необходимо и достаточно выполнение условия: х () = 0, (j = ) (3.1.24) у () = 0, (i = ) (3.1.25)

Теорема 3 (об оценках).

Компоненты оптимального плана двойственной задачи численно равны частным производным от экстремального значения целевой функции по свободным членам ограничении задачи: у = (i= ) (3.1.26)

В пределах устойчивости двойственных оценок имеют место следующие свойства.

1. Двойственные оценки у_i (i = ), — являются инструментом балансирования затрат и результатов.

С экономической точки зрения теорема 1 означает, что по оптимальному плану выпуска продукции все затраты внутри производства совпадают с оценкой готовой продукции, произведенной по этому плану, т.е. при оптимальном плане вся стоимость затрат внутри производства поглощается в стоимости готовой продукции. Т.е. затраты равны 35*3+30*4+40*0=225. Стоимость готовой продукции 14*0+10*5+14*12, 5+11*0=225.

2. Величина двойственной оценки того или иного ресурса показывает насколько возросло бы максимальное значение целевой функции, если бы объём данного ресурса увеличился бы на одну единицу (двойственные оценки измеряют эффективность малых приращений объёмов ресурсов в конкретных условиях данной задачи).

В примере 3.1.2 увеличение ресурса Р₁ на 1 единицу привело бы к росту максимальной суммы прибыли на 3 ден.ед. (y₁ =3), а увеличение ресурса Р₃ не повлияет на оптимальный план выпуска продукции и сумму прибыли.

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

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

В примере 3.1.2 недефицитным ресурсом является ресурс Р₃ поскольку y₃ = 0.

Острее ощущается дефицитность ресурса Р₂ (y₂ = 4) − он более дефицитен, чем ресурс Р₁ (y₁ = 3).

4. Двойственные оценки позволяют определять своеобразные ''нормы заменяемости ресурсов'': имеется в виду не абсолютная заменяемость ресурсов, а относительная, т.е. заменяемость с точки зрения конечного эффекта и лишь в конкретных условиях данной задачи.

Пример 3.1.4. Предположим, что из производства исключается 2 единицы дефицитного ресурса Р₂. Понятно, что выручка снизится. Какое ко­личество взаимозаменяемого ресурса Р₁ следует ввести в производство с тем, чтобы возместить уменьшение выручки.

Решение: Выручка (по третьей теореме двойственности) уменьшится на 2*у =2*4=8 ден.ед. Эту же величину необходимо возместить за счет введения первого ресурса, т.е. 8=Δ b₁*у . Отсюда легко находим значение Δ b₁. Получаем Δ b₁=8/3. 8/3 единиц первого ресурса заменят недостаток второго.

5. Двойственные оценки служат инструментом определения эффективности отдельных хозяйственных решений (технических способов), с их помощью можно определять выгодность новых изделий, эффективность новых технологических способов: если Δ _j = a _ij y_i^* – c_j ≤ 0 − выгодно, если Δ _j > 0 ─ невыгодно.

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

Пример 3.1.5. Проверить целесообразность выпуска продукции П₅, если удельные затраты ресурсов составляют соответственно 5; 4; 6 условных единиц. Стоимость единицы продукции составляет а) 25 ден.ед.; б) 33 ден.ед.

Решение. Найдем затраты на производство единицы продукции П₅ 5у +4у +6у = 5*3+4*4+6*0 = 31 ден.ед. Сравним со стоимостью готовой продукции:

а) 31 > 25 или Δ ₅ =31-25=6. Следовательно производство продукта П₅ по цене 25 ден.ед. не целесообразно.

б) 31 < 33 или Δ ₅ =31-33=-2. Следовательно производство продукта П₅ по цене 33 ден.ед. целесообразно.