4. Задачи, требующие принятия решения

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

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

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

Целевая функция описывается следующим выражением: U=F(X,Y),

где X = (x1, x2… xk) - k-мерный вектор управляемых параметров;

Y = (y1, y2… yl) – l- мерный вектор неуправляемых параметров.

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

xi min xi xi max (i=1,2,…k)

или условиям f(X) < 0, f(X) > 0, f(X) = 0, т.е. функциональным ограничениям.

Пример 4. Линейная оптимизационная задача (закупка топлива). На этом примере покажем, как решать задачи, требующие принятия решений, методом линейной оптимизации, когда целевая функция линейно зависит от управляемых параметров: F(X)=c1x1+c2x2+…+ckxk. На компоненты вектора X также накладываются ограничения в виде линейных равенств или неравенств.

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

Математическая модель. Все данные о закупке топлива помещены в ячейки A1:D4, (табл. 8). В строке 7 помещены произвольно выбранные числа, задающие стартовую точку при решении задачи оптимизации.

Всоответствии с исходными данными таблицы целевая функция записывается следующим образом: F(X)=10x1 + 6x2 + 2x3.

В приведенных формулах x1, x2, x3 – количество топлива первого, второго и третьего сорта.

Ограничения удовлетворяют следующим условиям.

• Общая теплотворная способность: 10x1 + 8x2 + 4x3=4000.

• Общее количество золы: 0,02x1 + 0,04x2 + 0,08x3  56.

• Переменные x1, x2, x3 не могут принимать отрицательные значения: xi > 0.

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

Для решения задачи указатель устанавливается в целевую ячейку E8, содержащую критерий. Далее вызывается процедура Поиск решения из меню Сервис. В диалоговом окне Поиск решения (рисунок 2) указан адрес целевой ячейки, переключатель условий поиска установлен в положение Равной минимальному значению. В поле Изменяя ячейки внесены адреса ячеек с управляемыми переменными. Все ограничения занесены в поле с соответствующим заголовком.

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

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

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

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

В данной задаче можно поставить вопрос о том, при каком соотношении цен станет выгодно покупать какое-то количество топлива первого сорта. Анализ задачи показывает, что если цена топлива первого сорта снизится до 8 руб./тонн, а требование к общему количеству золы снизится до 40 тонн, то нужно закупить 0,33; 332,85 и 333,5 тонн топлива первого, второго и третьего сорта соответственно. Минимальные затраты на закупку топлива при этом составят 26667 рублей.

Пример 5. Линейная оптимизационная задача (оптимальная производственная программа сборочного цеха).

Постановка задачи. Предприятие занимается сборкой бытовой электронной аппаратуры трех наименований: телевизоров, сканеров и акустических систем. На изготовление каждого вида изделия требуются комплектующие пяти наименований: шасси, кинескопы, громкоговорители, источники питания и радиодетали (табл. 10). Склад запасов предприятия вмещает ограниченное количество комплектующих и на момент расчета заполнен до отказа. Количество изделий каждого типа выпускается с учетом конъюнктуры рынка: ximin xi (i=1, 2, 3).

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

Математическая модель. Неизвестными в задаче являются количество выпускаемых телевизоров (x1), количество стереосистем (x2), количество акустических систем (x3).

В соответствии с исходными данными (табл. 10) целевая функция записывается следующим образом:

F(X)=75x1 + 50x2 + 35x3.

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

• По шасси: x1 + x2  450.

• По кинескопам: x1  250.

• По громкоговорителям: 2x1 + 2x2 + x3  800.

• По источникам питания: x1 + x2  450.

• По радиодеталям: 2x1 + x2 + x3  600.

Ограничения с учетом конъюнктуры рынка:

x1  20; x2  20; x3  50 .

Решение. Сведения о количестве комплектующих, входящих в состав каждого изделия, введены в ячейки D4:F8 (табл. 10). Запасы на складе указаны в ячейках B4:B8, размер прибыли от реализации одного изделия - в ячейках D10:F10. В строку 11 введены формулы, необходимые для вычисления объема выпуска. В целевую ячейку D12 введена формула: =СУММ(D11:F11).

Вызываемпроцедуру Поиск решения и заполняем поля одноименного окна условиями задачи в соответствии, рис. 3.

Анализ выполнения ограничений показывает, что из пяти типов комплектующих полностью на оптимальную программу расходуются только громкоговорители и радиодетали. По остальным позициям имеется запас. Следовательно, возможности развития производства следует рассматривать за счет увеличения запасов по двум полностью израсходованным позициям и уменьшения запасов по другим позициям с целью высвобождения места на складе. Например, увеличение запаса громкоговорителей до 950 единиц, радиодеталей – до 675 единиц и уменьшение запаса кинескопов до 175 единиц увеличивает прибыль с 24 875 руб. до 28 625 руб., а все запасы оказываются полностью выбранными.

Пример 6. Транспортная задача.

Постановка задачи. Фирма «Альтаир» имеет 4 предприятия и 5 центров продажи ее товаров. Центры продаж располагаются в Омске, Томске, Иркутске, Хабаровске и Владивостоке. Предприятия располагаются в Ирбите, Ревде, Первоуральске и Екатеринбурге. Исходными данными для решения задачи являются:

• ежедневные объемы производства предприятий;

• ежедневные потребности в продукции в центрах продаж;

• стоимость перевозки единицы продукции с предприятия в центры продаж;

• стоимость хранения на складе предприятия;

• штраф за просрочку поставки продукции, заказанной центром продаж.

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

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

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

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

Математическая модель. Неизвестными в задаче являются объемы перевозок xij с i – го предприятия в j - й центр продаж. Целевая функция описывается следующим выражением: U=, где cij – стоимость перевозки с i – го предприятия в j - й центр продаж. Целевую функцию необходимо минимизировать.

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

, j = 1,..5; , i = 1,..4,

где ai – объем производства на i – м предприятии, bj – спрос в j - м центре продаж.

Кроме того, объемы перевозок не могут принимать отрицательные значения:

xij 0, i = 1,..4, j = 1,..5.

Решение. Все данные о стоимости перевозок введены в ячейки B3:F6 (табл. 11). Данные об объемах производства, о потребностях в продукции в центрах продаж помещены в ячейки H8:H11 и B13:F13 соответственно. Ячейки B8:F11, отведенные под значения неизвестных, заполняются перед вызовом процедуры Поиск решения произвольными числами. В столбец G введены формулы, вычисляющие объемы производства на предприятиях. В строку 12 введены формулы, вычисляющие объемы доставляемой продукции. В целевую ячейку B17 введена функция:

=СУММПРОИЗВ(B3:F6;B8:F11).

Диалоговое окно Поиск решения заполняется в соответствии с рис. 4.

Оптимальный план поставок продукции и соответствующие ему транспортные расходы представлены в табл. 11.

Пример 7. Задача о назначении.

Постановка задачи. Имеются четыре рабочих и четыре вида работ. Стоимости cij выполнения i – м рабочим j – й работы известны. Необходимо составить так план выполнения работ, чтобы все работы были выполнены, каждый рабочий был загружен только на одной работе, а суммарная стоимость работ была минимальной.

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

Математическая модель. Неизвестными в задаче являются переменные xij. Будем считать, что xij = 1, если i – м рабочим выполняется j – я работа, и xij = 0, если i – м рабочим не выполняется j – я работа. Таким образом, xij принимает только два значения: 0 или 1. Такие переменные называются двоичными. Кроме того, неизвестные должны удовлетворять еще одним ограничениям:

, j = 1,..4; , i = 1,..4.

Целевая функция описывается следующим выражением: U= .

Эту функцию необходимо минимизировать.

Решение. Все данные о стоимости работ введены в ячейки B3:E6 (табл. 12). Ячейки B8:E11 отведены под неизвестные. Ячейки строки 12 и столбца F заполнены формулами, задающими левые части ограничений на переменные задачи (использована функция автосуммирования).

В целевую ячейку F13 введена формула, вычисляющую общую стоимость работ: =СУММПРОИЗВ(B3:F6;B8:F11).