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

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

Обозначим ai, j — объём i-ого ресурса, который расходуется на производство одной единицы j-ого вида продукции; xj — количество единиц j-ого вида продукции в производственном плане предприятия; bi — максимальное количество i-ого вида ресурса; сj — прибыль на единицу j-ого вида продукции (i=1,…,m; j=1,…,n).

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

(5).

Тогда, учитывая ограничения на ресурсы, получаем следующую систему неравенств:

(6).

(7).

(8).

(9).

(i=1,…,n), (10).

Кроме того, в некоторых случаях (в зависимости от единицы измерения выпускаемой продукции) следует предполагать, что xi принимают целые значения.

Пример 1. Предприятие выпускает 2 вида продукции. Цена единицы 1 вида продукции — 25 000 руб., 2 вида продукции — 50 000 руб. Для изготовления продукции используются три вида сырья, запасы которого 37, 57.6 и 7 условных единиц. Нормы затрат каждого сырья на единицу продукции представлены в следующей таблице.

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

Решение. Пусть продукция производится в количестве: 1-й вид — x1 единиц, 2-й вид — x2 единиц. Тогда стоимость произведенной продукции выражается целевой функцией:

f(x1,x2)=25 000 x1+50 000x2,.

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

• 1.2 x1+1.9 x2 37;
• 2.3 x1+1.8 x2 57,6;
• 0.1 x1+0.7 x2 7;

x10, x2 0.

Также будем предполагать, что x1 и x2 принимают целые значения.

Запишем полученную математическую модель в новом документе MS Excel (рис. 2.2.1).

Рис. 1.

Внесем в таблицу значения стоимости продукции, данные о расходах и запасах всех видов сырья. При этом будем предполагать, что первоначально x1 и x2 равны нулю (ячейки C2 и D2). В ячейку H1 запишем целевую функцию:

=C2*C3+D2*D3.

Столбец Затраты заполним следующими значениями:

Найдем решение данной задачи используя пакет Поиск решения MS Excel.

Пакет Поиск решений (Solver) — дополнительная надстройка MS Excel, которая предназначена для решения определенных систем уравнений, линейных и нелинейных задач оптимизации.

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

• · количество неизвестных (decision variable) — 200;
• · количество формульных ограничений (explicit constraint) на неизвестные — 100;
• · количество предельных условий (simple constraint) на неизвестные — 400.

Вызов пакета Поиск решения осуществляется выбором в меню «Сервис» вкладки «Поиск решения» (рис. 2.2.2).

Рис. 2.

Если пакет Поиск решения отсутствует, то для его установки необходимо:

• 1. В меню «Сервис» выбрать вкладку «Надстройки» (рис. 2.2.3).
• 2. Установить флажок возле строки «Поиск решения» (рис. 2.2.4).

Рис. 3.

Рис. 4.

В окне Поиск решения следует выполнить следующие действия (рис. 2.2.5):

• 1. Установить целевую ячейку (ячейка H1);
• 2. Указать, что необходимо найти максимальное значение целевой функции;
• 3. Указать адреса изменяющихся ячеек, т. е. ячеек в которых находятся значения переменных x1 и x2 (ячейки C2 и D2);

Рис. 5.

4. Добавить все необходимые ограничения, используя раскрывающийся список условных операторов (=, цел. или двоич.) (рис. 2.2.6). Если выбран цел., то в поле Ограничение появится «целое». Если выбрано двоич., в поле Ограничение появится «двоичное»;

Рис. 6.

5. При необходимости изменить параметры поиска решения (рис. 2.2.7).

Рис. 7.

Максимальное время — служит для ограничения времени, отпущенного на поиск решения задачи. В этом поле можно ввести время в секундах, не превышающее 32 767 (примерно девять часов); значение 100, используемое по умолчанию, вполне приемлемо для решения большинства простых задач.

Предельное число итераций — управляет временем решения задачи путем ограничения числа вычислительных циклов (итераций).

Относительная погрешность — определяет точность вычислений. Чем меньше значение этого параметра, тем выше точность вычислений.

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

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

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

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

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

Показывать результаты итераций — приостанавливает поиск решения для просмотра результатов отдельных итераций.

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

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

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

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

Разности прямые — используется в большинстве задач, где скорость изменения ограничений относительно невысока. Увеличивает скорость работы средства Поиск решения.

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

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

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

• 6. Нажать кнопку Выполнить.
• 7. В окне результатов поиска решения выбрать операцию сохранения найденного решения (рис. 2.2.8).

Более того, по найденным результатам можно создавать отчеты. Отчеты полезны для сравнения влияния на решение различных ограничений или исходных данных. Поэтому они являются очень важными инструментами для анализа полученных результатов и последующего их улучшения в зависимости от возможностей и ресурсов предприятия. Отчеты бывают трех типов: по результатам (Answer), по устойчивости (Sensitivity), по пределам (Limit).

Тип отчета выбирается по окончании поиска решений в диалоговом окне Результаты поиска решений (Solver results) в списке Отчеты (Reports). С помощью левой клавиши мыши, при нажатой клавиши, можно выбрать сразу два или три типа отчета. При этом каждый отчет будет создан на отдельном рабочем листе.

Рис. 8.

Из отчета, составленного по результатам (рис. 2.2.9), получим, что максимальная стоимость произведенной продукции рана 825 000 руб. При этом должен выполняться следующий план производства: 1-ый вид продукции — 19 единиц, 2-ой вид продукции — 7 единиц.

Рис. 9.

Пример 2. Банк собирается выдать кредиты по следующим типам:

Общая сумма кредитов не должна превышать 1 000 млн. р. При этом банк обязан выдать не менее 30% всех кредитов на покупку авто и не более 50% - на жилье. Общая доля невозврата не должна превосходить 0.09. Определить какую сумму следует выдавать банку на каждый вид кредита, чтобы максимизировать общий доход.

Пример 3. Компания производит 2 типа деталей. Для производства 1 детали первого типа требуется 1 человеко-час, а для производства детали второго типа требуется 2 человеко-часа. Фонд рабочего времени компании 4000 человеко-часов в неделю. Производственные мощности позволяют выпускать максимум 2250 деталей первого типа и 1750 деталей второго типа в неделю. Каждая деталь первого типа требует 2 кг металлических стержней и 5 кг листового металла. Для производства одной детали второго типа необходимо 5 кг стержней и 2 кг листового металла. Запас каждого вида сырья 10 000 кг в неделю. Известно, что еженедельно завод поставляет заказчику не менее 600 деталей первого типа. Сколько деталей каждого типа следует производить, чтобы максимизировать общую прибыль за неделю. Если прибыль от производства одной детали первого типа составляет 30 у.е., а от производства одной детали второго типа — 40 у.е.

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

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