Лабораторная работа. Составление математических моделей экономических задач. Решение оптимизационных задач с помощью электронных таблиц

Прочитайте Задание к лабораторной работе. Если вам необходимо вспомнить тему Поиск решения, выполните упражнения

Поиск решения

Подготовка к работе

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

·        Выполните команду Сервис/Поиск решения…

·        Для загрузки надстройки выполните команду Сервис/Надстройки…

·        В диалоговом окне Надстройки (рис. 11.1) установите флажок Поиск решения. OK.

Рис. 11.1

Упражнение № 11.  SEQ Упражнение_№_*. \* ARABIC 1

Частная фирма занимается переработкой молока на нескольких заводах, расположенных в разных районах Москвы. Молоко поставляется объединениями фермеров, расположенными в городах Московской области. Стоимость молока одинакова, однако перевозка от объединения фермеров на завод зависит от расстояния и отличается для каждого объединения и завода. Потребность заводов в молоке различна. Объем молока в каждом объединении ограничен.

Потребителей (молокоперерабатывающие заводы) назовем по наименованию районов Москвы, в которых они расположены, а поставщиков (объединения фермеров) – по названиям городов Подмосковья.

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

Возможности объединений в доставке молока.

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

Затраты на перевозку тонны молока от объединения X к заводу, расположенному в районе Y, указаны в таблице.

 

Решение

·        Удалите все листы, кроме первого.

·        Сохраните файл под именем Транспортная задача.

·        Составьте модель задачи.

§        Заполните 1-ю строку и столбец A (рис. 11.11).

§        Запросы заводов на поставку молока занесите в диапазон ячеек C2:F2.

§        Возможный объем поставки молока объединениями фермеров занесите в диапазон ячеек B12:B16.

§        Общий объем молока, поставляемый каждым объединением фермеров, разместите в диапазоне ячеек B5:B9. Выделите ячейку B5 и введите формулу =СУММ(C5:F5). Скопируйте формулу в диапазон ячеек B6:B9.

§        В диапазон ячеек С12:F16 занесите стоимость перевозки тонны молока, используя данные из таблицы. Для ячеек указанного диапазона установите формат Денежный с двумя знаками после запятой.

§        Решение задачи (объем молока для перевозки) будет расположено в диапазоне ячеек C5:F9.

Рис. 11.11

§        Полная стоимость перевозки молока по маршруту Наро-Фоминск – Лужники вычисляется по формуле =C5*C12.

§        Общая стоимость перевозок на завод в Лужники составит =C5*C12+C6*C13+C7*C14+C8*C15+C9*C16. Введите эту формулу в ячейку С17.

§        Для подсчета общей стоимости перевозок на другие перерабатывающие заводы скопируйте формулу из ячейки С17 в диапазон ячеек D17:F17.

§        Для подсчета итоговой стоимости всех перевозок введите в ячейку B17 формулу =СУММ(C17:F17).

§        Выделите диапазон ячеек B17:F17 и установите для этих ячеек формат Денежный с двумя знаками после запятой.

·        Выполните команду Сервис/ Поиск решения…

·        В диалоговом окне Поиск решения установите значения (рис. 11.12).

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

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

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

Рис. 11.12

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

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

Ограничение	Причина
B5:B9<=B12:B16	объем поставок не может превышать имеющиеся запасы
C4:F4>=C2:F2	запросы потребителей должны быть выполнены полностью
C5:F9=целое	количество перевозок не может быть дробным числом

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

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

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

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

Рис. 11.13

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

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

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

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

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

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

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

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

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

·        Появится диалоговое окно Текущее состояние поиска решения (рис. 11.14). Щелкните по кнопке Продолжить.

Рис. 11.14

·        После каждой итерации на экране будет отображаться окно Текущее состояние поиска решения.

·        После окончания поиска решения на экране появится окно Результаты поиска решения (рис. 11.15), сообщающее о том, что решение найдено.

Рис. 11.15

-       Установите переключатель в значение Сохранить найденное решение.

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

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

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

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

·        Щелкните по кнопке OK.

Ответ

Минимальная сумма затрат на перевозки при соблюдении всех условий составит 2.795.450 рублей. Предлагается выполнять перевозки по следующим маршрутам:

Примечание

При записи ограничения С5:F9=целое в окне Ссылка на ячейку: укажите диапазон ячеек С5:F9, в следующем окне – цел. В окне Ограничение: будет выведено – целое. OK.

Упражнение № 11. SEQ Упражнение_№_*. \* ARABIC 2

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

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

Решение

·        Составим математическую модель задачи.

Обозначим переменной X суточный объём производства сапог первого фасона, переменной Y – второго фасона. Тогда суммарная суточная прибыль от производства сапог обоих типов составит 1500*X+1000*Y (функция цели).

Задача состоит в определении всех допустимых значений X и Y таким образом, чтобы суммарная суточная прибыль была максимальна и выполнялись следующие условия:

·        Перенесем построенную модель на лист Microsoft Excel (рис. 11.16).

Рис. 11.16

-       Задайте ячейке B1 имя X, а ячейке B2 – Y.

-       Стоимость сапог первого фасона составляет 1500 руб., а стоимость сапог второго фасона – 1000 руб., поэтому суммарная суточная прибыль от сапог обоих фасонов вычисляется по формуле =1500*X+1000*Y. Введите эту формулу в ячейку B4 (рис. 11.16).

-       В диапазон ячеек B7:C10 введите ограничения, наложенные условием задачи (рис. 11.16).

·        Для поиска оптимального решения выполните команду Сервис/Поиск решения…

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

-       Установите целевую ячейку B4.

-       Равной: максимальному значению.

-       Изменяя ячейки: B1:B2 (количество сапог первого и второго фасонов).

-       Ограничения: B7:B10<=C7:C10 (данные ячеек B7:B10 должны быть меньше либо равны данным, находящимся в ячейках C7:C10).

-       Щелкните по кнопке Параметры. Установите флажок Неотрицательные значения (так как количество сапог не может быть отрицательным числом). OK.

-       Щелкните по кнопке Выполнить (рис. 11.17).

Рис. 11.17

Ответ

Максимальная суточная прибыль будет получена при производстве 39 пар сапог первого фасона и двух пар сапог второго фасона и составит 60500 руб.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Задание к лабораторной работе

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

Подготовьте и сдайте отчет (распечатанный электронный документ, не рукописный, с указанием № группы, Ф.И.О.)

Задача 1

Рацион для питания животных на ферме состоит из двух видов кормов I и II. Содержание веществ в килограмме корма представлено в таблице:

	Корм I	Корм II
Жиры	1	3
Белки	3	1
Углеводы	1	8
Нитраты	2	4
Цена 1 кг	20 руб	10 руб

Составить наиболее дешевый рацион питания, обеспечивающий жиров не менее 6 единиц, белков не менее 9 единиц, углеводов не менее 8 единиц, нитратов не более 16 единиц.

 

Задача 2

 

Для производства телевизоров необходимо 4 вида деталей. Количество деталей, необходимых для производства одного телевизора, представлено в таблице.

	I деталь	II деталь	III деталь	IV деталь
Витязь	4	0	2	2
Рекорд	3	2	0	3

 

Прибыль от реализации одного телевизора марки Витязь – 3 у.е., Рекорд – 2 у.е.Со склада этих деталей привозят: I вида не менее 120, II вида – не более 100, III вида не более 133, IV вида не более 222. Сколько телевизоров и какого вида нужно производить, чтобы прибыль была наибольшей?

 

Задача 3

 

Задача об экономии химического сырья. На химическом предприятии оказалось возможным отходы производства возвращать в установки и использовать как добавку к исходному сырью. Установка давала за смену 50 т продукции, потребляя 84 т сырья. Выделенные отходы в количестве 34 т состояли из трех видов: первый вид –12 т, второй вид – 8 т, третий вид – 14 т. При меньшем потреблении сырья отходы выделяются в тех же пропорциях. Отходы до использования должны пройти соответствующую обработку. При этом для обработки первого и третьего видов отходов может быть использован старый, но находящийся в хорошем состоянии двухсекционный агрегат, устроенный таким образом, что в нем могут обрабатываться (в разных секциях) сразу два вида отходов. При обработке этих отходов в агрегате вырабатывается тепло в следующих количествах: для первого вида – 187 ккал/т, для третьего вида – 95 ккал/т.

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

При обработке отходов в агрегате имеют место некоторые потери, сос­тавляющие для первого вида 20% отходов, для третьего вида 40% отходов. Для обработки отходов второго вида требуется простой агрегата и тепло в количестве 120 ккал/т. Это тепло может быть получено от первого агрегата, если охлаждающую воду после ее нагрева в этом агрегате направить во второй. В результате предварительного расчета установлено, что использование одной тонны отходов каждого вида дает следующую экономию: первый вид – 4000 руб., второй вид – 2000 руб., третий вид – 5000 руб.

В каких количествах использовать отходы, чтобы обеспечить максимально возможную экономию?

 

Задача 4

 

В течение каждого квартала на четырех строительствах требуется соответственно 5, 10, 20 и 15 вагонов материалов. Возможности различных заводов по производству строительных материалов соответственно равны 10, 15 и 25 вагонам в квартал.

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

Строительство № Завод №	1	2	3	4
1	8	3	5	2
2	4	1	6	7
3	1	9	4	3