Предельное число итераций

Служит для назначения числа итераций. Используемое по умолчанию значение 100 подходит для решения большинства задач.

После этих пояснений продолжим решение задачи.

2. Установить флажок Линейная модель, что обеспечивает применение симплекс-метода.

3. ОК.

На экране: знакомое уже диалоговое окно Поиск решения (рис. 3.3.7).

4. Выполнить.

На экране: диалоговое окно Результаты поиска решения. Решение найдено (рис. 3.3.10) и результат оптимального решения задачи приведены в таблице (рис. 3.3.11).

Рис. 3.3.10

Рис. 3.3.11

На рис. 3.3.11 видно, что в оптимальном решении

Прод1 = В3 = 10,

Прод2 = С3 = 0,

Прод3 = D3 = 6,

Прод4 = Е3 = 0.

При этом максимальная прибыль будет составлять F6 = 1320, а количество использованных ресурсов равно

трудовых = F9 =16,

сырья = F10 = 84,

финансов = F11 = 100.

Таково оптимальное решение рассматриваемой задачи распределения ресурсов. Однако решение задачи находится не всегда. Если условия задачи несовместны, на экране появляется диалоговое окно (рис. 3.3.12).

Рис. 3.3.12

Необходимые действия в этом случае рассматриваются в 3.3.5.

Если целевая функция не ограничена, то на экране появится диалоговое окно (рис. 3.3.13).

Рис. 3.3.13

Необходимые действия в этом случае рассматриваются в 3.3.6.

3.3.4. Графическое представление
результатов решения

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

Результат решения задачи, приведенный на рис. 3.3.11, был принят в качестве исходных данных при рассмотрении алгоритмов построения диаграмм различных типов в главе 2, разделе 2.2.

Диаграммы, построенные по этим данным, представлены на рис. 2.2.8, 2.2.9, 2.2.13, 2.2.14, 2.2.16. После получения оптимального решения рассмотренной задачи мы настоятельно рекомендуем внимательно посмотреть эти построенные диаграммы. Приведенные диаграммы убедительнее всяких слов доказывают преимущества наглядного представления результатов оптимального решения.

3.3.5. Преодоление несовместности

Как уже говорилось, достаточно часто при решении задач распределения ресурсов условия задачи оказываются несовместными. Мы обещали сказать, что же следует делать в таких случаях. Для этого рассмотрим следующий пример. В задаче, которую мы решали, было получено оптимальное решение Прод1 = 10, Прод3 = 6. При этом трудовые ресурсы и финансы были использованы полностью. Для получения несовместности в учебных целях, изменим условия задачи, сохранив значения переменных, которые мы получили в оптимальном решении Прод1 = 10, Прод3 = 6. Дополнительно еще назначим Прод2 = 5.

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

Алгоритм 3.3.4. Изменение условий задачи

1. Вызвать исходную таблицу (рис. 3.3.5).

2. По алг. 3.3.2 вызвать диалоговое окно Поиск решения.

3. Изменить граничные условия для Прод1:

Ø В окне Ограничения курсор на строку $B$3>=$B$4.

Ø Изменить...

На экране: диалоговое окно Изменить ограничение.

Ø Ввести изменение: $B$3=10.

Ø ОК.

4. Аналогично ввести значение для Прод3: D3=6.

5. Ввести дополнительное условие для Прод2:

Ø Добавить.

Ø Ввести: С3=5.

Ø ОК.

На этом ввод изменений закончен.

6. Решить задачу.

На экране: диалоговое окно рис. 3.3.12.

Появление этого диалогового окна — признак несовместного решения. Что же делать в таких случаях? Обратимся к математической модели. Рассматриваемая задача имеет модель:

(3.3.1)

Для выяснения причин несовместности введем дополнительные необходимые ресурсы t_i и запишем систему в виде:

(3.3.2)

Такая постановка задачи дает возможность определить минимальное значение дополнительных необходимых ресурсов t₁, t₂, t₃.

Для ввода условий задачи систему (3.3.2) запишем в виде:

(3.3.3)

Чтобы ввести эту систему, откорректируем таблицу для ввода данных (рис. 3.3.4) и сделаем ее такой, как на рис. 3.3.14 (данные) и рис. 3.3.15 (формулы).

Рис. 3.3.14 отличается от рис. 3.3.4 следующим:

rвведены столбцы F:H для переменных t₁, t₂, t₃;

rв ячейках F9:H11 введены — 1;

rв ячейке I6 зависимость для прибыли сохранена;

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

Рис. 3.3.14

Рис. 3.3.15

На основании рассмотренного можно записать следующий алгоритм.

Алгоритм 3.3.5. Преодоление несовместности

1. Откорректировать таблицу ввода условий задачи (рис. 3.3.4), как это показано на рис. 3.3.14.

Ø Ввести для новых переменных t₁, t₂, t₃ столбцы F:H.

Ø В ячейках F9:H1 ввести коэффициенты –1, с которыми эти переменные входят в ограничения.

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

Заметим, что формула старой целевой функции осталась без изменений.

2. Сервис, Поиск решения...

3. Установить целевую ячейку I4 равной минимальному значению.

4. В окно Изменяя ячейки ввести В3:Н3.

5. В окно Ограничения ввести ограничения и граничные условия:

B3 = 10 E3 >= 0 I9 <= K9

C3 = 5 F3 >= 0 I10 <= K10

D3 = 6 G3 >= 0 I11 <= K11

H3 >= 0

6. Выполнить.

На экране: результат решения, показанный на рис. 3.3.16.

Рис. 3.3.16

Из этого рисунка видно, что искомый дополнительный потребный ресурс равен t₁ = 5, t₂ = 0, t₃ = 30. Это значит, что для заданного выпуска продукции необходимо иметь всего следующее количество ресурсов:

трудовые 16+5=21,

сырье 110+0=110,

финансы 100+30=130.

При этом будет получена прибыль, равная 1670.

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

3.3.6. Устранение неограниченности
целевой функции

В 3.2.1 мы рассматривали систему (3.2.2). Добавим к системе целевую функцию, тогда получим:

которая графически была представлена на рис. 3.2.2. Было показано, что задача (3.2.2) имеет неограниченную целевую функцию. Посмотрим, как будет решаться такая задача в Excel. Условия задачи в формате, необходимом для ее решения в Excel, приведены на рис. 3.3.17.

Рис. 3.3.17

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

х₁ + х₂ і 2,

после чего (3.2.2) будет иметь вид:

(3.3.4)

что графически представлено на рис. 3.3.18.

 

Ввод условий задачи (3.3.4) в форме ввода формул и в форме ввода данных, а также результат ее решения приведены на рис. 3.3.19.

 

 

Рис. 3.3.19

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

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

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

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

Зная эти правила, легко устранить неограниченность целевой функции, признаком которой является появление на экране диалогового окна (рис. 3.3.13).

3.4. Анализ задач
линейного программирования в Excel

3.4.1. Анализ оптимального решения

Анализ оптимального решения выполняется на основании применения тех положений симплекс-метода, которые были достаточно подробно рассмотрены в 3.2.3, и начинается после успешного решения задачи, когда на экране появляется диалоговое окно Результат поиска решения. Решение найдено. (рис. 3.3.10). С помощью этого диалогового окна можно вызвать отчеты трех типов:

rрезультаты;

rустойчивость;

rпределы.

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

Алгоритм 3.4.1. Вызов отчетов анализа

На экране: диалоговое окно Результат поиска решения. Решение найдено (рис. 3.3.10).

1. Курсор на тип вызываемого отчета. Начнем сОтчета по результатам.

ОК.

На экране: вызванный отчет на новом листе, на ярлычке которого указано название отчета.

3. Курсор на ярлычок с названием отчета.

М1.

На экране: вызванный отчет (рис. 3.4.1).

Рис. 3.4.1

Отчет по результатам

Отчет состоит из трех таблиц:

rТаблица 1приводит сведения о целевой функции.

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

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

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

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

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

Отчет по устойчивости

Отчет по устойчивости (рис. 3.4.2) состоит из двух таблиц.

Рис. 3.4.2

В таблице 1приводятся следующие значения для переменных:

rрезультат решения задачи;

rредуц. стоимость, т. е. дополнительные двойственные переменные v_j, которые, как рассматривалось в 3.2.3, показывают, насколько изменяется целевая функция при принудительном включении единицы этой продукции в оптимальное решение;

rкоэффициенты целевой функции;

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

В таблице 2приводятся аналогичные значения для ограничений:

rвеличина использованных ресурсов;

rтеневая цена, т. е. двойственные оценки z_i, которые показывают, как изменится целевая функция при изменении ресурсов на единицу;

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

Задачи анализа, которые можно решать с помощью приведенных величин Dc_j и Db_i, были подробно рассмотрены в 3.2.3.

Отчет по пределам

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

rприводятся значения x_j в оптимальном решении;

rприводятся нижние пределы изменения значений x_j.

Рис. 3.4.3

Кроме этого, в отчете указаны значения целевой функции при выпуске данного типа продукции на нижнем пределе. Так, при значении 720 видно, что F = c₁x₁ + c₃x₃ = 60 ´ 0 + 120 ´ 6 = 720. Далее приводятся верхние пределы изменения x_j и значения целевой функции при выпуске продукции, вошедшей в оптимальное решение на верхних пределах.

Поэтому везде F = 60 ´ 10 + 120 ´ 6 = 1320.

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

3.4.2. Параметрический анализ

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

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

Алгоритм 3.4.2. Выполнение параметрических расчетов

1. Подготовительные работы.

1.1. Составить таблицу вариантов (рис. 3.4.4).

Рис. 3.4.4

1.2. Вызвать на экран таблицу с результатом решения задачи (рис. 3.3.11).

1.3. Удалить результат решения, находящийся в B3:E3:

Ø Выделить В3:Е3.

Ø <Delete >.

Ø Убрать выделение.

2. Решение задачи для 1-го варианта.

2.1. Ввести в ячейку Н11 =50.