Решение задачи линейного программирования в Excel. Задачи линейного программирования, решение средствами MS Excel

Рассмотрим пример задачи линейного программирования.

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

Рисунок 1.

Математическая модель задачи имеет вид:

где x j – количество выпускаемой продукции j-го типа; F – функция цели; в левых частях выражений ограничений указаны величины потребного ресурса , а правые части показывают количество имеющегося ресурса .

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

Для решения задачи с помощью Excel следует создать форму для ввода исходных данных и ввести их. Форма ввода показана на рис. 2.

В ячейку F6 введено выражение целевой функции как суммы произведений значений прибыли от выпуска единицы продукции каждого типа на количество выпускаемой продукции соответствующего типа. Для наглядности на рис. 3 представлена форма ввода исходных данных в режиме вывода формул.

В ячейки F8:F10 введены левые части ограничений для ресурсов каждого вида.

Рисунок 2.

Рисунок 3.

Решение задачи линейного программирования

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

Рисунок 4.

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

1 Назначить целевую функцию, для чего установить курсор в поле Установить целевую ячейку окна Поиск решения и щелкнуть в ячейке F6 в форме ввода;

2 Включить переключатель значения целевой функции, т.е. указать ее Равной Максимальному значению ;

3 Ввести адреса изменяемых переменных (x j): для этого установить курсор в поле Изменяя ячейки окна Поиск решения, а затем выделить диапазон ячеек B3:E3 в форме ввода;

4 Нажать кнопку Добавить окна Поиск решения для ввода ограничений задачи линейного программирования; на экран выводится окно Добавление ограничения (рис. 5) :

Ввести граничные условия для переменных x j (x j ³0), для этого в поле Ссылка на ячейку указать ячейку В3, соответствующую х 1 , выбрать из списка нужный знак (³), в поле Ограничение указать ячейку формы ввода, в которой хранится соответствующее значение граничного условия, (ячейка В4), нажать кнопку Добавить ; повторить описанные действия для переменных х 2 , х 3 и х 4 ;

Ввести ограничения для каждого вида ресурса, для этого в поле Ссылка на ячейку окна Добавление ограничения указать ячейку F9 формы ввода, в которой содержится выражение левой части ограничения, наложенного на трудовые ресурсы, в полях Ограничение указать знак £ и адрес Н9 правой части ограничения, нажать кнопку Добавить ; аналогично ввести ограничения на остальные виды ресурсов;

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

Рисунок 5.

Решение задачи линейного программирования начинается с установки параметров поиска:

В окне Поиск решения нажать кнопку Параметры , на экран выводится окно Параметры поиска решения (рис. 6);

Установить флажок Линейная модель, что обеспечивает применение симплекс-метода;

Указать предельное число итераций (по умолчанию – 100, что подходит для решения большинства задач);

Установить флажок , если необходимо просмотреть все этапы поиска оптимального решения;

Нажать ОК , возврат в окно Поиск решения .

Рисунок 6.

Для решения задачи нажать кнопку Выполнить в окне Поиск решения , на экране – окно Результаты поиска решения (рис. 7), в котором содержится сообщение Решение найдено. Все ограничения и условия оптимальности выполнены. Если условия задачи несовместны, то выводится сообщение Поиск не может найти подходящего решения . Если целевая функция не ограничена, то появляется сообщение Значения целевой ячейки не сходятся .

Рисунок 7.

Для рассматриваемого примера решение найдено и результат оптимального решения задачи выводится в форме ввода: значение целевой функции, соответствующее максимальной прибыли и равное 1320, указывается в ячейке F6 формы ввода, оптимальный план выпуска продукции х 1 =10, х 2 =0, х 3 =6, х 4 =0 указывается в ячейках В3:С3 формы ввода (рис. 8).

Количество использованных для выпуска продукции ресурсов выводится в ячейки F9:F11: трудовых – 16, сырья – 84, финансов – 100.

Рисунок 8.

Если при установке параметров в окне Параметры поиска решения (рис. 6) был установлен флажок Показывать результаты итераций , то будут показаны последовательно все шаги поиска. На экран будет выводиться окно (рис. 9). При этом текущие значения переменных и функции цели будут показаны в форме ввода. Так, результаты первой итерации поиска решения исходной задачи представлены в форме ввода на рисунке 10 .

Рисунок 9.

Рисунок 10.

Чтобы продолжить поиск решения, следует нажимать кнопку Продолжить в окне Текущее состояние поиска решения .

Анализ оптимального решения

Прежде чем, перейти к анализу результатов решения, представим исходную задачу в форме

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

Составим для исходной задачи двойственную задачу и введем дополнительные двойственные переменные v i .

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

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

Результаты,

Устойчивость,

Пределы.

Для вызова отчета в поле Тип отчета выделить название нужного типа и нажать ОК .

1 Отчет по результатам (рис. 11) состоит из трех таблиц:

Таблица 1 содержит сведения о целевой функции; в столбце Исходно указывается значение целевой функции до начала вычислений;

Таблица 2 содержит значения искомых переменных x j , полученных в результате решения задачи (оптимальный план выпуска продукции);

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

Для Ограничений в графе Формула приведены зависимости, которые были введены при задании ограничений в окне Поиск решения ; в графе Значение указаны величины использованного ресурса; в графе Разница показано количество неиспользованного ресурса. Если ресурс используется полностью, то в графе Состояние выводится сообщение связанное ; при неполном использовании ресурса в этой графе указывается не связан. Для Граничных условий приводятся аналогичные величины с той лишь разницей, что вместо неиспользованного ресурса показана разность между значением переменной x j в найденном оптимальном решении и заданным для нее граничным условием (x j ³0).

Именно в графе Разница можно увидеть значения дополнительных переменных y i исходной задачи в формулировке (2). Здесь у 1 =у 3 =0, т.е. величины неиспользованных трудовых и финансовых ресурсов равны нулю. Эти ресурсы используются полностью. Вместе с тем, величина неиспользованных ресурсов для сырья у 2 =26, значит, имеются излишки сырья.

Рисунок 11.

2 Отчет по устойчивости (рис. 12)состоит из двух таблиц.

В таблице 1 приводятся следующие значения:

Результат решения задачи (оптимальный план выпуска);

- Нормир. стоимость , т.е. величины, показывающие, насколько изменится целевая функция при принудительном включении единицы продукции соответствующего типа в оптимальный план;

Коэффициенты целевой функции;

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

В таблице 2 содержатся аналогичные данные для ограничений:

Величины использованных ресурсов;

- Теневая цена , показывающая, как изменится целевая функция при изменении величины соответствующего ресурса на единицу;

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

Рисунок 12.

Отчет по устойчивости позволяет позволяет получить двойственные оценки.

Как известно, двойственные переменные z i показывают, как изменится целевая функция при изменении ресурса i-го типа на единицу. В отчете Excel двойственная оценка называется Теневой ценой .

В нашем примере сырье не используется полностью и его ресурс у 2 =26. Очевидно, что увеличение количества сырья, например, до 111 не повлечет за собой увеличения целевой функции. Следовательно, для второго ограничения двойственная переменная z 2 =0. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет больше нуля, а двойственная оценка этого ограничения равна нулю.

В рассматриваемом примере трудовые ресурсы и финансы использовались полностью, поэтому их дополнительные переменные равны нулю (у 1 =у 3 =0). Если ресурс используется полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции, и следовательно, на величину целевой функции. Двойственные оценки ограничений на трудовые и финансовые ресурсы отличны от нуля, т.е. z 1 =20, z 3 =10.

Значения двойственных оценок находим в Отчете по устойчивости , в таблице 2, в графе Теневая цена .

При увеличении (уменьшении) трудовых ресурсов на единицу целевая функция увеличится (уменьшится) на 20 единиц и будет равна

F=1320+20×1=1340 (при увеличении).

Аналогично, при увеличении объема финансов на единицу целевая функция будет

F=1320+10×1=1330.

Здесь же, в графах Допустимое увеличение и Допустимое уменьшение таблицы 2, показаны допустимые пределы изменения количества ресурсов j-го вида. Например, для при изменении приращения величины трудовых ресурсов в пределах от –6 до 3,55, как показано в таблице, структура оптимального решения сохраняется, т.е наибольшую прибыль обеспечивает выпуск Прод1 и Прод3, но в других количествах.

Дополнительные двойственные переменные также отражены в Отчете по устойчивости в графе Нормир. стоимость таблицы 1.

Если основные переменные не вошли в оптимальное решение, т.е. равны нулю (в примере х 2 =х 4 =0), то соответствующие им дополнительные переменные имеют положительные значения (v 2 =10, v 4 =20). Если же основные переменные вошли в оптимальное решение (х 1 =10, х 3 =6), то их дополнительные двойственные переменные равны нулю (v 1 =0, v 3 =0).

Эти величины показывают, насколько уменьшится (поэтому знак минус в значениях переменных v 2 и v 4) целевая функция при принудительном выпуске единицы данной продукции. Следовательно, если мы захотим принудительно выпустить единицу продукции вида Прод3, то целевая функция уменьшится на 10 единиц и будет равна 1320 -10×1 =1310.

Обозначим через Dс j изменение коэффициентов целевой функции в исходной модели (1). Эти коэффициенты определяют прибыль, получаемую при реализации единицы продукции j-го вида.

В графах Допустимое увеличение и Допустимое Уменьшение таблицы 1 Отчета по устойчивости показаны пределы изменения Dс j , при которых сохраняется структура оптимального плана, т.е. будет выгодно по-прежнему выпускать продукцию вида Продj. Например, при изменении Dс 1 в пределах -12£ Dс 1 £ 40, как показано в отчете, по-прежнему будет выгодно выпускать продукцию вида Прод1. При этом значение целевой функции будет F=1320+x 1 ×Dс j =1320+10×Dс j .

3 Отчет по пределам приведен на рис. 13. В нем показывается, в каких пределах могут изменяться значения x j , вошедшие в оптимальное решение, при сохранении структуры оптимального решения. Кроме этого, для каждого типа продукции приводятся значения целевой функции, получаемые при подстановке в оптимальное решение значения нижнего предела выпуска изделий соответствующего типа при неизменных значениях выпуска остальных типов. Например, если при оптимальном решении х 1 =10, х 2 =0, х 3 =6, х 4 =0 положить х 1 =0 (нижний предел) при неизменных х 2 , х 3 и х 4 , то значение целевой функции будет равно 60×0+70×0+120×6+130×0=720.

Нижегородский Государственный Технический Университет

Павловский филиал

Курсовая работа

по информатике на тему:

“Технология решения задач линейного программирования с помощью Поиска решений приложения Excel” .

Выполнила : Бородулина Д.А.

Группа 05-АМ.

Проверила : Ловыгина М.Б.

Павлово 2006 г.

Введение……………………………………………………………………………стр. 3

Решение задач с помощью надстройки Поиск решения

1. Установка программы Поиск решения…………………………………………..…стр.4
2. Диалоговое окно Поиск решения…………………………………………………..…стр.4
3. Ввод и редактирование ограничений………………………………………………..стр.5
4. Настройка параметров алгоритма и программы……………………………….стр.6

1. Сохранение модели оптимизации…………………………………………………....стр.9
2. Загрузка модели оптимизации……………………………………………………….стр.9

Вычисления и результаты решения задачи………………………………..стр. 10

Просмотр промежуточных результатов поиска решения…………...стр.11

Возникающие проблемы и сообщения процедуры поиска решения…...стр.12

Итоговые сообщения процедуры поиска решения……………………....стр.13

Примеры выполнения задач

1. Пример № 1………………………………………………………………………………стр.15
2. Пример № 2 (графическим способом)……………………………………………...стр..20

Вывод……………………………………………………………………………....стр.24

Список литературы…………………………………………………………....стр.25

Введение

Линейная оптимизация – это раздел математического программирования, посвящённый нахождению экстремума линейных функций нескольких переменных при дополнительных линейных ограничениях, которые налагаются на переменные. Методы, с помощью которых решаются задачи, подразделяются на универсальные (например, симплексный метод) и специальные. С помощью универсальных методов решаются любые задачи линейного программирования. Особенностью задач линейного программирования является то, что экстремум целевой функции достигается на границе области допустимых решений.

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

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

Такие задачи в Excel решают с помощью Поиска решения .

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

Решение задач с помощью надстройки Поиск решения

1. Установка программы Поиск решения

В меню Сервис выберите команду Надстройки.

В диалоговом окне Надстройки установите флажок Поиск решения. Если диалоговое окно Надстройки не содержит команды Поиск решения , нажмите кнопку Обзор и укажите диск и папку, в которой содержится файл надстройки Solver. xla (как правило, это папка Library\ Solver folder) или запустите программу Setup , если найти файл не удаётся.

Надстройка, указанная в диалоговом окне Надстройки , остаётся активной до тех пор, пока она не будет удалена.

2. Диалоговое окно Поиск решения

Окно Поиск решения (рис. 1) вызывается командой меню Сервис>Поиск решения.

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

Рис.1.Диалоговое окно Поиск решения.

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

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

В поле Изменяя ячейки вводятся имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

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

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

Команда Изменить Изменение ограничения.

Команда Удалить служит для снятия указанного курсором ограничения.

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

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

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

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

3.Ввод и редактирование ограничений

Диалоговые окна изменения и добавления ограничений одинаковы, рис.2.

Выберите из раскрывающегося списка условный оператор, который необходимо разместить между ссылкой и её ограничением. Это знаки операторов: не более, не менее, равно и т. д.

В поле Ограничения введите число, формулу или имя ячейки или диапазона содержащих или вычисляющих ограничивающие значения.

Чтобы приступить к набору нового условия, нажмите кнопку Добавить.

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

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

Рис.2.Диалоговое окно Изменение ограничения.

4. Настройка параметров алгоритма и программы

Настройка параметров алгоритма и программы производится в диалоговом окне Параметры поиска решения , рис. 3.

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

Рис. 3. Диалоговое окно Параметры поиска решения.

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

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

При достижении отведённого временного интервала или при выполнении отведённого числа итераций, на экране появляется диалоговое окно

Поле Относительная погрешность служит для задания точности (допустимой погрешности), с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 (нуля) до1. Низкая точность соответствует введённому числу, содержащему меньшее количество десятичных знаков, чем число, используемое по умолчанию, например, 0,0001. Высокая точность увеличит время, которое требуется для того, чтобы сошёлся процесс оптимизации. Чем меньше введённое число, тем выше точность результатов.

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

Поле Сходимость результатов поиска решения применяется только к нелинейным задачам. Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость , поиск прекращается. Условием сходимости служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков, например, 0,0001 – это меньшее относительное изменение, чем 0,01. Чем меньше его значение, тем выше точность результатов. Лучшая сходимость требует больше времени на поиск оптимального решения.

Флажок Линейная модель служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи.

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

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

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

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

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

Квадратичная служит для использования квадратичной экстраполяции, которая даёт лучшие результаты при решении нелинейных задач.

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

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

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

Кнопки Метод поиска служат для выбора алгоритма оптимизации (метод Ньютона или сопряжённых градиентов).

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

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

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

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

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

1. Сохранение модели оптимизации

1. В меню Сервис выберите команду Поиск решения.
2. Нажмите кнопку Параметры.
3. Нажмите кнопку Сохранить модель. Появляется окно Сохранить модель, рис. 4.
4. В поле Задайте область модели введите ссылку на верхнюю ячейку столбца, в котором хотите разместить модель оптимизации.

Рис. 4. Диалоговое окно Сохранить модель.

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

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

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

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

1 В меню Сервис выберите команду Поиск решения.

2. Нажмите кнопку Параметры.

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

Диалоговое окно Загрузить модель используется для задания ссылки на область загружаемой (ранее сохранённой) модели оптимизации. Ссылка должна адресовать область модели целиком не достаточно указать только первую ячейку.

Вычисления и результаты решения задачи

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

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

Чтобы прервать поиск решения, нажмите клавишу ESC. Microsoft Excel пересчитает лист с учётом найденных значений влияющих ячеек.

По окончании счёта появляется диалоговое окно Результаты поиска решения, рис. 5.

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

Поле Тип отчёта служит для указания типа отчёта, размещаемого на отдельном листе книги.

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

Отчёт Устойчивость используется для создания отчёта, содержащего сведения о чувствительности решения к малым изменениям в формуле модели или в формулах ограничений. Такой отчёт не создаётся для моделей, значения в которых ограничены множеством целых чисел. В случае нелинейных моделей отчёт содержит данные для градиентов и множителей Лагранжа. В отчёт по нелинейным моделям включаются ограниченные затраты, фиктивные цены, а также диапазоны ограничений.

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

К сожалению, эти отчёты очень неудобны. Они перегружены плохо читаемыми абсолютными ссылками со знаками доллара. Желает лучшего и перевод с английского на русский.

Кнопка Сохранить сценарий служит для отображения диалогового окна Сохранение сценария , в котором можно сохранить сценарий решения задачи, чтобы использовать его в дальнейшем с помощью диспетчера сценариев Microsoft Excel. В поле Название сценария введите имя сценария. Чтобы создать сценарий, не сохраняя найденное решение и не отображая результатов на листе, сохраните сценарий в диалоговом окне Результаты поиска решения , а затем выберите Восстановить исходные значения.

Просмотр промежуточных результатов поиска решения

Режим пошагового решения задач используется при отладке моделей.

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

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

На экране появится диалоговое окно , рис. 6, а влияющие ячейки листа изменят свои значения.

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

Рис.6. Диалоговое окно Текущее состояние поиска решения.

Чтобы выполнить следующую итерацию и просмотреть её результаты, нажмите кнопку Продолжить.

Возникающие проблемы и сообщения процедуры поиска решения

Оптимальное решение не найдено

Поиск решения может остановиться до достижения оптимального решения по следующим причинам.

Пользователь прервал процесс поиска.

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

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

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

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

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

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

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

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

Итоговые сообщения процедуры поиска решения

1. Если поиск решения успешно завершён, в диалоговом окне Результаты поиска решения

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

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

Поиск свёлся к текущему решению. Все ограничения выполнены.

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

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

Поиск не может улучшить текущее решение. Все ограничения выполнены.

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

3. Поиск остановлен (истекло заданное на поиск время).

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

4. Поиск остановлен (достигнуто максимальное число итераций).

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

5. Значения целевой ячейки не сходятся.

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

6. Поиск не может найти подходящее решение.

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

7. Поиск остановлен по требованию пользователя.

Нажата кнопка Стоп в диалоговом окне Текущее состояние поиска решения после прерывания поиска решения в процессе выполнения итераций.

8. Условия для линейной модели не удовлетворяются.

Установлен флажок Линейная модель , однако итоговый пересчёт порождает такие значения, которые не согласуются с линейной моделью. Это означает, что решение недействительно для данных формул листа. Чтобы проверить линейность задачи, установите флажок Автоматическое масштабирование и повторно запустите задачу. Если это сообщение опять появится на экране, снимите флажок Линейная модель и снова запустите задачу.

9. При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения.

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

Набрано неверное имя или формула в окне Добавить ограничение или окне Изменить ограничение или в поле Ограничения были заданы целое или двоичное ограничение. Чтобы ограничить значения ячейки множеством целых чисел, выберите оператор целого ограничения в списке условных операторов. Чтобы установить двоичное ограничение, выберите оператор для двоичного ограничения.

10. Мало памяти для решения задачи.

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

Примеры выполнения задач

ПРИМЕР № 1

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

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

1. Формулировка математической модели задачи :

· переменные для решения задачи: x 1 – суточный объём изготовления продукции А, x 2 – суточный объём изготовления продукции Б, x 3 – суточный объём изготовления продукции В, x 4 – суточный объём изготовления продукции Г;

· определение функции цели (критерия оптимизации). Суммарная суточная прибыль от изготовления всех видов продукции равна:

F=12* x 1 +7* x 2 +18* x 3 +10* x 4,

поэтому цель состоит в том, чтобы среди всех допустимых значений x 1, x 2, x 3, x 4 найти такие, которые максимизируют суммарную прибыль от изготовления продуктов F:

· ограничения на переменные:

1. объём производства продукции не может быть отрицательным, т. е.

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

Таким образом, получаем следующую математическую модель задачи:

· Найти максимум следующей функции:

F=12* x 1 +7* x 2 +18* x 3 +10* x 4 max;

· При ограничениях вида:

1* x 1 +2* x 2 +1* x 3 +0* x 4 ≤ 18,

1* x 1 +1* x 2 +2* x 3 +1* x 4 ≤ 30,

1* x 1 +3* x 2 +3* x 3 +2* x 4 ≤ 40,

x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0;

2. Подготовка листа рабочей книги MS Excel для вычислений – на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 7. Переменные задачи x 1, x 2, x 3, x 4 находятся соответственно в C3, С4, С5, С6 . Целевая функция находится в ячейке С8 и содержит формулу:

12*C3+7*C4+18*C5+10*C6

Ограничения на задачу учтены в ячейках С10:С12.

3. Работа с надстройкой Поиск решения – воспользовавшись командой Сервис | Поиск решения, вводим необходимые данные для рассматриваемой задачи (установка данных в окне Поиск решения приведена на рис. 8). Результат работы по поиску решения помещён на рис. 9 – 14.

Рис. 7. Рабочий лист MS Excel для решения задачи .

Рис. 8. Установка необходимых параметров задачи в окне Поиск решения .

Рис.9. Результаты расчёта надстройки Поиск решения.

Рис. 10. Отчёт по результатам поиска решения.

Рис. 11. Отчёт по устойчивости поиска решения.

Рис. 12. Отчёт по пределам поиска решения.

ВЫВОД : из решения видно, что оптимальный план выпуска предусматривает изготовление продукции видов "А" и "Г". А продукцию видов "Б" и "В" производить не стоит. Полученная Вами прибыль составит 326 усл. ед.

ПРИМЕР № 2

Задача распределения ресурсов

Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства краски используется два исходных продукта A и B. Расходы продуктов A и B на 1 т. соответствующих красок и запасы этих продуктов на складе приведены в таблице:

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

Рассмотрим поэтапное решение этой задачи графическим способом с использованием процедуры « Поиск решения » Excel.

I. Составление математической модели задачи.

1) Переменные задачи.

Обозначим: x 1 - количество производимой краски для

внутренних работ;

x 2 - соответствующее количество краски

для наружных работ.

2) Ограничения, которым должны удовлетворять переменные задачи:

по расходу продукта A: x 1 + 2x 2 3;

по расходу продукта B: 3x 1 + x 2 3;

В левых частях последних двух неравенств определены расходы продуктов A и B, а в правых частях неравенств записаны запасы этих продуктов.

3) Целевая функция задачи.

Обозначим Z доход от продажи краски (в тысячах рублей), тогда целевая функция задачи записывается так:

Z = 2x 1 + x 2 ,

таким образом, задача состоит в том, чтобы найти max Z=2x 1 +x 2 , при ограничениях:

x 1 + 2x 2 3 (A)

3x 1 + x 2 3 (B)

x 1 , x 2 0 .

Так как переменные задачи x 1 и x 2 входят в целевую функцию и ограничения задачи линейно , то соответствующая задача оптимизации называется задачей линейного программирования (ЛП)

В рассматриваемом примере содержатся только две переменные x 1 и x 2 , поэтому задачу можно решить графически.

1) На плоскости x 1 , x 2 строим область допустимых значений переменных, определяемую ограничениями задачи:

x 1 + 2x 2 3 (A)

3x 1 + 1x 2 3 (B)

x 1 , x 2 0 .

Последнее ограничение определяет первый квадрант плоскости. Чтобы построить множество точек удовлетворяющих неравенству (А) нанесем на плоскость график прямой, определяющий границу этого множества: x 1 +2x 2 =3 (A).

Линии уровня целевой функции. Линией уровня называется множество точек, на которых функция принимает постоянное значение:

Z = 2x 1 + x 2 = К,

где К - задаваемая постоянная.

При К = 1 уравнение линии уровня будет:

2x 1 + x 2 = 1

или (в отрезках) :

При К = 2, аналогично:

2x 1 + x 2 = 2 , или .

Нанеся линии уровня на область допустимых решений (рис.13), получим, что при увеличении значения Z соответствующая линия уровня перемещается параллельно предыдущей вправо и вверх. Таким образом, точкой из многоугольника ABCD в которой целевая функция Z имеет максимальное значение будет вершина С. Эта точка и определяет решение задачи.

x 1 + 2x 2 = 3 (A)

3x 1 + x 2 = 3 (B)

x 1 * = 0.6 ; x 2 * = 1.2 ;

максимальное значение Z:

Z * = 2*0.6 + 1.2 = 2.4.

Надстройка Поиск решения в Microsoft Excel даёт возможность найти решение, оптимальное при нескольких входных значениях и наборе ограничений на решение. Программа Поиск решения содержит параметры, управляющие процессом поиска решения: максимальное время, число итераций, точность, допустимое отклонение. Каждый из этих параметров имеет значение по умолчанию, подходящее для большинства задач. Использование новых установок параметров обычно необходимо для проведения серьёзных исследований сложных систем управления. Диспетчер сценариев способен запомнить несколько решений, найденных данным средством, и сгенерировать на этой основе отчёт. Надстройка Поиск решения готовит три вида отчётов, которые характеризуют найденное решение задачи: отчёт по результатам, отчёт по устойчивости и отчёт по пределам. Режим пошагового поиска позволяет наблюдать последовательность приближений к оптимальному решению задачи. Во многих случаях это помогает «почувствовать» сходимость процесса и установить причины неудач и тупиков при поиске оптимального решения. В результате поиска решения EXCEL выводит сообщения о том, удалось ли получить оптимальное решение задачи.

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

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

Список литературы

1. Л. В. Рудикова «Microsoft Excel для студента», Санкт – Петербург, БХВ-Петербург, 2005;

2. «Лабораторные работы на персональном компьютере» И. Ф. Цисарь, издательство «Экзамен», Москва, 2002;

3. Додж М. и др. «Эффективная работа с Microsoft Excel», 2000.СПб.:Питер, 2001.

4. Солодовников А. С. «Введение в линейную алгебру и линейное программирование». Москва, издательство «Просвещение», 1966. – 184 с.

5. Стрейвер А. «Теория линейного и целочисленного программирования» в двух томах, том 1: перевод с английского. – Москва: Мир, 1991. – 360 с.

6. Ашманов С.А.«Линейное программирование». - М.: Наука, 1981.

7. Банди Б. «Основы линейного программирования»: Пер. с англ. - М.: Радио и связь, 1989.

8. Кораблин М. А. «Информатика поиска управленческих решений», Москва, СОЛОН-Пресс, 2003.

9. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.1. Общие задачи, Минск, Изд-во БГУ им. В.И. Ленина, 1977. - 176 с.

Решение задач линейного программирования в MS Excel

Инструментом для решений задач оптимизации в MS Excel служит надстройка «Поиск решения». Процедура поис­ка решения позволяет найти оптимальное значение фор­мулы, содержащейся в ячейке, которая называется целе­вой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во вли­яющих ячейках.

Если данная надстройка установлена, то «Поиск реше­ния»запускается из меню «Сервис». Если такого пункта нет, следует выполнить команду «Сервис - Надстройки...» и вы­ставить флажок против надстройки «Поиск решения».

Решение задачи оптимизации состоит из трёх этапов.

A. Создание модели задачи оптимизации.

B. Поиск решения задачи оптимизации.

C. Анализ найденного решения задачи оптимизации.

Рассмотрим подробнее эти этапы.

Этап А.

На этапе создания модели вводятся обозначения неиз­вестных, на рабочем листе заполняются диапазоны исход­ными данными задачи, вводится формула целевой функ­ции.

Этап В.

Команда «Сервис - Поиск решения» открывает диалоговое окно «Поиск решения», в котором, в свою очередь, имеются следующие поля:

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

«Равной» - служит для выбора варианта оптимизации зна­чения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить чис­ло, введите его в поле.

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

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

«Ограничения» - служит для отображения списка гранич­ных условий поставленной задачи.

«Добавить» - служит для отображения диалогового окна «Добавить ограничение».

«Изменить» - служит для отображения диалоговое окна «Изменить ограничение».

«Удалить» – служит для снятия указанного ограничения.

«Выполнить» – служит для запуска поиска решения по­ставленной задачи.

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

«Параметры» - служит для отображения диалогового окна «Параметры поиска решения», в котором можно загрузить или сохранить оптимизируемую модель и ука­зать предусмотренные варианты поиска решения.

«Восстановить» - служит для очистки полей окна диалога и восстановления значений параметров поиска ре­шения, используемых по умолчанию.

Для решения задачи оптимизации выполните следую­щие действия.

1. В меню «Сервис» выберите команду «Поиск решения».

2. В поле «Установить целевую ячейку» введите адрес или имя ячейки, в которой находится формула оптимизируемой модели.

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

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

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

4. В поле «Изменяя ячейки» введите имена или адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

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

5. В поле «Ограничения» введите все ограничения, накладываемые на поиск решения.

6. Нажмите кнопку «Выполнить».

Чтобы восстановить исходные данные, установите пере­ключатель в положение «Восстановить исходные значения».

Этап С.

Для вывода итогового сообщения о результате решения используется диалоговое окно «Результаты поиска реше­ния».

Диалоговое окно «Результаты поиска решения» содер­жит следующие поля:

«Восстановить исходные значения» - служит для восста­новления исходных значений влияющих ячеек моде­ли.

«Отчеты» - служит для указания типа отчета, размещаемо­го на отдельном листе книги.

«Результаты» - используется для создания отчета, состоя­щего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.

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

«Ограничения» - используется для создания отчета, состоя­щего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, зна­чения в которых ограничены множеством целых чи­сел. Нижним пределом является наименьшее значе­ние, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограни­чениям. Соответственно, верхним пределом называ­ется наибольшее значение.

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

Одной из возможных задач и моделей линейной оптимизации является задача о планировании производства.

Предприятие должно производить изделия видов: , причем количество каждого выпускаемого изделия не должно превысить спрос и одновременно не должно быть меньше за­планированных величин соответственно. На изготовление изделий идет m видов сырья , за­пасы которых ограничены соответственно величинами Известно, что на изготовление i -ro изделия идет единиц j -го сырья. Прибыль, получаемая от реализации изделий равна соответственно . Требуется так спланировать производство из­делий, чтобы прибыль была максимальной и при этом выполнялся план на производство каждого изделия, но не превышался спрос на него.

Цель работы: изучение современных программных средств решения задачи линейного программирования; практическое решение задач линейного программирования графическим методом, симплекс-методом и средствами программыMicrosoftExcel; программная реализация симплекс-метода на языке программирования высокого уровня.

1. Теоретическая часть

Для решения задач линейного программирования в программе Microsoft Excel имеется надстройка Поиск решения , обращение к которой производится из меню Сервис .

Если команда Поиск решения отсутствует в меню Сервис , то требуется установить надстройку «Поиск решения». Для этого в меню Сервис выбирается команда Надстройки , которая открывает диалоговое окно, показанное на рис. 1.

Покажем использование надстройки «Поиск решения» на примере решения следующей задачи.

Постановка задачи

Предприятие изготавливает и реализует три вида продукции – P 1 , Р 2 и Р 3 . Для производства продукции используются три вида ресурсов – комплектующие изделия, сырье и материалы. Запасы ресурсов и их расход на изготовление единицы продукции каждого вида приведены в табл. 1.

Таблица 1

Прибыль от реализации единицы продукции каждого вида составляет 240, 210 и 180 денежных единиц для P 1 , Р 2 и Р 3 соответственно.

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

Математическая модель задачи

Обозначим переменными x 1 , x 2 и x 3 искомые объемы производства продукции видов P 1 , Р 2 и Р 2 , а через F – прибыль предприятия. Тогда математическая постановка представленной задачи принимает следующий вид.

Определить значения переменных x 1 , x 2 и x 3 , для которых достигается максимум целевой функции

F = 240 x 1 + 210 х 2 + 180 x 3

при ограничениях:

Целевая функция описывает суммарную прибыль от реализации произведенной продукции всех трех видов. Ограничения (1), (2) и (3) учитывают расход и запасы комплектующих изделий, сырья и материалов соответственно. Поскольку объемы производства продукции не могут быть отрицательными, добавляются условия

x 1 ≥ 0; x 2 ≥ 0; x 3 ≥ 0.

Порядок оптимального решения задачи

Примерные действия, необходимые для решения задачи линейного программирования средствами программы Excel, представим в виде последовательности шагов.

Шаг 1. Исходные данные задачи записываются на рабочем листе электронной таблицы. Один из вариантов показан на рис. 2.

Замечание. Если известно исходное допустимое базисное решение, то можно несколько ускорить процесс поиска оптимального решения. Для этого начальные значения некоторых или всех переменных могут быть заданы вручную. В данном примере для их хранения используются ячейки $B$2, $C$2 и $D$2. Если допустимое базисное решение не задано, то программа Excel автоматически определяет начальные значения переменных задачи.

Шаг 2. В ячейку E3 вводится формула

СУММПРОИЗВ(В3:D3; $B$2:$D$2)

для вычисления текущего значения целевой функции, которая находит сумму попарных произведений ячеек (В3:D3) с коэффициентами при переменных в выражении целевой функции на ячейки ($B$2:$D$2) с текущими значениями переменных.

Шаг 3. Чтобы задать ограничения решаемой задачи, в ячейки E5, E6 и E7 копируется формула из ячейки E3. После этого в указанных ячейках должны быть получены формулы, представленные в табл. 2.

Таблица 2

Шаг 4. После создания таблицы с исходными данными курсор устанавливается в ячейку E3, содержащую формулу для вычисления целевой функции. Далее в меню Сервис выбирается команда Поиск решения , которая открывает диалоговое окно, приведенное на рис. 3.

В поле Установить целевую ячейку окна «Поиск решения», показанного на рис. 3, должен появиться адрес ячейки с формулой целевой функции (в данном примере это ячейка $E$3).

Затем в этом окне (рис. 3) заполняются следующие поля этого окна:

В поле Равной переключатель вида экстремума целевой функции устанавливается в положение максимальное значение (или минимальное значение при соответствующей постановке задачи);

В поле Изменяя ячейки указывается диапазон ячеек со значениями переменных задачи, выделяемый на рабочем листе электронной таблицы (в примере это ячейки $B$2:$D$2);

В поле Ограничения задаются ограничения исходной задачи. Для этого курсор устанавливается в поле ввода ограничений и нажимается кнопка Добавить . В результате выводится диалоговое окно «Добавление ограничения», показанное на рис. 4.

В этом окне в поле Ссылка на ячейку вводится адрес ячейки с формулой соответствующего ограничения (например, для ограничения (1) это будет ячейка E5), а в поле Ограничение указывается предельное значение, которое может принимать выбранное ограничение (в данном примере правая часть ограничения (1) находится в ячейке G5).

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

Затем выбирается вид отношения, связывающего левую и правую части ограничения, что показано на рис. 5.

После нажатия кнопки Добавить в окне «Добавление ограничения» (или кнопки ОК для ввода последнего ограничения) данное ограничение попадает в список ограничений решаемой задачи. С помощью кнопок Удалить и Изменить можно удалять выделенные в списке ограничения или вносить в них исправления.

Замечание . В окне «Добавление ограничения» можно указать, что все или некоторые переменные должны принимать только целые значения (рис. 5). Это позволяет получать решения задач целочисленного линейного программирования (полностью или частично целочисленных).

Шаг 5. После заполнения всех полей окна «Поиск решения» нажимается кнопка Параметры (рис. 3), которая открывает диалоговое окно «Параметры поиска решения», показанное на рис. 6.

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

Здесь (рис. 6) также можно определить параметры процесса решения: предельное время поиска решения, максимальное количество итераций, точность и т.п. Флажок Показывать результаты итераций позволяет по шагам следить за поиском решения. Флажок Автоматическое масштабирование включается в том случае, когда разброс значений переменных очень велик.

Шаг 6. Задав необходимые параметры в окне «Параметры поиска решения», следует нажать на кнопку Выполнить для поиска решения задачи (рис. 3) в окне «Поиск решения». Если решение найдено, то на экран выводится окно с соответствующим сообщением (рис. 7).

Полученные результаты отображаются на рабочем листе электронной таблицы, как это показано на рис. 8. В частности, значения переменных - в ячейках $B$2:$D$2, значение целевой функции – в ячейке E3.

Таким образом, получено оптимальное решение исходной задачи в виде вектора
, где
,
и
, для которого значение целевой функцииF максимально и составляет F * = 129825.

Результаты решения задачи линейного программирования также можно сохранить в виде отдельных рабочих листов с именами Отчет по результатам , Отчет по устойчивости и Отчет по пределам . Для сохранения результатов в виде отчетов необходимо предварительно в поле Тип отчета выделить требуемые типы отчетов (рис. 7). В этом же окне можно отказаться от полученных решений и восстановить исходные значения переменных.

Отчет по результатам для рассмотренной задачи показан на рис. 9.

В данном отчете представлены оптимальное решение задачи линейного программирования и его расположение в области допустимых решений. В графах Результат выводятся оптимальные значения целевой функции F * и переменных задачи
, а также их значения для исходного базисного решения, с которого начинался поиск оптимального решения (графаИсходное значение ). Состояние ограничений (графа Статус ) характеризует расположение точки
в области допустимых решений. ГрафаРазница показывает разности между значениями левых и правых частей ограничений (невязки). Для связанного ограничения невязка равна нулю, что свидетельствует о расположение точки
на границе области допустимых решений, которая задается этим ограничением. Если ограничение являются не связанным, то оно не влияет на оптимальное решение.

Замечание . В экономической интерпретации связанные ограничения соответствуют дефицитным ресурсам. Для не связанных ограничений графа Разница показывает оставшиеся объемы неиспользованных не дефицитных ресурсов. В рассмотренной задаче ограничения (1) и (3) соответствуют комплектующим изделиям и материалам, которые являются дефицитными ресурсами. Ограничение (2) является не связанным, т.е. не влияет на оптимальный план производства продукции по критерию максимальной прибыли. Это означает, что второй ресурс (сырье) не использован в объеме 292,5 ед.

В отчете по устойчивости (рис. 10) приведены границы устойчивости переменных задачи (графы Допустимое увеличение и Допустимое уменьшение коэффициентов целевой функции), а также границы устойчивости теневых цен (т.е. переменных двойственной задачи), в пределах которых оптимальное решение не изменяется. Большие значения пределов (1Е+30) означают фактическое отсутствие соответствующих границ, т.е. переменная может изменяться до бесконечности.

В графе Нормированная стоимость элемент во второй строке (-150) показывает, на сколько уменьшится значение функции, если в решении переменную x 2 увеличить на единицу. С другой стороны, при допустимом увеличении коэффициента функции при неизвестной x 2 на 150 единиц значение этой переменной не изменится, т.е. неизвестная x 2 будет равна нулю, а если выйти за пределы допустимого увеличения (коэффициент при x 2 увеличить более чем на 150), то неизвестная x 2 в решении будет больше нуля.

В отчете по пределам (рис. 11) показаны нижние и верхние пределы возможного изменения переменных (в пределах области допустимых решений) и соответствующие значения целевой функции (графа Целевой результат ) при этих изменениях. В частности, если x 1 = 0, а x 2 и x 3 остаются без изменений, то F = 2400 + 2100 + 180191,25 = 34425; при x 3 = 0 и неизменных x 1 и x 2 получим F = 240397,5 + 2100 + 1800 = 95400.

Введение

4.1. Исходные данные

4.2. Формулы для вычислений

4.3. Заполнение диалогового окна «Поиск решения»

4.4. Результаты решения

Заключение

Cписок литературы

Введение

линейный программирование excel оптимизационный задача

Решение широкого круга задач электроэнергетики и других отраслей народного хозяйства основывается на оптимизации сложной совокупности зависимостей, описанных математически с помощью некоторой «целевой функции» (ЦФ). Подобные функции можно записать для определения затрат на топливо для электростанций, на потери электроэнергии при транспорте ее от электростанции к потребителям и многие другие проблемные задачи. В таких случаях требуется найти ЦФ при определенных ограничениях, накладываемых на ее переменные. Если ЦФ линейно зависит от входящих в ее состав переменных и все ограничения образуют линейную систему уравнений и неравенств, то такая частная форма оптимизационной задачи получила название «задачи линейного программирования».

Тема курсовой работы «Решение задач линейного программирования в MS Excel», на примере «транспортная задача» взятой из области общей энергетики, получить практические навыки в использовании электронных таблиц Microsoft Excel и решения оптимизационных задач линейного программирования.

1. Исходные данные для решения задачи

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

Рис.1. Исходные данные

2. Краткие сведения об электронных таблицах MS Excel

Рис. 2. Вид окна приложения

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

.Использовать сложные формулы, содержащие встроенные функции.

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

.Создавать сводные таблицы.

.Применять к таблицам сортировку и фильтрацию данных.

.Осуществлять консолидацию данных (объединение данных из нескольких таблиц в одну).

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

.Выполнять автоматизированный поиск ошибок в формулах.

.Защищать данные.

.Использовать структурирование данных (скрывать и отображать части таблиц).

.Применять автозаполнение.

.Применять макросы.

.Строить диаграммы.

.Использовать автозамену и проверку орфографии.

.Использовать стили, шаблоны, автоформатирование.

.Обмениваться данными с другими приложениями.

Ключевые понятия :

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

2.Лист (объем: 256 столбцов, 65536 строк).

.Ячейка - наименьшая структурная единица размещения данных.

.Адрес ячейки - определяет положение ячейки в таблице.

.Формула - математическая запись вычислений.

.Ссылка - запись адреса ячейки в составе формулы.

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

Ввод данных :

Данные могут быть следующих типов -

·Числа.

·Текст.

·Функции.

·Формулы.

Вводить можно -

·В ячейки.

·В строку формул.

Если на экране в ячейке после ввода появляется ########, значит число длинное и в ячейке не помещается, то надо увеличить ширину ячейки.

Формулы - определяют, каким образом величины в ячейках связаны друг с другом. Т.е. данные в ячейке получаются не заполнением, а автоматически вычисляются. При изменении содержимого ячеек, на которые есть ссылка в формуле, меняется и результат в вычисляемой ячейке. Все формулы начинаются знаком =. Далее могут следовать -

·Ссылка на ячейку (например, А6).

·Функция.

·Арифметический оператор (+, -, /, *).

·Операторы сравнения (>, <, <=, =>, =).

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

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

Способ: Вставка - Функция или в строке формул щелкнуть на = . Появится диалоговое окно со списком десяти недавно использованных функций. Для расширения списка выбрать Другие функции…, откроется другое диалоговое окно, где функции сгруппированы по типам (категориям), приведено описание назначения функции и их параметров.

Полное описание по работе с электронными таблицами MS Excel, можно найти в учебниках и пособиях (специализированных).

3. Математическая постановка задачи

По критерию минимума затрат на топливо для ЭС указанного района электроснабжения необходимо определить их оптимальное топливоснабжение от трех угольных бассейнов с учетом ограничения по потребностям ЭС и производительности УБ.

Исходные данные задачи и переменные, подлежащие определению в ходе ее решения, можно представить в виде табл.3

Обозначение данных:

Вуб1, Вуб2, Вуб3 - производительность угольных бассейнов, тыс.тонн;

Суб1, Суб2, Суб3 - стоимость топлива на угольных бассейнах, у.е./тонн;

Lу - длина железнодорожного пути между УБ к ЭС, км;

Су - удельная стоимость перевозки топлива по трассе от УБ к ЭС, у.е./тонна*км (С11=С12=С13=С21=С22=С23=С31=С32=С33);

Ву - объем топлива, доставляемого от УБ на ЭС, тыс.тонн;

ВЭС1, ВЭС2, ВЭС3 - годовая потребность в топливе первой, второй, третьей ЭС соответственно, тыс.тонн;

Ву - являются параметрами переменными целевой функции, подлежащими определению в процессе решения задачи;

Необходимо определить оптимальный объем топлива (Ву), доставляемые от УБ к каждой из ЭС, при которых суммарные затраты на топливо для всех трех ЭС будут минимальными.

Целевой функцией, подлежащей оптимизации в процессе решения задачи, будут суммарные затраты на топливо для всех трех ЭС.

4. Решение задачи линейного программирования

.1 Исходные данные

Рис. 4. Исходные данные

4.2 Формулы для вычислений

Рис.5. Промежуточные расчеты

4.3 Заполнение диалогового окна «Поиск решения»

Рис. 6. Процесс оптимизации.

Рис.6.1.Задание ограничений (топлива должно быть>0).

Рис.6.2.Задание ограничений (кол-во привез. = кол-ву потреблен. топлива).

Рис.6.3.Задание ограничений (годовая отгрузка, не превышать производ. УБ1).

Рис.6.4.Задание ограничений (годовая отгрузка, не превышать производ. УБ2).

Рис.6.5.Задание ограничений (годовая отгрузка, не превышать производ. УБ3).

.4 Результаты решения

Рис.8. Результаты решения задачи

Ответ: Количество топлива (тыс. тонн), доставлено на:

ЭС4 из УБ1 составляет 118,17тн;

ЭС6 из УБ1 составляет 545,66тн;

ЭС5 из УБ2 составляет 19,66тн;

ЭС6 из УБ2 составляет 180,34тн;

ЭС5 из УБ3 составляет 277,94тн;

ЭС6 из УБ3 составляет 526,00тн;

ЭС4 всего 118,17тн;

ЭС5 всего 297,60тн;

ЭС6 всего 1252,00тн;

Затраты на топливо составили (у.е.):

Для ЭС4 - 496314,00.

Для ЭС5 - 227064,75.

Для ЭС6 - 23099064,78.

Суммарные затраты для всех ЭС составляют - 23822443,53 у.е.;

Заключение

Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.

В курсовой работе показано как создавать и работать при оформлении документа MS Word, в рамках которого рассмотрено решение экономической оптимизационной задачи, на примере «транспортная задача», взятой из области общей энергетики, средствами Microsoft Excel.