Метод линейного программирования

Рассмотрим типовую задачу оптимизации. Это задача о красках^[1].

Фабрика изготовляет два вида красок: для внутренних и наружных работ (2 и 1). Для производства используется два исходных продукта: А и В.

Максимально возможные суточные запасы продуктов составляют соответственно 6 и 8 т. Расходы продуктов на производство одной тонны краски 2: 1 и 2 т, краски 1: 2 и 1 т соответственно. Суточный спрос на краску 2 не превышает 2 т, и ее не продается никогда больше.

Цена на первую краску — 3 тыс., а на вторую — 2 тыс.

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

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

Сделаем некоторые обозначения. Пусть Х₀ — целевая функция; функция, которой нужно доставить максимальное значение;

Xj — объем производства краски 1 (для наружных работ).

Х₂ — объем производства краски 2 (для внутренних работ). Совершенно очевидно, что можно записать выражение для целевой функции.

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

Совершенно очевидно, что с увеличением переменных X, и Х₂ будет увеличиваться и доход от продаж. Но переменные X, и Х₂ ограничены запасами исходных продуктов, А и В, 6 и 8 т соответственно. Составить неравенства мне лично помогала вот такая схема (рис. 3.87). (Схема сделана в Excel, так как сейчас мы изучаем именно эту программу, а так, конечно, есть более совершенные инструменты.).

Рис. 3.87. Иллюстрация постановки задачи о красках.

Продукта, А расходуется на производство красок 1 и 2. Коэффициенты в неравенстве суть объемы исходного продута А, затрачиваемого на производство одной тонны каждой из красок, а X, и Х₂это объемы производства этих красок. И затраты исходного продукта, А не могут превышать 6 т.

Соответственно для продукта В можно записать следующее неравенство:

Ну и самое простое неравенство связано с тем, что краски для наружных работ никогда не продается больше двух тонн:

Итак, мы создали математическую модель задачи оптимизации. Мы определили:

• 1) целевую функцию Х₀;
• 2) управляющие факторы и Х₂;
• 3) ограничения, заданные неравенствами (2)—(4);
• 4) критерий: оптимальным будет такое производство, которое доставит максиму целевой функции (1), т. е. обеспечит максимальный доход от продажи красок.

Теперь необходимо перенести полученную математическую модель на рабочий лист Excel.

Создайте Книгу Excel и назовите ее Задача о красках. Назовите лист ИД (исходные данные) и введите формулы в соответствии с условиями задачи (рис. 3.88):

• 1) в столбце Л внесены имена целевой функции и переменных;
• 2) в ячейках В2 внесено выражение для вычисления целевой функции, в соответствии с выражением (1);
• 3) в ячейках ВЗ и В4 будет получено оптимальное сочетание значений Xj и Х₂, решение задачи оптимизации. Пока эти ячейки пустые. Система будет интерпретировать эти ячейки как нулевые. И целевая функция изначально будет иметь нулевое значение;
• 4) в ячейка D1 и Е1 введены заголовки столбцов;
• 5) в ячейках столбца D введены левые части неравенств (2)—(4);
• 6) в столбце Е — соответственно правые части неравенств.

Рис. 3.88. Условия задачи на листе Excel

У вас должна получиться вот такая картинка на рабочем листе (рис. 3.89). Создайте копию листа ИД и назовите его Формулы.

Рис. 3.89. Рабочий лист задачи оптимизации

А чтобы на листе Формулы были видны введенные нами выражения, нужно выполнить команду Файл / Параметры / Дополнительно / Показывать формулы, а не их значения (рис. 3.90).

Рис. 3.90. Отображение формул на рабочем листе.

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

Решение задач оптимизации в Excel осуществляется с помощью надстройки Поиск решения. Если эта надстройка доступна, то на вкладке Вид в группе Анализ будет доступна опция Поиск решения. В противном случае необходимо выполнить команду Файл / Параметры / Дополнительно / Надстройки / Поиск решения / Перейти (рис. 3.91).

Рис. 3.91. Подключение надстройки Поиск решения

На экране появится окно Надстройки (рис. 3.92). Напротив опции Поиск решения необходимо выставить флаг и щелкнуть по кнопке ОК. В результате на вкладке Вид должна появиться опция Поиск решения.

Рис. 3.92. Окно Надстройки.

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

Теперь, собственно говоря, поиск оптимального решения.

1. Установите курсор в ячейку В2 на листе Решение и вызовите окно Поиск решения (рис. 3.93).

Рис. 3.93. Окно Параметры поиска решения.

В поле Оптимизировать целевую функцию будет введен адрес ячейки В2.

• 2. Наша задача — отыскать максимум целевой функции. Поэтому необходимо выбрать опцию Максимум.
• 3. Оптимальное решение будет отыскиваться за счет изменения значений Х_{ и Х₂, значения которых расположены в ячейках В2 и ВЗ. Этот диапазон необходимо внести в окно Изменяя ячейки переменных.
• 4. Далее необходимо добавить ограничения (2)—(4). Подчеркнем, важно, чтобы по возможности это были ограничения одинакового типа: или меньше, или больше. Все ограничения или меньше, или больше. В таких случаях мы сможем вводить ограничения не по одному, а массивом. Чтобы ввести ограничения, необходимо щелкнуть по кнопке Добавить. В результате появится окно Добавление ограничений (рис. 3.94). В окно Ссылка на ячейки необходимо ввести диапазон ячеек, соответствующий левым частям неравенств. В окно Ограничение — диапазон ячеек с предельными значениями. А в окне между этими двумя окнами выбрать одно из доступных отношений. В нашем случае это отношение меньше или равно. То есть ресурсов может быть израсходовано не больше, чем указано в ячейках Е2: Е4.

Рис. 3.94. Окно Добавление ограничений

• 5. Поскольку не всегда ограничения могут быть однородными, в случае необходимости ввести другие ограничения нужно щелкнуть, но кнопке Добавить. Если все ограничения введены, необходимо щелкнуть по кнопке ОК
• 6. Когда все поля в форме Поиск решения заполнены, необходимо щелкнуть, но кнопке Найти решение. На экране должно появиться окно Результаты поиска решения (рис. 3.95).

Рис. 3.95. Результат поиска решения

7. Нами получено правильное решение. Единственно, что можно сделать, так это немного изменить это решение по форме, изменить формат ячеек: шесть знаков после запятой в нашем случае едва ли оправданная точность. И такое количество знаков только мешает восприятию. В данной ситуации уместнее дробный формат (рис. 3.96).

Рис. 3.96. Окно Формат ячеек

В таком случае решение будет именно таким, каким его можно видеть в книге Тахи в эпоху решения задачи оптимизации вручную (рис. 3.97).

Рис. 3.97. Представление решения в дробном формате

8. И только в самом конце можно заняться оформлением. Сначала решение задачи по существу и только потом дизайн. Очень важный элемент, дизайн, но только при получении правильного решения по существу.

Теперь посмотрите листы решения задачи «О производстве красок» (рис. 3.98).

Рис. 3.98. Имена рабочих листов в задаче о красках

• 1. Па листе Условия записаны условия задачи, что можно еще назвать вербальной постановкой задачи.
• 2. Лист Граф должен помочь формализовать задачу (см. рис. 3.87).
• 3. Далее идет лист исходных данных (ИД).
• 4. Лист ИД скопирован в лист Формулы. Здесь все смыслы ясны. Этот лист нужен в демонстрационных целях. Вы всегда имеете возможность показать все используемые в данной задаче формулы.
• 5. Лист ид скопирован в лист Решение. Именно здесь решается задача оптимизации.
• 6. При необходимости посмотреть на задачу с некоторых других точек зрения целесообразно скопировать лист Решение, например, в лист Эксперименты.

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

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

Образование лишним не бывает Разговорились с одним студентом. Он учится на 4-м курсе по специальности «Бухгалтерский учет, анализ и аудит». Учится и работает в консалтинговой фирме. А еще он очень здорово разбирается в компьютерах. Спрашиваю: «Если компьютеры, то почему Бухучет, а не Информационные технологии?» «А зачем? — отвечает он. Айтишники люто ненавидят бухгалтеров. Бухгалтеры люто ненавидят айтишников. Ненавидят, потому что нс понимают друг друга. А я понимаю и тех и других. Когда у них возникают проблемы, они идут ко мне. Так что у меня отличная позиция».

• [1] Задача из кн.: Таха X. А.

  Введение

  в исследование операций. М.: Вильямс, 2005.