1.9. Задача об оптимальном использовании ограниченных ресурсов. Продукцией городского молочного завода являются молоко, кефир и сметана. На производство 1 т молока, кефира и сметаны требуется соответственно 1,01; 1,01 и 9,45 т молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машиночаса. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 ч. Всего для производства цельномолочной продукции завод может использовать 136 т молока. Основное оборудование может быть занято в течение 21,4 машиночасов, а автоматы по расфасовке сметаны – в течение 16,25 ч. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока.

Требуется определить объемы выпуска молочной продукции, позволяющие получить наибольшую прибыль. К чему приведет задание по выпуску кефира в объеме не менее 10 т?

Решение.

Составим вспомогательную таблицу.

Экономико-математическая модель.

Обозначим через X₁, X₂, X₃ объемы производства соответствующего вида продукции (молока, кефира и сметаны).

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

                   ḟ(x) = 30X₁ + 22X₂ + 136X₃.

Ограничения по ресурсам:

1,01X₁  + 1,01 X₂  +  9,45 X₃ ≤ 136

 0,18 X₁  + 0,19 X₂  ≤ 21,4 

3,25 X₂ ≤ 16,25

X₁, X₂, X₃ ≥ 0

X₁ ≥ 100.

1. Теперь переходим к решению задачи программными средствами. Для этого мы используем MS Excel 2000. Создаем текстовую форму – таблицу для ввода задачи и заполняем ее исходными данными:

2. Выбираем и указываем адреса ячеек, в которые будет помещен результат решения. В нашей задаче оптимальные значения компонент вектора X = (X₁, X₂, X₃) будут помещены в ячейках В3:D3. Оптимальные значения целевой функции – в ячейке E4.

3. Вводим зависимость для целевой функции. С помощью Мастера функций открываем функцию СУММПРОИЗВ.

В строку «Массив 1» вводим $B$3:$D$3.

В строку «Массив 2» вводим B4:D4.

Нажимаем кнопку «ОК». На экране в ячейку Е4 введена функция.

4. Теперь вводим зависимости для ограничений:

Курсор в ячейку E4.

На панели инструментов кнопка Копировать в буфер.

Ставим курсор в ячейку E7.

На панели инструментов кнопка Вставить из буфера.

Ставим курсор в ячейку E8.

На панели инструментов кнопка Вставить из буфера.

Курсор в ячейку E9.

На панели инструментов кнопка Вставить из буфера.

Проверяем содержимое ячеек Е7:Е9.

5. В строке Меню указатель мыши на имя Сервис.  В развернутом меню выбираем команду Поиск решения. Появляется диалоговое окно Поиск решения.

Устанавливаем целевую ячейку: вводим адрес $E$4.

Выбираем направление целевой функции – Максимальному значению.

Курсор в строку Изменяя  ячейки. Вводим адреса искомых переменных $B$3:$D$3.

6. Вводим ограничения:

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

В строке Ссылка на ячейку вводим адрес $E$7. Вводим знак ограничения <=. В строке Ограничение вводим $G$7.

Введем остальные ограничения задачи по описанному выше алгоритму.

После введения последнего ограничения нажимаем кнопку ОК. На экране появляется диалоговое окно Поиск решения с введенными условиями.

7. Вводим параметры для решения ЗЛП. В диалоговом окне ставим указатель мыши на кнопку Параметры. На экране появляется окно Параметры поиска решения.

Устанавливаем флажки в пунктах Линейная модель (что обеспечит применение симплекс-метода) и Неотрицательные значения.

Нажимаем кнопку ОК. На экране снова диалоговое окно Поиск решения. Нажимаем кнопку Выполнить.

Через непродолжительное время появится диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками B3:D3 для значений X_i и ячейка Е4 с максимальным значением целевой функции.

Задаем параметры по выпуску кефира в объеме не менее 10 т.

Для этого добавляем еще одно ограничение. В строке Ссылка на ячейку вводим адрес $C$3. Вводим знак ограничения >=. В строке Ограничение вводим 10.

Возвращаемся в окно Поиск решения и нажимаем кнопку Выполнить. На экран выводятся результаты решения.

Полученные решения означают, что максимальную прибыль 3627,32 руб. городской молочный завод может получить при выпуске и реализации 118,89 т. молока и 1,68 т. сметаны. Кефир при этом не производится. При этом сырье оборудование по производству молока и кефира будут использоваться полностью, а из возможных 16,25 ч. оборудование по расфасовке сметаны будет задействовано 5,48 ч.

Если же задать параметры по выпуску кефира в объеме не менее 10 т., то завод будет получать прибыль 3532,79 руб. при выпуске и реализации 108,33 т. молока, 10 т. кефира и 1,74 т. сметаны.

2.9. Транспортная задача. Администрация деревоперерабатывающего предприятия «Смена» приняла на работу пять человек. Каждый из них имеет различные способности и навыки и затрачивает различное время на выполнение определенной работы. В настоящее время необходимо выполнить пять видов работ. Время выполнения работы каждым работником приведено в таблице.

1.                 Требуется назначить на каждый вид работы одного из работников. Как это следует сделать, чтобы общее время, необходимое для завершения всех видов работ, было минимальным?

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

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

Решение.

Обозначим через x_ij назначение i-го работника на j-работу и через C_ij время, необходимое для выполнения определенной работы. Так как количество работников равно количеству должностей и один работник может выполнять только один вид работы,  то x_ij может принимать только два значения: 1 (если работник назначен на выполнение работы) или 0 (если не назначается).

1. Создаем форму для решения задачи – матрицу назначений по должностям. Выполняем резервирование изменяемых решений: в блок ячеек В3:F7 вводятся «1». Таким образом резервируется место, где после решения задачи будет проводиться распределение по видам работ, обеспечивающее минимизацию общего времени выполнения работ.

где x_ij - назначение i-го работника на j-работу;

m – количество возможных работ.

Для этого необходимо выполнить следующие операции:

Курсор в ячейку А3. Щелкнуть знак «Σ». Выделить необходимые для суммирования ячейки В3:F3. Нажать ENTER – подтверждение ввода формулы для суммирования.

Аналогичные действия выполнить для ячеек А4, А5, А6, А7, т.е. ввести условия реализации выполнения каждого вида работы.

Введение условия заполнения вакантной должности, т.е

Для этого необходимо выполнить следующие операции. Курсор в В8. Щелкнуть знак «Σ». При этом автоматически выделяется весь столбец В3:В7. Нажать ENTER – подтверждение ввода формулы для суммирования. Последовательность тех же действий выполнить для ячеек С8:F8.

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

Вводим исходные данные – время выполнения конкретных видов работ (в ячейки А13:А17 вводится «1»), потребности назначения на вакантную работу (в ячейки В12:F12 вводится «1»), ввод затрачиваемого времени на выполнение одного вида работ каждым работником (блок В13: F17). 

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

где C_ij - время, необходимое для выполнения j-работы i-м работником.

x_ij - назначение i-го работника на j-работу.

Для этого ставим курсор в ячейку В19. В данную ячейку будет помещаться значение целевой функции после решения задачи. Щелкаем Мастер функций. В окне Категория выбираем Математические. В окне Функция выбираем СУММПРОИЗВ. Щелкаем ОК. В окне СУММПРОИЗВ указываем адреса массивов, элементы которых обозначаются этой функцией.

В задаче целевая функция представляет собой произведение времени выполнения работы (расположенных в блоке ячеек В13: F17) и назначения работников на выполнение работы (содержимое ячеек В3:F7). Для этого в поле Массив 1 указать адреса В13: F17, а в поле Массив 2 указать адреса В3:F7. ОК – подтверждение окончания ввода адресов массивов. В ячейке В19 появляется числовое значение, равное произведению «1» на время выполнения  конкретной работы определенным работником. В нашей задаче 492.

4. Вводим зависимости из математической модели.

Для осуществления данного этапа необходимо выполнить следующий перечень операций. Щелкаем Сервис – Поиск решения, подводим курсор в поле Установить целевую ячейку, вводим адрес $B$19. Таким образом производится указание ячейки, куда при решении задачи помещается значение целевой функции. Устанавливаем направление изменения целевой функции, равное «минимальному значению».

Вводим адреса изменяемых ячеек. Для этого щелкаем в поле Изменяя ячейки, где вводим адреса $В$3:$F$7.

Вводим ограничения задачи. В матрицу с исходными данными необходимо ввести условие назначения работника только на одну работу. Для этого щелкаем Добавить ограничения, в поле Ссылка на ячейку вводим адреса $A$3:$A$7, в среднем поле устанавливаем знак «=». В поле Ограничение установить адреса $A$13:$A$17. Щелкаем ОК, возвращаемся в поле Поиск решения.

Далее вводим ограничение, которое реализует условие выполнения каждой из работ. Для этого щелкаем Добавить ограничение, в поле Ссылка на ячейку вводим адреса $B$8:$F$8, в среднем поле устанавливаем знак «=». В поле Ограничение установить адреса $B$12:$F$12. Щелкаем ОК, возвращаемся в поле Поиск решения.

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

5. Просмотр результатов и вывод отчета.

После выполнения всех вышеуказанных действий на экран выводится окно Результаты поиска решения. В окне Тип отчета выбираем Отчет по результатам. Теперь у нас появляется еще один лист – Отчет по результатам 2.9.

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

Вывод: минимальное общее время выполнения работ будет достигнуто при назначении:

-                           первого работника на Работу 4 (содержимое ячейки Е3 равно 1)

-                           второго работника на Работу 1 («1» в ячейке В4);

-                           третьего работника на Работу 2 («1» в ячейке С5);

-                           четвертого работника на Работу 5 («1» в ячейке  F6);

-                           пятого работника на Работу 3 («1» в ячейке D7).

…………………………………………………………………………………………………………………………………………………………………………………………………………………………………..