|
1. Цели и задачи ЛР.
Получить практические навыки работы с инструментом MS Excel Поиск решения для решения задач линейного и нелинейного программирования.
2. Теоретические сведения.
Назначение и возможности надстройки “Поиск решения”
Большая часть задач, с которыми приходится сталкиваться в научной и финансовой деятельности, не столь просты, как кажутся на первый взгляд. Зачастую значения искомых функций зависят от большого числа переменных, и при этом чаще всего требуется отыскать наилучшее, оптимальное решение для данной задачи (например, дающее максимальную прибыль или обеспечивающее минимальные затраты), удовлетворяющее при этом целому ряду дополнительных условий на значения используемых параметров. Для решения таких задач, требующих применения математического аппарата линейного и нелинейного программирования и методов исследования операций, используется имеющаяся в Excel надстройка “Поиск решения” (Add-in “Solver”).
Линейное программирование — это вид математического моделирования, который служит для поиска оптимального варианта распределения ограниченных ресурсов между конкурирующими работами.
Круг задач линейного программирования довольно широк. Ниже приведены лишь несколько классических примеров.
- Транспортная задача. Ее форма состоит в следующем: имеется несколько пунктов производства и пунктов потребления некоторого продукта. Для каждого из пунктов производства задан объем производства, а для каждого пункта потребления – объем потребления. Известна также стоимость перевозки единицы продукта из каждого пункта производства в каждый пункт потребления. Требуется составить план перевозок продукта, в котором все пункты потребления были бы обеспечены необходимыми продуктами, ни из какого пункта производства не вывозилось бы продуктов больше, чем там производится, а стоимость перевозки была бы минимальной.
- Задача о выборе портфеля ценных бумаг. Вкладчик хочет выбрать портфель ценных бумаг, при этом известны средние значения доходов от каждого вида ценных бумаг и ожидаемая дисперсия этих доходов. Требуется отыскать оптимальный портфель, обеспечивающий максимальный ожидаемый доход при минимальном рассеянии, и, следовательно, минимальном риске.
- Задача о назначениях. Имеется несколько должностей и соответствующее количество претендентов на эти должности. Назначение i-го претендента на j—ую должность связано с затратами С[i, j]. Требуется распределить претендентов на должности так, чтобы суммарные затраты были бы минимальными.
- Задача о выборе оптимальных производственных линий и производственных процессов. Примеры встречаются везде, где действуют ограничения на производственные мощности (например, на размер завода или на машинное время) и где принимаются решения о выпуске продукции при наличии ограничений на ресурсы.
- Задача о выборе оптимального меню. Имеется набор некоторых продуктов, обладающих некоторой калорийностью, а также известны количества белков, жиров и углеводов для каждого из этих продуктов и их стоимость. Требуется составить меню, удовлетворяющее требованиям калорийности и сбалансированности питательных продуктов и при этом минимизирующее суммарную стоимость.
- Задачи линейной алгебры. С помощью этих же методов можно решать различные системы линейных (и не только линейных) уравнений.
Задачи, для решения которых можно воспользоваться надстройкой “Поиск решения”, имеют ряд общих свойств.
- Существует единственная целевая ячейка, содержащая формулу, значение которой должно быть сделано максимальным, минимальным или равным какому-то конкретному значению. Эта формула может, например, служить для вычисления чистой прибыли или общих транспортных расходов.
- Формула в целевой ячейке содержит ссылки (прямые или косвенные) на ряд изменяемых ячеек (содержащих неизвестные, или переменные решаемой задачи). Поиск решения заключается в том, чтобы подобрать такие значения этих переменных, которые бы давали оптимальные значения для формулы в целевой ячейке. Изменяемые ячейки могут содержать, например, себестоимость или цену товаров, транспортные тарифы или налоговые ставки.
- Кроме того, может быть задано некоторое количество ограничений – условий или соотношений, которым должны удовлетворять некоторые из изменяемых ячеек. Например, можно потребовать, чтобы общие затраты не превосходили 100 тыс. руб. или чтобы затраты на рекламную кампанию составляли от 10 % до 15 % от общих расходов.
Использование надстройки “Поиск решения”
Постановка задачи и оптимизация модели с помощью процедуры поиска решения
- В меню Сервис выберите команду Поиск решения.
- Если команда Поиск решения отсутствует в меню Сервис, установите соответствующую надстройку.
- В поле Установить целевую ячейку введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.
- Чтобы максимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение максимальному значению.
Чтобы минимизировать значение целевой ячейки путем изменения значений влияющих ячеек, установите переключатель в положение минимальному значению.
Чтобы установить значение в целевой ячейке равным некоторому числу путем изменения значений влияющих ячеек, установите переключатель в положение значению и введите в соответствующее поле требуемое число.
- В поле Изменяя ячейки введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.
- Чтобы автоматически найти все ячейки, влияющие на формулу модели, нажмите кнопку Предположить.
- В поле Ограничения введите все ограничения, накладываемые на поиск решения.
- Нажмите кнопку Выполнить.
- Чтобы сохранить найденное решение, установите переключатель в диалоговом окне Результаты поиска решения в положение Сохранить найденное решение.
Чтобы восстановить исходные данные, установите переключатель в положение Восстановить исходные значения.
Совет. Чтобы прервать поиск решения, нажмите клавишу ESC. Microsoft Excel пересчитает лист с учетом найденных значений влияющих ячеек.
Вызов надстройки “Поиск решения”
Чтобы запустить поиск решения в меню Сервис выберите команду Поиск решения.
| !!! Вызовите диалог «Поиск решения» и ознакомьтесь с его составляющими |
Диалоговое окно “Поиск решения”
| Установить целевую ячейку |
Служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу. |
| Равной |
Служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить число, введите его в поле. |
| Изменяя ячейки |
Служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле «Установить целевую ячейку». |
| Предположить |
Используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки. |
| Ограничения |
Служит для отображения списка граничных условий поставленной задачи. |
| Добавить |
Служит для отображения диалогового окна «Добавить» ограничение. |
| Изменить |
Служит для отображения диалоговое окна «Изменить» ограничение. |
| Удалить |
Служит для снятия указанного ограничения. |
| Выполнить |
Служит для запуска поиска решения поставленной задачи. |
| Закрыть |
Служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить, Изменить или Удалить. |
| Параметры |
Служит для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения. |
| Восстановить |
Служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используемых по умолчанию. |
Диалоговое окно Параметры поиска решения
В Microsoft Excel можно изменять условия и варианты поиска решения для линейных и нелинейных задач, а также загружать и сохранять оптимизируемые модели. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач.
Вызовите диалоговое окно Параметры поиска решений
| !!! Вызовите диалоговое окно Параметры поиска решений |
| Максимальное время |
Служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач. |
| Итерации |
Служит для управления временем решения задачи, путем ограничения числа промежуточных вычислений. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач. |
| Точность |
Служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 (нуля) до 1. Низкая точность соответствует введенному числу, содержащему меньшее количество десятичных знаков, чем число, используемое по умолчанию — например, 0,0001. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации. |
| Допустимое отклонение |
Служит для задания допуска на отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел. При указании большего допуска поиск решения заканчивается быстрее. |
| Сходимость |
Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков ѕ например, 0,0001 — это меньшее относительное изменение, чем 0,01. Лучшая сходимость требует больше времени на поиск оптимального решения. |
| Линейная модель |
Служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи. |
| Показывать результаты итераций |
Служит для приостановки поиска решения для просмотра результатов отдельных итераций. |
| Автоматическое масштабирование |
Служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине — например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей. |
| Значения не отрицательны |
Позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение. |
| Оценка |
Служит для указания метода экстраполяции — линейная или квадратичная — используемого для получения исходных оценок значений переменных в каждом одномерном поиске. |
| Линейная |
Служит для использования линейной экстраполяции вдоль касательного вектора. |
| Квадратичная |
Служит для использования квадратичной экстраполяции, которая дает лучшие результаты при решении нелинейных задач. |
| Производные |
Служит для указания метода численного дифференцирования — прямые или центральные производные — который используется для вычисления частных производных целевых и ограничивающих функций. |
| Прямые |
Используется для гладких непрерывных функций. |
| Центральные |
Используется для функций, имеющих разрывную производную. Не смотря на то, что данный способ требует больше вычислений, он может помочь при получении итогового сообщения о том, что процедура поиска решения не может улучшить текущий набор влияющих ячеек. |
| Метод |
Служит для выбора алгоритма оптимизации ѕ метод Ньютона или сопряженных градиентов ѕ для указания направление поиска. |
| Ньютона |
Служит для реализации квазиньютоновского метода, в котором запрашивается больше памяти, но выполняется меньше итераций, чем в методе сопряженных градиентов. |
| Сопряженных градиентов |
Служит для реализации метода сопряженных градиентов, в котором запрашивается меньше памяти, но выполняется больше итераций, чем в методе Ньютона. Данный метод следует использовать, если задача достаточно велика и необходимо экономить память, а также если итерации дают слишком малое отличие в последовательных приближениях. |
| Загрузить модель |
Служит для отображения на экране диалогового окна Загрузить модель, в котором можно задать ссылку на область ячеек, содержащих загружаемую модель. |
| Сохранить модель |
Служит для отображения на экране диалогового окна Сохранить модель, в котором можно задать ссылку на область ячеек, предназначенную для хранения модели оптимизации. Данный вариант предусмотрен для хранения на листе более одной модели оптимизации — первая модель сохраняется автоматически. |
Граничные условия
Ограничения на значения изменяемых ячеек, конечных ячеек или других ячеек, прямо или косвенно связанных друг с другом. Для линейных задач ограничений на количество граничных условий не налагается. Для нелинейных задач, каждая изменяемая ячейка может иметь следующие граничные условия: логическое ограничение; целочисленное ограничение плюс верхний, нижний или оба предела; кроме того, верхний или нижний предел может быть определен для 100 ячеек.
При задании граничных условий можно использовать следующие операторы.
| <= |
меньше или равно |
| >= |
больше или равно |
| = |
равно |
| int |
целое число (применимо только к изменяемым ячейкам) |
| bin |
двоичное(применимо только к изменяемым ячейкам) |
Наложение ограничений на поиск решения
- В меню Сервис выберите команду Поиск решения
- Нажмите кнопку Добавить.
- В поле Ссылка на ячейку введите адрес или имя ячейки, на значение которой накладываются ограничения.
- Выберите из раскрывающегося списка условный оператор, который необходимо разместить между ссылкой и ограничением.
- В поле Ограничения введите число, формулу или имя ячейки.
- Чтобы наложить условие на поиск решения задачи и приступить к набору нового условия, нажмите кнопку Добавить.
- Чтобы наложить условие и вернуться в диалоговое окно Поиск Решения, нажмите кнопку OK.
Добавление ограничения
Нажмите на кнопку, чтобы, не возвращаясь в окно диалога Параметры поиска решения, наложить новое условие на поиск решения задачи.
Ссылка на ячейку
Служит для указания ячейки или диапазона, на значения которых необходимо наложить ограничение.
Ограничение
Служит для задания условия, которое накладывается на значения ячейки или диапазона, указанного в поле Ссылка на ячейку. Выберите необходимый условный оператор и введите ограничение – число, формулу, ссылку на ячейку или диапазон ѕ в поле справа от раскрывающегося списка.
Примечания
- Условные операторы целого и двоичного типа можно применять только при наложении ограничений на изменяемые ячейки.
- Флажок Линейная модель в диалоговом окне Параметры поиска решения позволяет задать любое количество ограничений. При решении нелинейных задач на значения изменяемых ячеек можно наложить двоичное или целое ограничение с верхней, нижней или обеими границами. Верхнюю, нижнюю или обе границы допустимо наложить 100 других ячеек.
| !!! Добавьте несколько новых ограничений в текущую задачу |
Изменение и удаление ограничения на поиск решения
- В меню Сервис выберите команду Поиск решения.
- В списке Ограничения укажите строку, которую следует изменить или удалить.
- Чтобы удалить ограничение, нажмите кнопку Удалить.
- Чтобы изменить ограничение, нажмите кнопку Изменить, а затем внесите нужные изменения.
Изменение погрешности и сходимость результатов поиска решения
- В меню Сервис выберите команду Поиск решения.
- Нажмите кнопку Параметры.
- В поле Точность введите необходимую погрешность — чем меньше введенное число, тем выше точность результатов.
- В поле Сходимость введите значение относительного изменения, при достижении которого в последних пяти итерациях поиск решения прекращается — чем меньше это значение, тем выше точность результатов.
| !!! Измените параметры поиска решения и ознакомьтесь с результатом |
Изменение погрешности целых величин, полученных в результате поиска решения
- В меню Сервис выберите команду Поиск решения.
- Нажмите кнопку Параметры.
- В поле Допустимое отклонение введите необходимый допуск.
Изменение числа итераций или относительной погрешности
Итерация – повторяющиеся вычисления, производимые до тех пор, пока не будет выполнено указанное условие.
Если в вычислениях используются итерации, лист пересчитывается столько раз, какое значение указано в поле Предельное число итераций, или когда все величины модели изменятся за одну итерацию на число, меньшее указанного в поле Относительная погрешность.
- Выберите команду Параметры в меню Сервис, а затем — вкладку Вычисления.
- Установите флажок Итерации.
- Введите количество итераций, выполняемых при обработке формул в поле Предельное число итераций.
- Чем больше предельное число итераций, тем больше времени потребуется Microsoft Excel для пересчета листа.
- Введите относительную погрешность вычислений в поле Относительная погрешность. Чем меньше погрешность, тем больше время пересчета листа и точнее результаты обработки формул.
Ограничение времени поиска решения и числа итераций
- В меню Сервис выберите команду Поиск решения.
- Нажмите кнопку Параметры.
- В поле Максимальное время введите интервал в секундах, чтобы ограничить время поиска решения задачи.
- В поле Итерации введите максимальное количество итераций, отводимое на достижение конечного результата.
Примечания. При достижении границы отведенного временного интервала или при выполнении отведенного числа итераций, на экране появляется диалоговое окно Текущее состояние поиска решения.
| !!! Измените время поиска решения и число итерация и запустите расчет задачи снова. |
Итоговые сообщения процедуры поиска решения
Если поиск решения успешно завершен, в диалоговом окне Результаты поиска решения выводится одно из следующих сообщений.
- Решение найдено. Все ограничения и условия оптимальности выполнены.
Все ограничения соблюдены с установленной точностью и найдено заданное значение целевой ячейки.
- Поиск свелся к текущему решению. Все ограничения выполнены.
Относительное изменение значения в целевой ячейке за последние пять итераций стало меньше установленного значения параметра Сходимость в диалоговом окне Параметры поиска решения. Чтобы найти более точное решение, установите меньшее значение параметра Сходимость, но это займет больше времени.
Если поиск не может найти оптимальное решение, в диалоговом окне Результаты поиска решения выводится одно из следующих сообщений.
- Поиск не может улучшить текущее решение. Все ограничения выполнены.
В процессе поиска решения нельзя найти такой набор значений влияющих ячеек, который был бы лучше текущего решения. Приблизительное решение найдено, но либо дальнейшее уточнение невозможно, либо заданная погрешность слишком высока. Измените погрешность на меньшее число и запустите процедуру поиска решения снова.
- Поиск остановлен (истекло заданное на поиск время). Время, отпущенное на решение задачи, исчерпано, но достичь удовлетворительного решения не удалось. Чтобы при следующем запуске процедуры поиска решения не повторять выполненные вычисления, установите переключатель Сохранить найденное решение или Сохранить сценарий.
- Поиск остановлен (достигнуто максимальное число итераций). Произведено разрешенное число итераций, но достичь удовлетворительного решения не удалось. Увеличение числа итераций может помочь, однако следует рассмотреть результаты, чтобы понять причины остановки. Чтобы при следующем запуске процедуры поиска решения не повторять выполненные вычисления, установите переключатель Сохранить найденное решение или нажмите кнопку Сохранить сценарий.
- Значения целевой ячейки не сходятся. Значение целевой ячейки неограниченно увеличивается (или уменьшается), даже если все ограничения соблюдены. Возможно следует в задаче снять одно ограничение или сразу несколько. Изучите процесс расхождения решения, проверьте ограничения и запустите задачу снова.
- Поиск не может найти подходящего решения. В процессе поиска решения нельзя сделать итерацию, которая удовлетворяла бы всем ограничениям при заданной точности. Вероятно, ограничения противоречивы. Исследуйте лист на предмет возможных ошибок в формулах ограничений или в выборе ограничений.
- Поиск остановлен по требованию пользователя. Нажата кнопка Стоп в диалоговом окне Текущее состояние поиска решения после прерывания поиска решения в процессе выполнения итераций.
- Условия для линейной модели не удовлетворяются. Установлен флажок Линейная модель, однако итоговый пересчет порождает такие значения, которые не согласуются с линейной моделью. Это означает, что решение недействительно для данных формул листа. Чтобы проверить линейность задачи, установите флажок Автоматическое масштабирование и повторно запустите задачу. Если это сообщение опять появится на экране, снимите флажок Линейная модель и снова запустите задачу.
- При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения. При пересчете значений ячеек обнаружена ошибка в одной формуле или в нескольких сразу. Найдите целевую ячейку или ячейку ограничения, порождающие ошибку, и измените их формулы так, чтобы они возвращали подходящее числовое значение.
Набрано неверное имя или формула в окне Добавить ограничение или окне Изменить ограничение или в поле Ограничение были заданы целое или двоичное ограничение. Чтобы ограничить значения ячейки множеством целых чисел, выберите оператор целого ограничения в списке условных операторов. Чтобы установить двоичное ограничение, выберите оператор для двоичного ограничения.
- Мало памяти для решения задачи. Система не смогла выделить память, необходимую для поиска решения. Закройте некоторые файлы или приложения, и попытайтесь снова выполнить процедуру поиска решения.
- Другой экземпляр Excel использует SOLVER.DLL. Запущено несколько копий Microsoft Excel, в одном из которых используется файл Solver.dll.
- Оптимальное решение не найдено.
Поиск решения может остановиться до достижения оптимального решения по следующим причинам:
- Пользователь прервал процесс поиска.
- Команда Показывать результаты итераций в диалоговом окне Параметры поиска решения выбрана перед Выполнить.
- Пользователь нажал кнопку Стоп в режиме пошагового выполнения итераций, по истечении времени, отведенного на работу процедуры, или после выполнения заданного числа итераций.
- Установлен флажок Линейная модель в диалоговом окне Параметры поиска решения, в то время как решаемая задача не линейна.
- Значение, заданное в поле Установить диалогового окна Поиск решения, неограниченно увеличивается или уменьшается.
- Необходимо изменить значения полей Максимальное время или Итерации в диалоговом окне Параметры поиска решения.
- В случае задач, значения в которых ограничены множеством целых чисел, необходимо уменьшить значение в поле Допустимое отклонение диалогового окна Параметры поиска решения, что позволит найти лучшее решение.
- В случае нелинейных задач необходимо уменьшить значение в поле Сходимость диалогового окна Параметры поиска решения, что позволит продолжать поиск решения, когда значение в целевой ячейке изменяется медленно.
- Необходимо установить флажок Автоматическое масштабирование в диалоговом окне Параметры поиска решения, если значения влияющих ячеек или значения влияющей и целевой ячеек различаются на несколько порядков.
После остановки на экране отображается диалоговое окно Результаты поиска решения. Установите переключатель в положение Сохранить найденное решение или Восстановить исходные значения, внесите нужные изменения и запустите процедуру поиска решения снова.
Диалоговое окно “Результаты поиска решения”
Используется для вывода итогового сообщения и найденного решения. Чтобы получить дополнительные сведения об итоговых сообщениях процедуры поиска решения, нажмите кнопку «Справка».
| Сохранить найденное решение |
Служит для сохранения найденного решения во влияющих ячейках модели. |
| Восстановить исходные значения |
Служит для восстановления исходных значений влияющих ячеек модели. |
| Тип отчета |
Служит для указания типа отчета, размещаемого на отдельном листе книги. |
| Результаты |
Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях. |
| Устойчивость |
Используется для создания отчета, содержащего сведения о чувствительности решения к малым изменениям в формуле модели или в формулах ограничений. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. В случае нелинейных моделей отчет содержит данные для градиентов и множителей Лагранжа. В отчет по нелинейным моделям включаются ограниченные затраты, фиктивные цены, объективный коэффициент (с некоторым допуском), а также диапазоны ограничений справа. |
| Пределы |
Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно верхним пределом называется наибольшее значение. |
| Сохранить сценарий |
Служит для отображения диалогового окна Сохранение сценария, в котором можно сохранить сценарий решения задачи, чтобы использовать его в дальнейшем с помощью диспетчера сценариев Microsoft Excel. |
Диалоговое окно “Сохранить сценарий”
Сохранить сценарий
Служит для отображения на экране диалогового окна Сохранить сценарий, в котором можно выполнить сохранение сценария решения задачи, чтобы использовать его в дальнейшем с помощью диспетчера сценариев Microsoft Excel. Если сценарий не определен, диспетчер сценариев использует ссылку, указанную в поле Изменяя ячейки диалогового окна Поиск решения.
В поле Название сценария диалогового окна Сохранение сценария введите имя сценария, который следует сохранить и нажмите кнопку OK.
Продолжить
Служит для запуска следующей итерации.
Стоп
Служит для остановки поиска решения и отображения на экране диалогового окна Результаты поиска решения.
| !!! Сохраните сценарий полученного решения под именем «Сценарий1» |
В составе Microsoft Excel в папке Examples\Solver находится книга с примерами (Solvsamp.xls) использования процедуры поиска решения. Чтобы применить любой из шести примеров — “Структура производства”, “Транспортная задача”, “График занятости”, “Управление капиталом”, “Портфель ценных бумаг” и “Проектирование цепи” — откройте книгу, перейдите к нужному листу и выберите Поиск решения в меню Сервис. В примерах уже подобраны целевая и влияющие ячейки, а также ограничения.
ПРОСТЕЙШАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАМИРОВАНИЯ
Рассмотрим решение задачи линейного программирования на следующем примере:
Целевая функция:
Z 4x1+6x2->min
Ограничения:
|
|
3x1 + x2 ≥ 9
x1 + 2x2 ≥ 8
x1 + 6x2 ≥12
x1 ≥ 0, x2 ≥ 0 |
Подготовка рабочей таблицы на листе Excel
Для решения задачи необходимо подготовить исходную таблицу на рабочем листе Microsoft Excel. Для этого
| !!! создайте новую книгу MS Excel
«Линейное программирование <ФИО студента> » |
Переименуйте лист 1, на котором Вы будете работать, для этого щелкните по нему правой кнопкой мыши и в открывшемся меню выберете Переименовать. Введите с клавиатуры название «Простейшая задача линейного программирования».Подготовьте на листе 1 MS Excelрабочую таблицу. Она должна выглядеть так:
В данном случае ячейки B8 и B9 пусты, так как в них Excel позже разместит оптимальное базовое решение.
| !!! В ячейки E8:E12 занесите формулы, соответствующие ограничениям линейной модели |
Эти формулы будут выглядеть так:
| Ячейка |
Формула |
| E8 |
=3*B8+B9 |
| E9 |
=B8+2*B9 |
| E10 |
=B8+6*B9 |
| E11 |
=B8 |
| E12 |
=B9 |
| !!! В ячейку H8 занесите формулу, соответствующую целевой функции, т.е.: =4*B8+6*B9 |
Работа с инструментом Поиск решения
Теперь, чтобы решить задачу линейного программирования нужно воспользоваться инструментом Поиск решения.
| !!! Откройте окно поиска решения: Сервис/ Поиск решения и установите в нем целевую ячейку, укажите изменяемые ячейки и внесите ограничения. |
В данном случае целевой ячейкой является H8, она стремится к минимальному значению. Изменяемые ячейки: B8 и B9.
Добавьте ограничения. Для этого нажмите кнопку Добавить. Ограничения добавляются в соответствии с исходной линейной моделью. Так как формулы ограничений были записаны в ячейки Е8:Е12, значит, они будут иметь вид.
| Ячейка |
знак |
Ограничение |
| E8 |
>= |
9 |
| E9 |
>= |
8 |
| E10 |
>= |
12 |
| E11 |
>= |
0 |
| E12 |
>= |
0 |
Всего ограничений будет пять, как и в исходной линейной модели.
| !!! Нажмите кнопку Выполнить, чтобы получить решение задачи |
MS Excel предложит сохранить найденное решение в таблице и создать отчет.
Выберите Тип отчета «Результаты». Таблица с решениями должна выглядеть следующим образом. Если ваши результаты не соответствуют приведенному решению – проверьте правильность ограничений и установленную целевую ячейку.
ТРАНСПОРТНАЯ ЗАДАЧА
В простейшей постановке транспортная задача представляет собой определение минимальных затрат на перевозку некоторой однородной продукции из пунктов отправления (от поставщиков или производителей) в пункты назначения (потребителям).
Данная задача решает проблему доставки товаров с трех заводов на пять региональных складов. Считается, что товары могут доставляться с любого завода на любой склад. Очевидно, что стоимость доставки на большее расстояние будет большей. Требуется определить объемы перевозок между каждым заводом и складом, в соответствии с производственными потребностями складов и заводов, при которых транспортные расходы будут минимальными.
В обычном виде данные задачи представлены в таблице.
| Потребители Поставщики |
Казань |
Рига |
Воронеж |
Курск |
Москва |
Запасы |
| Белоруссия |
4
|
2
|
3
|
1
|
2
|
100
|
| Украина |
6
|
5
|
3
|
4
|
3
|
125
|
| Литва |
6
|
4
|
5
|
2
|
3
|
75
|
| Потребность |
55
|
65
|
50
|
75
|
55
|
375
|
| !!! В ранеесозданной книге создайте новый листи назовите его
«Транспортная задача». |
Структура транспортной задачи на листе MS Excel будет следующей.
Для того, чтобы сформировать такую таблицу выполните следующие действия:
| !!! 1. В строку» Потребности» (ячейки С14:G14) занесите сведения из исходных данных о потребностях потребителей. |
| !!! 2. В столбец «Поставки» (ячейки В16:В18) занесите сведения о запасах поставщика из исходных данных. |
| !!! 3.В ячейки С16С18:G16G18 занесите сведения из исходных данных о затратах на перевозку от i-го завода к j-му складу. |
Далее для формирования ограничений необходимо ввести ряд формул. Для этого, формально примем, что число перевозок от i-го завода к j-ve складу равно 1, так как эти данные в задачи являются изменяемыми. Поэтому:
| !!! Внесите в ячейки С8С10:G8G10 значение 1 |
| !!! В ячейку В8 внесите формулу =СУММ(C8:G8). |
Затем наведите курсор мыши в нижний правый угол этой ячейки и, после появления значка + , растяните рабочую область ячейки на столбец В8:В10.
| !!! В ячейку С12 внесите формулу =СУММ(C8:С10). |
Затем наведите курсор мыши в нижний правый угол этой ячейки и, после появления значка + , растяните рабочую область ячейки на строку C8:G8.
| !!! В ячейку С20 внесите формулу =C8*C16+C9*C17+C10*C18 |
Затем наведите курсор мыши в нижний правый угол этой ячейки и, после появления значка +, растяните рабочую область ячейки на строку C20:G20.
И последняя формула сформирует целевую ячейку. Для ее создания:
| !!! В ячейку С20 внесите формулу =СУММ(C20:G20) |
Затем в окне поиск решения Сервис/Поиск решения установите целевую ячейку В20, которая стремится к минимальному значению. Укажите изменяемые величины (ими будут ячейки C8:G10) и внесите ограничения, приведенные в следующей таблице.
| Ячейка |
знак |
Ограничение |
| В8:В10 |
<= |
В16:В18 |
| C12:G12 |
>= |
C14:G14 |
| C8:G10 |
>= |
0 |
| !!! Нажмите кнопку Выполнить, чтобы получить результаты задачи |
Результаты поиска решений можно просмотреть после появления окна Результаты поиска решения. Если все ячейки содержат числовые данные, целевая ячейка не равна 0 и нет сообщений об ошибке, то задача решена . В этом случае выберете команду Сохранить найденное решение. Если решение сохранено, но оно не удовлетворяет каким-либо требованиям, вернуть исходные данные можно заменив значения в ячейках С8С10:G8G10 на 1.
Ваш результат должен иметь приведенный здесь вид. Если ваши результаты не соответствуют решению – проверьте правильность ограничений и установленную целевую ячейку.
3.3 СТРУКТУРА ПРОИЗВОДСТВА С УМЕНЬШЕНИЕМ НОРМЫ ПРИБЫЛИ
Предположим, что предприятие выпускает телевизоры, стерео- и акустические системы, используя один склад комплектующих. В связи с ограниченностью запаса необходимо найти оптимальное соотношение объема выпуска изделий.
Эта модель включает данные по нескольким изделиям, в которых использованы общие комплектующие. Каждому изделию соответствует своя норма прибыли. Запас комплектующих ограничен, и задача состоит в определении каждого вида изделий для получения наибольшей прибыли.
Данные задачи представлены в таблице:
| Наименование |
Телевизор
|
Стерео
|
Ак .сист.
|
| |
|
Количество->
|
100
|
100
|
100
|
| Наим. изд. |
Склад
|
Использ.
|
|
|
|
| Шасси |
450 |
200
|
1
|
1
|
0
|
| Кинескоп |
250 |
100
|
1
|
0
|
0
|
| Динамик |
800 |
500
|
2
|
2
|
1
|
| Блок пит. |
450 |
200
|
1
|
1
|
0
|
| Элек. плата |
600 |
400
|
2
|
1
|
1
|
| Прибыль по видам изделий, т. руб |
4 732р.
|
3 155р.
|
2 208р.
|
| Прибыль всего: |
10 095р
|
| !!! В ранеесозданной книге создайте новый лист Вставка/Новый лист и назовите его «Структура производства». |
Данные задачи занесите на лист Excel в следующем виде:
| !! Перенесите данные из таблицы на лист MS Excel без изменений |
Ниже приведенные строки будет содержать формулы.
| !!! Занесите следующие формулы в строку формул fx соответствующей ячейки или непосредственно в саму ячейку. |
|
Ячейка
|
Формула
|
| D17 |
= 75*МАКС(D9;0)^$H$15 |
| E17 |
=50*МАКС(E9;0)^$H$15 |
| F17 |
= 35*МАКС(F9;0)^$H$15 |
| D18 |
= СУММ(D17:F17) |
| С11 |
=$D$9*D11+$E$9*E11+$F$9*F11 |
| С12 |
=$D$9*D12+$E$9*E12+$F$9*F12 |
| С13 |
=$D$9*D13+$E$9*E13+$F$9*F13 |
| С14 |
=$D$9*D14+$E$9*E14+$F$9*F14 |
| С15 |
=$D$9*D15+$E$9*E15+$F$9*F15 |
Используйте инструмент Поиск решения . В нашем случае окно поиска решения должно иметь вид:
| !!! Нажмите кнопку Выполнить для получения решения задачи |
Ваш результат должен выглядеть следующим образом. Если Ваши результаты не соответствуют представленному решению – проверьте правильность ограничений и установленную целевую ячейку.
В формулу прибыли на изделие в ячейках D17:F17 входит коэффициент ^H15, учитывающий уменьшение прибыли с ростом объема. В H15 содержится 0,9, что делает задачу нелинейной. Изменение H15 на 1,0 (если прибыль не зависит от объема производства) и повторный запуск процесса поиска решения даст другое решение, отличное от оптимального решения, найденного ранее. Данное изменение делает задачу линейной.
3.Оборудование для лабораторной работы.
Персональный IBM PC — совместимый компьютер, подключенный в одноранговую локальную вычислительную сеть под управлением Windows XP.
4. Порядок выполнения работы.
- Прочитать п.2 настоящего руководства и выполнить предписанные в нем действия.
- Закрепить полученные знания, ответив на вопросы для самотестирования.
|
