Описание отчетов о решении задачи

Отчет по результатам: таблица Целевая ячейка выводит сведения о целевой функции; таблица Изменяемые ячейкипоказывает значение искомых переменных, полученных в результате решения задачи; таблица Ограничения отображает результаты оптимального решения для ограничений и для граничных условий. В поле Формулаприведены зависимости, которые были введены в окно Поиск решения,в поле Разница– величины использованного материала. Если материал используется полностью, то в поле Статусуказывается связанное,при неполном использовании материала в этом поле указывается не связан.Для граничных условий приводятся аналогичные величины с той лишь разницей, что вместо величины неиспользованного продукта показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.

Отчет по устойчивости содержит информацию о том, насколько полученное решение устойчиво при изменениях в коэффициентах целевой функции и ограничениях. В графе Изменяемые ячейки приводятся рассчи­танные значения искомых переменных и их двойственных оценок. Для каждой переменной рассчитывается показатель Нормированная стоимость (в Excel 7.0 – «редуцированная стоимость») – коэффициент, показывающий, насколь­ко изменяется целевая функция при изменении соответствующей переменной (т.е. при ее принудительном включении в оптимальный план) на одну единицу. В этой же графе приводятся оценки для предельных приращений коэффициен­тов целевой функции (допустимое увеличение и допустимое уменьшение), при которых возможно корректное применение показателя «нормированная стои­мость», а также сохраняется оптимальное решение (т.е. сохраняется структура оптимального плана).

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

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

3. Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений

В 1975 г. наш соотечественник Л.В. Канторович был удостоен Нобелевской премии по экономике (совместно с американским экономистом Т. Купмансом) за разработку теории оптимального использования ресурсов. С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной; первоначальная задача называется исходной, или прямой. Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.

Переменные двойственной задачи y_i называются объективно обусловленными оценками (или двойственными оценками, «ценами» ресурсов, теневыми ценами).

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

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

1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи – на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид (≤), в задаче на минимум вид (≥);

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица А^Тв двойственной задаче получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной;

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи – коэффициенты при неизвестных в целевой функции исходной;

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

Модель исходной (прямой) задачи в общем виде может быть записана следующим образом:

, (10)

(11)

а модель двойственной задачи –

(12)

(13)

Решая ЗЛП симплекс-методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи y_ί называют объективно обусловленными оценками.

Рассмотрим анализ оптимального решения на основе примера 1. Решение произведено с использованием MS Excel (Поиск решения) и представлено на рисунке 13.

Создание отчёта по результатам поиска решения

Excel позволяет представить результаты поиска решения в форме отчёта (рис. 25, 26).

Существует три типа таких отчётов:

· отчет по устойчивости «Sensitiviti», содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений;

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

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

В отчёте по результатам содержатся оптимальные значения переменных Х1, Х2, Х3, Х4 , которые, соответственно, равны 0; 30; 10; 0; значение целевой функции – 150, а также левые части ограничений (рис. 25).

Рис. 25. Отчёт по результатам