Решение задач линейного программирования с помощью Excel

 

Ввод условий задачи

 

Ввод условий задачи состоит из следующих основных шагов:

1). Создание формы для ввода условий задачи.

2). Ввод исходных данных (коэффициентов математической модели).

3). Ввод целевой функции, ограничений и граничных условий.

Последовательность работ рассмотрим на примере задачи распределения ресурсов.

Фирма выпускает продукцию четырех типов Продукт1, Продукт2, Продукт3, Продукт4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье, финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Норма расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в табл., там же приведено наличие располагаемого ресурса. Требуется определить, в каком количестве надо выпускать продукцию каждого типа, чтобы суммарная прибыль была максимальной.

Ресурс	Продукт1	Продукт2	Продукт3	Продукт4	Наличие
Трудовые
Сырье
Финансы
Прибыль

Составим математическую модель, для чего введем следующие обозначения:

x_j- количество выпускаемой продукции j-го типа j=1,2,3,4;

b_i- количество располагаемого ресурса i-го вида i=1,2,3;

a_ij- норма расхода i-го ресурса для выпуска единицы продукции j-го типа;

c_j- прибыль, получаемая от реализации единицы продукции j-го типа.

Из табл. видно, что для выпуска единицы Продукта1 требуется 6 единиц сырья, значит, для выпуска всей продукции первого типа требуется 6x₁ единиц сырья, где x₁- количество выпускаемой продукции Продукт1. С учетом того, что для других видов продукции зависимости будут аналогичны, ограничение по сырью будет иметь вид:

6× x₁+5× x₂+4× x₃+3× x₄ £ 110.

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

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

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

60× x₁+70× x₂+120× x₃+130× x_4® max

Ограничения имеют вид:

x₁+x₂+x₃+x_4£ 16

6× x₁+5× x₂+4× x₃+3× x_4£ 110

4× x₁+6× x₂+10× x₃+13× x_4£ 100

x_j³ 0; j= .

Рис. 6

1). Форма ввода условий задачи представлена на рис. 6. Весь текст на рисунке (и в дальнейшем) является комментарием и на решение задачи не влияет.

2). Необходимые исходные данные приведены на рис. 7.

Рис. 7

3). Рассмотрим алгоритмы ввода уравнений целевой функции и ограничений:

· Установить курсор в ячейку, содержащую целевую функцию (F6).

• Щелкнуть мышью по кнопке -Мастер функций (на панели инструментов). На экране: диалоговое окно "Мастер функций шаг 1 из 2" (рис. 8).
• Выбрать категорию Мат. и тригонометрия
• Выбрать функцию СУММПРОИЗВ
• Щелкнуть по кнопке Шаг >. На экране: диалоговое окно "Мастер функций шаг 2 из 2" (рис. 9).
• В массив 1 ввести $B$3:$E$3.

Рис. 8

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

· В массив 2 ввести B6:E6.

• Щелкнуть по кнопке Закончить.

Рис. 9

В ячейке F6 отображается значение целевой функции, оно равно 0.

Ввод ограничений (в ячейки F9, F10, F11) осуществляется аналогичным образом, с заданием соответствующих адресов. Однако значительно проще можно выполнить данную процедуру используя мышь. Для этого подведите курсор мыши к ячейке с целевой функцией (F6), нажмите клавишу <Ctrl> (при этом рядом с изображением курсора мыши должен появиться знак "+"). Удерживая <Ctrl> перетащите содержимое ячейки F6 в ячейку F9. Содержимое F6 скопировано в F9. Ячейка F9 стала активной, об этом свидетельствует черная рамка вокруг нее, также называемая курсором. В правом нижнем углу курсора-рамки имеется маленький квадрат. Подведите курсор мыши к нему (курсор мыши превратится в черный крестик), "ухватите" мышью квадрат и тяните вниз до ячейки F11 включительно. Таким образом вы скопируете формулу из F9 в ячейки F10 и F11.

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

Рис. 10

Рис. 11

Все необходимые условия внесены в таблицу в виде формул. Следующим этапом будет поиск решения задачи средствами Excel.

 

2.2. Работа в диалоговом окне "Поиск решения"

 

1). Выберите последовательно опции меню Сервис, Поиск решения. На экране появится соответствующее окно (рис. 12).

Рис. 12

Поясним смысл элементов окна.

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

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

Предположить- отыскивает все неформульные ячейки, прямо или непрямо зависящие от формулы в окне Установить целевую ячейку, и помещает их ссылки в окно Изменяя ячейки.

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

Добавить- выводит окно диалога “Добавить ограничение”, в котором можно добавить ограничения к текущей проблеме.

Изменить- выводит окно диалога “Изменить ограничение”, в котором можно модифицировать имеющиеся ограничения.

Удалить- удалить выделенное ограничение.

Выполнить- запускает процесс решения определенной проблемы.

Закрыть- закрывает окно диалога, не решая проблемы. Сохраняются лишь изменения, сделанные при помощи кнопок Параметры, Добавить, Изменить и Удалить. Не сохраняются изменения, произведенные после использования данных кнопок.

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

Восстановить- очищает все текущие установки проблемы и возвращает все параметры к их значениям по умолчанию.

Курсор ввода с клавиатуры установлен в поле Установить целевую ячейку. Сюда необходимо внести адрес ячейки, содержащей целевую функцию. Для того чтобы сделать это щелкните мышью на той ячейке рабочего листа, где содержится ЦФ (F6). Вокруг F6 появился движущийся пунктирный контур, а в поле окна- соответствующий адрес. Следует отметить, что подобным способом можно вносить все остальные необходимые данные, это удобнее, чем вводить их с клавиатуры.

2). В поле Равной выберите флажок Максимальному значению.

3). Введите адреса искомых переменных, для этого выделите мышью область таблицы B3:E3.

4). Ввод ограничений задачи. Щелкните на кнопке Добавить. На экране появилось окно "Добавление ограничения" (рис. 13). Excel воспринимает ограничения в виде ссылок на ячейки в которых содержатся соответствующие формулы, при этом левая часть ограничения представляет собой, как правило, ссылку на формулу, а правая- значение: число или ссылку на ячейку, содержащую значение. Адреса ячеек должны содержать символ $. Если определяется интервал ячеек, то он должен быть той же формы и тех же размеров, что и интервал в окне Ссылка на ячейку. Некоторые из ограничений примера представлены на рис. 12.

Рис. 13

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

Ограничение- определяет условие, налагаемое на содержимое окна Ссылка на ячейку. Выберите из списка отношение, которое нужно установить между ячейкой или интервалом и ограничением, которое нужно ввести в окне справа от списка. Можно выбрать <=, =, >=, или "цел". Если Вы выбрали "цел" для указания на то. что переменная должна быть целочисленной, то слово "Целое" появляется в окне справа от списка.

Добавить- в окне диалога “Добавить ограничение” можно добавить новое ограничение без возврата в диалог “Параметры поиска решений”.

Если при вводе задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делается с помощью кнопок Изменить, Удалить (рис. 12). На этом ввод условий задачи закончен.

5). Установка параметров решения. Щелкните мышью по кнопке Параметры. На экране появится окно "Параметры поиска решения" (рис. 14).

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

Рис. 14

Поясним элементы окна.

Максимальное время- ограничивает время, требующееся для процесса отыскания решения. Это значение должно быть положительным целым числом. Значение по умолчанию равно 100 (секунд), что вполне годится для большинства малых задач, хотя Вы можете ввести любое значение до 32767.

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

Точность- контролирует точность ответов, получаемых при поиске решений. Число, вводимое в поле Точность:

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

• должно быть дробным числом от 0 до 1 (не включая концы).
• имеет значение по умолчанию равно 0,000001.

указывает на меньшую точность, если число введено с меньшим количеством десятичных знаков; например, 0,0001.

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

Допустимое отклонение- проблемы, связанные с изменяемыми ячейками, которые должны содержать целые значения, могут требовать большого количества времени, так как при этом необходимо решать несколько подпроблем, каждая из которых есть задача для Поиска Решений с целочисленными ограничениями. Можно подобрать величину отклонения, которая представляет процент допустимого отклонения от оптимального решения при целочисленных ограничениях для всех элементов задачи. Чем выше отклонение (допустимое отклонение в процентах), тем быстрее процесс решения. Установка отклонения не играет роли, если не введены целочисленные ограничения.

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

Показать результаты итераций- прерывает Поиск Решения и показывает результаты после каждой итерации.

Автоматический масштаб- включает автоматический масштаб. Это полезно, когда параметры ввода (Изменяя ячейки) и вывода (Установить целевую ячейку и Ограничения) сильно различаются по величине; например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.

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

· линейная- использует линейную экстраполяцию вдоль касательного вектора.

• квадратичная- использует квадратичную экстраполяцию; это дает лучшие результаты для нелинейных проблем.

Производная- параметры группы Производная определяют способ вычисления производной при оценке частных производных целевых и ограничивающих функций. Эти варианты существенно отличаются своим действием на функциях, чье графическое представление недостаточно гладко или непрерывно. Для таких функций следует использовать вариант Центральная.

· прямая- такой способ дифференцирования установлен по умолчанию.

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

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

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

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

Загрузить модель- выводит окно диалога "Загрузить Модель", в котором можно указать, какую именно модель нужно загрузить.

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

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

6). Нажмите OK, затем кнопку Выполнить в окне "Поиск решения". Через некоторое время на экране появится окно "Результаты поиска решения" (рис. 15).

Рис. 15

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

Когда Поиск Решения завершает попытки отыскания решения, то на экран в верху окна диалога "Результаты поиска решений" выводится сообщение о завершении.

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

Восстановить исходные значения- восстанавливает исходные значения в изменяемых ячейках.

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

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

· Результаты- перечисляет изменяемые ячейки и ячейку в окне Установить целевую ячейку вместе с исходным и конечным значением. Также показывает ограничения и информацию о них.

• Устойчивость- предоставляет информацию о том, насколько чувствительно решение к малым изменениям в формуле окна Установить целевую ячейку или ограничениях. Для нелинейных моделей, отчет предоставляет двойственные значения (нормированные градиенты и множители Лагранжа). Для линейных моделей отчет включает редуцированную стоимость, теневые цены, objective coefficient (с допустимыми отклонениями в обе стороны), и ограничения на изменение правой стороны равенства.
• Пределы- перечисляет изменяемые ячейки вместе с соответствующими значениями, ячейку в окне Установить целевую ячейку, верхние и нижние пределы и целевые значения. Нижний предел есть наименьшее значение, которое может находиться в изменяемой ячейке, если фиксировать остальные ячейки и удовлетворить все ограничения. Верхний предел есть наибольшее значение. Целевое значение есть значение ячейки в окне Установить целевую ячейку, когда значение изменяемой ячейки достигает наименьшего или наибольшего предела.

Результаты поиска появятся в таблице (рис. 16).

Рис. 16

На рис. 16 видно, что в оптимальном решении Продукт1=B3=10; Продукт2=C3=0; Продукт3=D3=6; Продукт4=E3=0. При этом максимальная прибыль будет составлять F6=1320, а количество использованных ресурсов равно: трудовых=F9=16, сырья=F10=84, финансов=F11=100.

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

Рис. 17

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

Рис. 18

 

Примеры решения оптимизационных задач средствами Excel

 

Получение требуемого сплава

 

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

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

Составляющие	Кол-во компонент составляющих в исходных материалах	Необходимое кол-во компонент в сплаве
	Сплав1	Сплав2	Сплав3
Свинец
Цинк
Олово
Цена единицы материала (руб.)

 

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

5× x₁+4× x₂+7× x_3® min,

Ограничения имеют вид:

40× x₁+30× x₂+25× x₃=30

40× x₁+60× x₂+45× x₃=55

20× x₁+10× x₂+30× x₃=15

x_j³ 0, j= .

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 19.

Поясним содержание некоторых ячеек таблицы.

В блоке ячеек В3:D3 находятся искомые значения x_j, которые до выполнения поиска решения были равны 0. Адрес данного блока входит в поле ввода Изменяя ячейки в окне “Поиск решения” (см. рис. 21). Ячейки блока выполняют роль переменных целевой функции и ограничений- x_j.

Рис. 19

Блок ячеек B4:D4 содержит правые части граничных неравенств (граничных условий). В ячейках блока содержатся нулевые значения (см. рис. 19).

Блок ячеек B6:D6 содержит данные о цене единицы исходных материалов, каждая его ячейка играет роль коэффициента при целевой функции в математической модели.

В блоках ячеек B10:D12 и G10:G12 находятся данные, соответствующие коэффициентам a_ij и b_i ограничений математической модели.

Рис. 20

Сами формулы целевой функции и ограничений расположены соответственно в ячейке E6 и ячейках E10, E11, E12 (см. рис. 19 и 20). Вид электронной таблицы в режиме отображения формул представлен на рис. 20.

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

Обычно в поле ввода Изменяя ячейки (см. рис. 21) заносятся адреса ячеек, которые выполняют роль переменных математической модели. Таким образом, под x₁, x₂, x₃ отводятся ячейки B3, C3, D3.

Ограничения удобно задавать поблочно. Первое ограничение данного примера (см. рис. 21) представляет собой запись граничных условий, в которой каждая ячейка левого блока больше либо равна каждой ячейке правого блока. Левый блок означает, как известно, совокупность переменных x_j, правый- множество нижних границ переменных. В данном примере нижней границей всех x_j является 0, поэтому можно было бы записать: $B$3:$D$3>=0. Вторая запись в группе Ограничения представляет три ограничения по содержанию требуемых компонентов в сплаве. В каждой ячейке левого блока содержится формула одного из ограничений (см. рис. 20), ячейки правого блока содержат требования b_i. По-прежнему, знак “>=“ относится каждой ячейке обоих блоков.

Рис. 21

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

Результаты поиска решения заносятся в ячейки таблицы (см. рис. 19). Прежде всего это значения x_j. Для получения требуемого сплава нужно 0,44 единицы сплава1 и 0,63 единиц сплава2. Стоимость нового сплава равна 46,88 д. е., количество компонент свинца, цинка и олова равно соответственно 36,25; 55; 15 компонент.

 

Транспортная задача

 

Три поставщика одного и того же продукта располагают в планируемый период следующими запасами этого продукта: первый- 120 условных единиц, второй- 100 и третий 80 единиц. Этот продукт должен быть перевезен к трем потребителям, спросы которых соответственно равны 90, 90 и 120 условных единиц. Приведенная ниже таблица содержит показатели затрат, связанных с перевозкой продукта из i-го пункта отправления в j-й пункт потребления.

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

 

Поставщики	Потребители и их спрос	Запасы
	А	Б	В
I
II
III
Спрос

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

7× x₁₁+6× x₁₂+4× x₁₃+3× x₂₁+8× x₂₂+5× x₂₃+2× x₃₁+3× x₃₂+7× x_33® min,

Ограничения имеют вид:

x₁₁+x₁₂+x₁₃=120,

x₂₁+x₂₂+x₂₃=100,

x₃₁+x₃₂+x₃₃=80,

x₁₁+x₂₁+x₃₁=90,

x₁₂+x₂₂+x₃₂=90,

x₁₃+x₂₃+x₃₃=120,

x_ij³ 0, i, j= .

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 22

Искомые значения x_ij находятся в блоке ячеек B4:D6. Адрес данного блока входит в поле ввода Изменяя ячейки в окне “Поиск решения” (см. рис. 24). Требования к ограничениям по спросу и запасам представлены соответственно в ячейках B7:D7 и E4:E6. Коэффициенты ЦФ, означающие затраты на доставку расположены в блоке ячеек B12:D14.

Рис. 22

Формулы целевой функции и ограничений находятся соответственно в ячейке F8 и ячейках B8:D8 (ограничения по спросу), F4:F6 (ограничения по запасам) (см. рис. 22 и 23). Вид электронной таблицы в режиме отображения формул представлен на рис. 23.

Рис. 23

Первая запись в группе Ограничения (см. рис. 24) представляет ограничения по нижней границе x_ij. Вторая и третья записи выражают ограничения по уровню спроса и запасов соответственно.

Рис. 24

Результаты поиска решения представлены на рис. 22.