VI-947 / Васюков М.П / REShENIE_ZADACh_LINEJNOGO_PROGRAMMIROVANIYa_V_SREDE_EXCEL_PRI_POMOSchI_NADSTROJKI

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В СРЕДЕ EXCEL ПРИ ПОМОЩИ НАДСТРОЙКИ "ПОИСК РЕШЕНИЯ"

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

Необходимые навыки – умение: работать с табличным процессором Excel, присваивать имена ячейкам, диапазонам, назначать формат диапазона, использовать встроенные команды и функции.

Задание:

1.Изучить информацию о задачах линейного программирования и о средствах их решения в среде Excel.

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

3.При помощи отчетов пакета "Поиск решения" провести анализ оптимальности полученного решения задачи. Оформить результат анализа в виде вывода.

4.В соответствии с ГОСТ 7.32-2001, составить отчет по выполненному заданию в среде Word. В отчете кроме ответа привести скриншоты фрагментов рабочей книги Excel, где проводился поиск решения и скриншоты отчетов пакета "Поиск решения".

Теоретические сведения.

Существует ряд задач, где требуется найти элементы решения x1, x2, …, xn, приводящие показатель эффективности W, выраженный как линейная функция от этих переменных в минимум или максимум (экстремум), либо к некоторой константе при нескольких линейных ограничениях, равенствах или неравенствах, наложенных на эти элементы решения. В любом случае все искомые переменные должны быть неотрицательны (≥0). Задачи такого рода принято называть задачами линейного программирования.

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

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

При работе с электронной таблицей Excel применяются следующие термины:

строка (графа, ряд), которая нумеруется арабской цифрой 1,2,3…;

столбец (колонка), нумеруемый латинской буквой A,B,C…;

ячейка, место которой в таблице определяется координатами, например, А3, В5,

Х54.

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

формулы, что делает электронные таблицы универсальным расчетным инструментом.

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

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

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

				Таблица 1
Исходные данные	Зависимости между	Искомые	Класс	задачи
	переменными	переменные	оптимизации
Детерминированные	Линейные	Непрерывные	Линейное
			программирование
Детерминированные	Линейные	Целочисленные	Целочисленное
			программирование
Детерминированные	Нелинейные	Непрерывные,	Нелинейное
		целочисленные	программирование
Случайные	Линейные	Непрерывные	Стохастическое
			программирование

Для графического анализа результатов оптимизации решения задачи пакет Excel

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

кольцевые, кольчатые диаграммы, диаграммы с выделенными областями и гистограммы.

Последовательность работ при принятии оптимального формализуемого решения можно разделить на следующие этапы:

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

построение математической модели оптимизации решения задачи;

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

решение задачи, которое во многих случаях может иметь несколько вариантов;

анализ предложенных решений;

принятие оптимального решения (при этом нужно помнить, что в окончательное решение всегда принимает руководитель, а ЭВМ только рекомендует ему варианты решения);

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

Задача. Фирма производит два продукта А и В, рынок сбыта которых неограничен. Каждый продукт должен быть обработан каждой машиной I, II, III. Время обработки в часах для каждого из изделий А и В приведено в таблице 1.

Таблица 2 – Время обработки каждого из изделий на машинах в часах

	I	II	III
А	0,5	0,4	0,2
В	0,25	0,3	0,4

Время работы машин I, II, III соответственно 40, 36 и 36 часов в неделю. Прибыль от изделий А и В составляет соответственно 5 и 3 денежных единицы (д.е.). Фирме надо определить недельные нормы выпуска изделий А и В, максимизирующие прибыль.

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

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

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

Таблица 3 – Исходные данные

			Изделие А	Изделие В	Ограничения
Время работы станка			0,5	0,25	40 час/нед
I, час
Время работы станка			0,4	0,3	36 час/нед
II, час
Время работы станка			0,2	0,4	36 час/нед
Ш, час
Прибыль	от	1	5	3	Max
изделия, д.е.

Перенесем таблицу в Excel и подготовим её для решения (см. рисунок 1).

Рисунок 1 – Рабочая таблица в Excel, подготовленная к решению задачи

Ячейкам В2 и С2 присвоены имена А и В соответственно, в этих ячейках после проведения операции поиска решения будет находиться решение задачи – количество изделий А и В, необходимое для максимизации прибыли предприятия. Эти ячейки выделены серым цветом. Рядом с таблицей исходных данных непосредственно справа располагается колонка формул – столбец, куда будут занесены формулы, необходимые для решения задачи при помощи надстройки "Поиск решения" вместе с целевой формулой. Ячейка Е6 с целевой формулой выделена серым цветом, это целевая ячейка, после проведения поиска решения в ней появится максимальная прибыль предприятия при заданных ограничениях. Пока поиск решения не проведен, в колонке формул находятся нули.

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

Ограничение относительно времени работы станка I: 0,5*А+0,25*В ≤ 40

Ограничение относительно времени работы станка II: 0,4*А+0,3*В ≤ 36

Ограничение относительно времени работы станка Ш: 0,2*А+0,4*В ≤ 36

Поскольку элементы решения не могут быть отрицательными, А≥0 и В≥0

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

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

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

Целевой функцией является сумма произведений единицы прибыли на количество изделий (5*А+3*В) Max

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

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

1.Решение задачи

—В меню выбрать Сервис–"Поиск решения". Вид готового к решению задачи диалогового окна "Поиск решения" приведен на рисунке 2.

Рисунок 2 – Диалоговое окно надстройки "Поиск решения"

— В поле "Установить целевую ячейку" внести ссылку на ячейку, в которой находится целевая функция модели – $Е$6.

—В поле "Равной" установить маркер в положение "Максимальному значению".

—В поле "Изменяя ячейки" ввести диапазон, в котором находятся неизвестные величины любым способом: прописать $В$2:$С$2, или A; B, если этим ячейкам присвоены соответствующие имена, либо выделить соответствующий диапазон на рабочем листе.

Далее в диалоговую таблицу заносятся ограничения, приведенные в условии задачи.

Здесь это ограничения относительно времени работ станков I, II, III.

— Установить курсор-прямоугольник в поле "Ограничения". Нажать на кнопку

"Добавить". Появится следующее диалоговое окно, приведенное на рисунке 3.

Рисунок 3 – Диалоговое окно для добавления ограничений В поле "Ссылка на ячейку" ввести $Е$3. Выбрать знак <=. В поле "Ограничение" ввести

адрес $D$3, либо число 40, являющееся ограничением для времени работы станка I. Нажать кнопку "Добавить".

— То же повторить для ячеек $E$4 и $E$5, внося соответствующие им ограничения.

Нажать кнопку "Добавить".

— В поле "Ссылка на ячейку" ввести диапазон $В$2:$С$2 с искомыми переменными.

Выбрать для них значение "Целое". Нажать кнопку ОК.

— В диалоговом окне "Поиск решения" нажать кнопку Параметры. Соответствующее диалоговое окно приведено на рисунке 4. Значения относительной погрешности решения равной 0,001 вполне достаточно. Установить маркеры на линейную модель и неотрицательные значения. Нажать кнопку OK.

Рисунок 4 – Диалоговое окно параметров поиска решения

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

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

Рисунок 5 – Результаты поиска решения

— В рабочей таблице появятся выходные значения, приведенные на рисунке 6 – оптимальные значения выпуска изделий А и В, максимальное значение целевой функции. Эти значения были указаны в качестве элементов решения в строке "Изменяя ячейки" диалоговой таблицы пакета "Поиск решения " MS Excel

Рисунок 6 – Скриншот рабочей таблицы в Excel с решением задачи

Таким образом, ответ к задаче следующий: максимальная прибыль предприятия размером 420 денежных единиц будет достигнута при производстве изделия А в количестве 60 штук в неделю, и изделия В в количестве 40 штук в неделю (выделено серым цветом).

Кроме диалогового окна, дающего окончательное решение задачи, приведенного на рисунке 5, возможны следующие варианты результатов поиска решения (Рисунки 7 и 8)

Рисунок 7 – Решений нет вследствие неограниченности целевой функции на области допустимых решений

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

Рисунок 8 – Решений нет вследствие несовместности ограничений В случае появления этой таблички необходимо проверить правильность ограничений,

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

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

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

Для получения корректных отчетов в нашем примере были сняты ограничения на целостность (сравните рисунок 2 и рисунок 9), а также маркер "Линейная модель" в "Параметрах поиска решения (сравните рисунок 4 и рисунок 10)

Рисунок 9 – Ограничение на целостность элементов решения снято

Рисунок 10 – Снят маркер "Линейная модель"

Типы отчетов:

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

Рисунок 11 – Отчет по результатам

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

Внашей задаче полученное оптимальное решение означает выпуск изделий А и В в количестве 60 и 40 единиц соответственно. При таком плане выпуска полностью будут использованы ресурсы (время работы) 1 и 2 станков, а время работы 3-го станка избыточно.

Отчет по результатам дает информацию для анализа возможного изменения запасов недефицитных ресурсов при сохранении полученного оптимального значения ЦФ. Если на ресурс наложено ограничение типа ≤, то в графе «Разница» дается количество ресурса, которое не используется при реализации оптимального решения. Например, используется 28 часов в неделю работы третьего станка. Неизрасходованным остается 8 часов в неделю, на это количество можно уменьшить ресурс «Время работы станка III» без изменения оптимального решения.

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

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

Рисунок 12 – Отчет по устойчивости

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

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

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

Множитель Лагранжа, или теневая цена это ценность дополнительной единицы i-го ресурса. Теневая цена показывает насколько возрастет значение ЦФ в случае выделения дополнительной единицы i-го ресурса. Очевидно, что теневая цена не нулевая только для дефицитных ресурсов. Например, если время обработки на 1 станке увеличится на 1 час в неделю, прибыль возрастет на 6 денежных единиц, а увеличение времени обработки на 2 станке приведет к увеличению прибыли на 4,99 денежных единицы к исходной. Поэтому в первую очередь выгодно увеличивать время обработки изделий А и В на станке I.

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

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