Описание решения оптимизационных задач линейных моделей с помощью табличного процессора еxcel

Описание решения оптимизационных задач линейных моделей  с помощью табличного процессора Excel

Пример 11. Рассмотрим разобранную выше задачу №4:

Для изготовления четырех видов продукции (П₁, П₂, П₃, П₄) предприятие использует три типа ресурсов Р₁, Р₂, Р₃. Размеры допустимых затрат ресурсов ограничены соответственно величинами 180, 210, 800. Нормы расхода ресурсов каждого типа на единицу продукции, их наличие в распоряжении предприятия, а также цена единицы продукции приведены в таб. 25.

 Определить,  сколько продукции каждого вида следует производить, если цель предприятия состоит в максимизации прибыли (сбыт продукции обеспечен).

                                                                                 Таблица 25

Решение. Пусть x₁, x₂, x₃, x₄ – число единиц продукции соответствующего вида П₁, П₂, П₃, П₄, запланированных к производству. Поскольку имеются ограничения на размеры допустимых затрат ресурсов, то переменные x₁, x₂, x₃, x₄ должны удовлетворять системе неравенств:

                        (1)

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

                         x₁, x₂, x₃, x₄ ³ 0                     (2)

Суммарная прибыль от реализации продукции составит:

         F = 9 x₁ + 6 x₂ + 4 x₃  + 7 x₄                       (3)

Итак, требуется найти такой план выпуска продукции X = (x₁, x₂, x₃, x₄), удовлетворяющий системе (1) и условию (2), при котором функция (3) принимает максимальное значение.

Экономико-математическая модель задачи описывается средствами табличного процессора Excel как совокупность формул, сведенных в таблицу и зависящих от изменяемых параметров – исходных данных.

Для решения нашей задачи создадим в Excel «книгу» с именем «Оптимизация доходов предприятия». Данные занесем на лист, который назовем «План выпуска продукции», как показано на рис. 9.

Рис. 9 Лист Excel с данными задачи

В ячейках B10, C10, D10 и E10 занесены предварительные значения переменных, которые будут варьироваться в процессе решения. Здесь они заданы равными единице, поскольку при решении линейных задач от начальных значений переменных не зависят ни конечные значения, ни время поиска решения.

В восьмой строке занесены коэффициенты целевой функции.

В ячейке F12 занесена формула для прибыли от реализации продукции.

В ячейках F16, F17, F18 занесены формулы для расхода ресурсов.

В Excel поиск значений переменных, при которых достигается экстремум целевой функции, осуществляется через пункт меню «Сервис », подпункт «Поиск решения » (в англоязычном варианте  – «Solver »).

Раскройте пункт меню «Сервис », выберите команду «Поиск решения ». Если в меню «Сервис» отсутствует команда «Поиск решения », выберите команду «Сервис – Надстройки » и активизируйте надстройку «Поиск решения ».

"Поиск решения" вызывает диалоговое окно, представленное на рис. 10.

Рис. 10 Диалоговое окно «Поиск решения»

Ниже перечислены основные поля и органы управления диалогового окна «Поиск решения» и их назначение.

· Поле «Установить целевую ячейку» служит для указания ячейки, содержащей целевую функцию, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. (Эта ячейка должна содержать формулу).

· Переключатель «Равной» служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного значения). Чтобы установить заданное значение, введите его в поле, расположенное справа от слова «Значение».

· Поле «Изменяя ячейки» служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле «Установить целевую ячейку».

· Кнопка «Предположить» используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле «Установить целевую ячейку». Результат поиска отображается в поле «Изменяя ячейки».

· Список «Ограничения» служит для отображения списка граничных условий поставленной задачи.

· Кнопка «Добавить» служит для отображения диалогового окна «Добавить ограничение», с помощью которого записываются выражения, определяющие ограничения.

· Кнопка «Изменить» служит для отображения диалогового окна «Изменить ограничение», которое позволяет редактировать выбранное выражение из списка ограничений.

· Кнопка «Удалить» служит для снятия выбранного ограничения.

· Кнопка «Выполнить» служит для запуска поиска решения поставленной задачи.

· Кнопка «Закрыть» служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки «Параметры», «Добавить», «Изменить» или «Удалить».

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

· Кнопка «Восстановить» служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используемых по умолчанию.

Описание ограничений, присущих оптимизационной задаче, выполняется с помощью двух однотипных диалоговых окон «Добавление ограничения » и «Изменение ограничения », одно из которых представлено на рис. 11.

Рис. 1 Диалоговое окно «Добавление ограничения»

Ниже перечислены основные поля и органы управления названных диалоговых окон.

· Поле «Ссылка на ячейку» служит для указания ячейки или диапазона, на значения которых необходимо наложить ограничение.

· Раскрывающийся список предназначен для выбора условия (<=,  >=,  =) определяющего ограничение.

· Поле «Ограничение» служит для задания числа, формулы, ссылки на ячейку или диапазон, определяющие ограничение.

· Кнопка «Добавить »  используется для того, чтобы, не возвращаясь в окно диалога «Параметры поиска решения», наложить новое условие на поиск решения задачи.

Управление алгоритмом поиска и определение его параметров (скорости сходимости, точности и т.п.) выполняется с помощью диалогового окна «Параметры поиска решения », представленного на рис. 12.

Рис. 12 Диалоговое окно «Параметры поиска решения»

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

Ниже описаны значения полей, переключателей и флагов этого диалогового окна:

· Поле «Максимальное время » служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах), не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.

· Поле «Предельное число итераций » служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.

· Поле «Относительная погрешность » служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Относительная погрешность по умолчанию  0,000001.

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

· Поле «Сходимость ». Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле «Сходимость», поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0  до 1.

· Флаг «Линейная модель » служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи.

· Флаг «Показывать результаты итераций »  служит для приостановки поиска решения для просмотра результатов отдельных итераций.

· Флаг «Автоматическое масштабирование » служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине, например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.

· Флаг «Значения не отрицательны » позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле "Ограничение" диалогового окна «Добавить ограничение».

· Переключатель «Оценки »  служит для указания метода экстраполяции (линейная или квадратичная), используемого для получения исходных оценок значений переменных в каждом одномерном поиске.

· Значение переключателя «Линейная» служит для использования линейной экстраполяции вдоль касательного вектора.

· Значение переключателя «Квадратичная» служит для использования квадратичной экстраполяции, которая дает лучшие результаты при решении нелинейных задач и не играет роли для линейных задач.

· Переключатель «Производные» служит для указания метода численного дифференцирования и для линейных задач его значение не играет роли.

· Переключатель «Метод поиска» служит для выбора алгоритма оптимизации (метод Ньютона или метод сопряженных градиентов) для указания направления поиска. Для решения задач линейного программирования его значения несущественны.

· Кнопка «Загрузить модель» служит для отображения на экране диалогового окна «Загрузить модель», в котором можно задать ссылку на область ячеек, содержащих загружаемую модель.

· Кнопка «Сохранить модель» служит для отображения на экране диалогового окна «Сохранить модель», в котором можно задать ссылку на область ячеек, предназначенную для хранения модели оптимизации. Данный вариант предусмотрен для хранения на листе более одной модели оптимизации, первая модель сохраняется автоматически.

В результате заполнения всех полей и внесения всех ограничений, диалоговое окно «Поиск решения» для нашей задачи примет вид рис. 13.

После нажатия на кнопку «Выполнить» появляется окно «Результаты поиска решения» , в котором предлагается выбрать тип отчета: результаты, устойчивость, пределы, либо любую их комбинацию. Переключатель «Сохранить найденное решение», либо «Восстановить исходные значения». Кнопки «ОК», «Отмена», «Сохранить сценарий» и «Справка».

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

Рис. 13  Результат  заполнения полей диалогового окна «Поиск решения»

Ниже приведено описание листов отчетов для нашей задачи и экономическая интерпретация результатов решения.

1. «Отчет по результатам» (рис. 14) состоит из трех таблиц:

· в таблице «Целевая ячейка (Максимум)» приведены адрес, исходное и результатное значение целевой функции;

· в таблице «Изменяемые ячейки» находятся адреса, идентификаторы (имена) и значения всех искомых переменных задачи;

·  в таблице «Ограничения» показаны результаты оптимального решения для ограничений задачи. В графе «Формула» указаны зависимости, которые были введены в диалоговом окне «Поиск решения».

Рис. 14 Лист отчета по результатам

В результате 4-х итераций получен оптимальный план производства
X*=(95; 210; 0; 0), максимальное значение целевой функции (прибыль от реализации продукции) составляет 2115 денежных единиц.

· В таблице «Ограничения» этого листа приводятся значения левых частей каждого ограничения задачи ЛП; разница между значениями правых и левых частей по каждому ограничению.

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

 В нашей задаче ресурсы второго и третьего типов (Р₂ и Р₃) использованы полностью, а соответствующие им ограничения системы (1) обратились в точные равенства при подстановке оптимального плана в систему ограничений экономико-математической модели задачи. (Эти ограничения имеют статус «связанное»).

Ресурс 1-го типа (Р₁) используется в оптимальном плане в объеме 95 единиц, а значит, остается в избытке в объеме, равном 85 единиц. И соответствующее ограничение системы (1) имеет вид строгого неравенства при подстановке оптимального решения. Это ограничение имеет статус «несвязанное».

2. «Отчет по устойчивости» (рис. 15) содержит информацию  о том, насколько целевая ячейка чувствительно к изменениям ограничений и переменных. Этот отчет имеет две таблицы: одна для изменяемых ячеек, вторая для ограничений.

Рис. 15 Лист отчета по устойчивости

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

Графа «Целевой коэффициент» показывает степень зависимости между изменяемой и целевой ячейками, то есть коэффициенты целевой функции.

Графы «Допустимое увеличение» – «Допустимое уменьшение» показывают предельные значения приращения коэффициентов в целевой функции, при которых сохраняется оптимальное решение.

· В таблице «Ограничения» , в графе «Теневая цена» приведены двойственные оценки, которые показывают, как изменится максимальное значение целевой функция при изменении запаса ресурса на единицу.

В графах «Допустимое увеличение» – «Допустимое уменьшение», показаны предельные значения изменения запаса каждого ресурса, при которых сохраняется набор переменных, входящих в оптимальное решение.

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

Ø проводить анализ чувствительности коэффициентов целевой функции к изменению исходных данных;

Ø определить степень дефицитности ресурсов;

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

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

По оптимальному плану в рассмотренной задаче следует производить продукцию первого и второго видов и превышение затрат над ценой реализации равно нулю. Например, для продукции первого вида затраты на ресурсы составляют 1×y₁ + 0×y₂ + 4×y₃ = 1×0 + 0×1,5 + 4×2,25 = 9 и цена реализации равна 9.

А для продукции, например, третьего вида затраты на ресурсы составляют 2×y₁ + 3×y₂ + 0×y₃ = 2×0 + 3×1,5 + 0×2,25 = 4,5. Цена реализации этой продукции равна 4, и соответствующая нормированная стоимость равна 0,5. Если включить в план производства единицу продукции третьего вида, то целевая функция уменьшится на 0,5 денежных единиц, поэтому в таблице нормированная стоимость указана со знаком минус.

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

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

 можно увеличить, либо уменьшить этот коэффициент с сохранением оптимального плана.

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

· В таблице «Ограничения» для каждого вида ресурса указано, какое количество его используется в оптимальном плане (графа «Результ. значение»), а в графе «Теневая цена» приведены двойственные оценки ресурсов. В литературе эти оценки называют «скрытыми доходами», «маргинальными оценками», «разрешающими множителями» или «объективно обусловленными оценками» (по Л. В. Канторовичу). Эти оценки показывают, насколько денежных единиц изменится максимальная прибыль от реализации продукции при изменении запаса соответствующего ресурса на одну единицу.

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

В этой же таблице указано для каждого вида ресурса его исходное значение (графа «Ограничение Правая часть»), а также, на какое предельное значение можно увеличить или уменьшить запас каждого ресурса, с сохранением структуры оптимального плана. Например: при увеличении запаса второго ресурса Р₂ на величину 190 либо уменьшении на 170 единиц, набор производимой продукции (базисных переменных) останется неизменным.

Рис.16 Лист отчета по устойчивости с измененными ресурсами

Проверим данное утверждение, изменив величину запаса второго ресурса с 210 единиц до 390. Рис. 16 показывает, что при этом производимая продукция осталась той же, нормированные стоимости и теневые цены не изменились. Допустимое увеличение запасов второго ресурса сократилось до 10, то есть максимальное его значение по-прежнему 400.

3. «Отчет по пределам»   (рис. 17). В лист “Отчета по пределам” кроме экстремального значения целевой функции для оптимального плана в графах «Нижний предел» и «Верхний предел» приведены возможные предельные значения переменных, а также соответствующие значения целевой функции.

Рис. 17 Лист отчета по пределам

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

В заключение приведем высказывание Эмерсона: «Приступайте к делу и силы появятся».

Желаем успеха!

Задача о составлении оптимального рациона питания

Пусть имеется m видов необходимых человеку витаминов S₁, S₂, …, S_m, содержащихся в n видах различных продуктов P₁, P₂, …, P_n. 

Известны следующие исходные данные:

a_ij – содержание i-го витамина S_i в j-ом продукте P_j;

c_j - стоимость единицы продукта P_j;

b_i -  минимальная суточная потребность в i-м витамине.

Требуется составить оптимальный рацион питания из продуктов P₁, P₂, …, P_n с учетом суточной потребности в витаминах S₁, S₂, …, S_m, при котором затраты на продукты будут минимальными. Построим математическую модель этой задачи.

Обозначим за x_j (j = 1,2,...,n) – количество каждого вида продукта в суточном рационе. Тогда затраты на продукты составят c_j∙x_j, а суммарные затраты на суточный рацион составят:

F = c₁ x₁ + c₂ x₂ + ...+ c_n x_n.

Естественно, хотелось бы понести минимальные затраты. Следовательно, они подлежат минимизации.

Общее количество витамина S_i в потребленных продуктах Х = (x₁, x₂ ,..., x_n ) будет выражаться суммой произведений содержания витамина a_ij на количество потребленного продукта и составит величину, равную a_i1 x₁ + a_i2 x₂ + ... + a_in x_n . Поскольку суточная потребность в витамине S_i равна b_i , а суточное потребление не должно быть меньше его необходимого количества, то приходим к ограничениям следующего вида:

a_i1x₁ + a_i2x₂ +… + a_inx_n  b_i,     i = 1,2,...,m

Учитывая естественные условия неотрицательности потребления продуктов,

x_j0, j=1,2,...,n,

придем к следующей задаче:

Найти такой план Х = (x₁, x₂ ,..., x_n) питания, удовлетворяющий системе неравенств

                                          a₁₁x₁ + a₁₂x₂ + … + a_1nx_n    b₁,

                                          a₂₁x₁ + a₂₂x₂ + … + a_2nx_n   b₂,

                                           …   …   …   …   …   …   …

                                          a_i1x₁ + a_i2x₂ + … + a_inx_n    b_i,

                                          …   …   …   …   …   …   …

                                          a_m1x₁ + a_m2x₂ + … + a_mnx_n   b_m,

                                               x_j ³ 0,   j = 1, 2, …, n,

при котором функция  F = c₁x₁ + c₂x₂ + … + c_nx_n  принимает минимальное значение.

В десяти видах продуктов (P₁, P₂, Р₃, Р₄, Р₅, Р₆, Р₇, Р₈, Р₉, Р₁₀) содержатся 5 видов витаминов (S₁, S₂, S₃, S₄, S₅). Минимальная суточная потребность человека в этих витаминах равна соответственно b₁, b₂, b₃, b₄, b₅ мг. Содержание витамина i-го вида (i = 1, 2, 3, 4, 5) в продукте j-ого вида (j = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10) составляет a_ij мг в 100 г продукта. Цена 100 г продукта равна c_j рублей.

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

Решение. Составим экономико-математическую модель задачи. Обозначим  x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀ – количество продуктов соответствующего вида, входящих в рацион питания. Поскольку суточное потребление витаминов не должно быть меньше минимальной суточной потребности человека, то переменные x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀ должны удовлетворять системе неравенств:

                                                                               (1)

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

                                               x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀ ³ 0.                         (2)

Суммарные затраты на продукты составят составит:

 F = 2 x₁ + 8 x₂ + 17 x₃ + 2,1 x₄ + 1,8 x₅ + 3,5 x₆ + 5 x₇ + 6 x₈ + 4,5 x₉ + 4,5 x₁₀.        (3)

Итак, требуется найти такой план рациона питания X = (x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀), удовлетворяющий системе (1) и условию (2), при котором функция (3) принимает минимальное значение.

Формулировка двойственной задачи

Предположим, что некоторая организация решила закупить ресурсы Р₁ , Р₂ ,…, Р_m фирмы и необходимо определить цены на эти ресурсы у₁, у₂,…, у_m. Естественно, что покупающая организация заинтересована в том, чтобы затраты на покупку ресурсов в объеме b₁, b₂,…, b_m по ценам у₁, у₂,…, у_m  были минимальны, то есть Z = b₁y₁ + b₂y₂ + … +b_my_m  ®  min.

Предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не меньше той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции j-го вида расходуется сырье Р₁ в объеме а_1j, сырье Р₂ в объеме а_2j…, сырье Р_m в объеме  а_mj по цене у₁, у₂,…, у_m  соответственно, то есть затраты на изготовление продукции П_j должны быть не меньше, чем цена ее реализации. Приходим к ограничениям следующего вида:

а_1jу₁ + а_2jу₂  + … + а_mjу_m ≥ с_j ,     j=1,2,...,n.

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

Найти такой вектор У = (у₁, у₂ ,..., у_m) – цен ресурсов, удовлетворяющий системе неравенств

                                          a₁₁у₁ + a₂₁у₂ + … + a_m1у_m ≥  c₁,

                                          a₁₂y₁ + a₂₂y₂ + … + a_m2y_m  ≥  c₂,

                                           …   …   …   …   …   …   …

                                          a_1jy₁ + a_2jy₂ + … + a_mjy_m ≥   c_j,

                                          …   …   …   …   …   …   …

                                          a_1ny₁ + a_2ny₂ + … + a_mny_m ≥  c_n,

                                               y_i ³ 0,   i = 1, 2, …, m,

при котором функция Z = b₁y₁ + b₂y₂ + …+ b_my_m  принимает минимальное значение.

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

Сопоставим общие представления прямой и двойственной задач в табл. 3, причем прямая задача – это задача модели распределения ограниченных ресурсов.

                                                                                     Таблица 3

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

1. Если первая задача имеет размеры  (m–ограничений с n неизвестными), то вторая – размеры .

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

З. В правых частях ограничений в каждой     задаче стоят коэффициенты при неизвестных в целевой функции другой задачи.

4. В прямой задаче  все ограничения представляют собой неравенства типа « », причем в этой задаче требуется достичь . Напротив, в двойственной задаче все ограничения суть неравенства типа « », причем требуется достичь .

Графически эти правила представлены в таблице 4.

                                                                                                                 Таблица 4

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

Из приведенных соотношений видно, что для всех допустимых решений прямой и двойственной задач значения целевой функции задачи минимизации всегда будет верхним пределом значения целевой функции задачи максимизации. Таким образом, итерационное решение задачи максимизации ведет к возрастанию значения целевой функции, а итерационное решение задач минимизации – к ее убыванию. В итоге, при успешном завершении процессов вычисления прямой и двойственной задач приходят к точке «равновесия», где значения целевых функций задач максимизации и минимизации становятся равными.

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

Теорема равновесия. Пусть Х^* – какое-нибудь допустимое решение прямой задачи, а Y^* – какое-нибудь допустимое решение двойственной задачи. Для одновременной оптимальности этих решений необходимо и достаточно выполнение равенств:

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

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

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

Если Вам понравилась эта лекция, то понравится и эта - Италия после Первой Мировой Войны.

  Если     a_i1 x₁^* + a_i2 x₂^*+ ... + a_in x_n^* < b_i , то y_i^* = 0 .

Если     a_1j y₁^* + a_2j y₂^*+  … + a_mj y_m^* > c_j , то x_j^* = 0 .

Если какая-либо координата оптимального плана одной задачи положительна, то соответствующее ограничение другой задачи обращается в равенство:

Если y_i^* > 0 , то a_i1 x₁^* + a_i2 x₂^*+  ... + a_in x_n^* = b_i .                        

Если x_j^* > 0 , то a_1j y₁^* + a_2j y₂^*+   … + a_mj y_m^* = c_j .                       

Экономическое содержание теоремы равновесия означает, что если по некоторому оптимальному плану Х^*  производства расход i-го ресурса строго меньше его запаса bi, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равно нулю. Если же в некотором оптимальном плане оценок его i-ая координата строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует, что двойственные оценки служат мерой дефицитности ресурсов. Дефицитный ресурс, который полностью используется по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, не используемый полностью, имеет нулевую оценку.