Линейная оптимизация

Решение задач оптимизации с помощью Поиска решения и Подбора параметров. Запросы к базам данных при помощи языка запросов MS Query.

Лабораторная работа №7

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

Упражнение 1

Задание 1

Фирма производит две модели А. и В сборных книжных полок. Их производство ограничено наличием сырья и временем машинной обработ­ки. Для каждого изделия модели А требуется 3 м² досок, а для изделия модели В - 4 м². Фирма может получать от своих поставщиков до 1700 м досок в неделю. Для каждого из­делия модели А требуется 12 мин машинного времени, а для изделия модели В - 30 мин. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой моде­ли следует выпускать фирме в неделю, если каждое изделие модели А приносит 2$ при­были. а каждое изделие модели В - 4$ прибыли?

Указания для выполнения задания.

Составим математическую модель. Обозначим: х - количество изделий модели А. выпускаемых в течение недели, у - количество изделий модели В. Прибыль от этих изделий равна 2х+ 4у $. Эту прибыль нужно максимизировать. Функция, для которой ищется экстремум (максимум или минимум) носит название целевой функции.(целевая ячейка) Беспредельному увеличению количества изделий препятствуют ограничения на количество досок 1700 м^2, отсюда можно записать ограничения для данной задачи 3x+4y<=1700. Ограничено машинное время на изготовление полок. На изделие А уходит 0.2 часа, на изделие В - 0.5 часа, а всего не более 160 ч, поэтому ограничения по времени: 0.2х + 0.5у <= 160. Кроме того, количество изделий - неотрицательное число, поэтому х>= 0, у > =0.Это задача линейного программирования (ЗЛП) и она запишется следующим образом:

Решим эту задачу в Excel. Создайте рабочую книгу и сохраните ее под своим именем, дайте первому листу имя «Полки».

Введите в ячейки рабочего листа информацию, показанную на (рис.1). Ячейкам В2 и ВЗ присвоите имена x и y. В ячейках С6, С9 и С10 представлены формулы, занесенные в соответствующие ячейки столбца В.

Выделим ячейку, в которой вычисляется целевая функция 2х+4у, и вызовем окно Поиск решения (команда Сервис /Поиск решения). В диалоговом окне в поле ввода Установить

целевую ячейку уже содержит адрес ячейки с целевой функцией $В$6.Установить переключатель Равной максимальному значению. Перейти к полю ввода Изменяя ячейки и щелчок на кнопке Предположить, в поле ввода появится адрес блока $B$2:$B$3.

Далее вводятся ограничения, щелчок на кнопке Добавить, появится диалог Добавление ограничений (Рис.2).

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

В поле ввода Ссылка на ячейку введите $B$9,правее из выпадающего списка выбрать оператор <=,в поле ввода Ограничение вводится ограничения по доскам 1700. Далее щелчок на кнопке Добавить и вновь в окне вводится следующее ограничение $B$10 <=160, после щелчка на кнопке ОК появится диалоговое окно Поиск решения Рис3.

Рис.2 Ввод ограничений

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

	Рис.3 Окно поиска решения

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

Д алее щелчок на ОК и переходим в окно Поиск решения, запустить программу на выполнение щелкнув на кнопке - Выполнить. Появится диалоговое окно Результаты поиска решения (Рис.5) с переключателями Сохранить найденное решение и Восстановить исходные значения.

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

Установить флажок Сохранить найденное решения и выбрать все отчеты - щелчoк при нажатой клавише Ctrl.После подтверждения- OK в ячейках х и у появятся оптимальные значения: чтобы получать при заданных ограничениях максимальную прибыль в неделю 1400 $(целевая функция)

Необходимо выпускать изделия А в количестве 300 штук в неделю, а полок В- 200 штук в неделю.

Задание 2

Имеются три сплава. Первый сплав содержит 70% олова и 30% свинца, второй -80% олова и 20% цинка, третий - 50%о олова. 10%o свинца и 40%о цинка. Из, них необходимо изготовить новый сплав, содержащий 15% свинца. Какое наибольшее и наименьшее процентное содержание олова может быть в этом сплаве?

Указания для выполнения задания.

Обозначим u -количество первого сплава, v- количество второго сплава, w- количества третьего сплава, взятые для изготовления нового сплава. По заданию в сплаве должно быть 15% свинца, отсюда уравнение:

Количество олова в новом сплаве:

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

, , .

В результате получаем ограничения:0.3 x + 0.1 k -0.15=0 и x + y + k -1=0,переменные х, у,k –неотрицательные. Целевая функция для данной задачи имеет вид: 0.7 x + 0.8 y + 0.5 k.

Заполнить рабочий лист, причем надо помнить, что в одной рабочей книге Имена ячеек на разных листах не должны повторяться и не совпадать с адресами ячеек. Можно использовать знак подчеркивания, например: X1_1.

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

В столбце С показаны формулы, которые вставлены в ячейки столбца В. Ячейка В8 – целевая ячейка и на нее наложен процентный формат. Выделить целевую ячейку - Сервис/Поиск решения, в ДО указать изменяемые переменные - В1:В3 (кнопка Предположить), и задать ограничения (В5:В6=0). В Параметрах установить флажки Линейная модель и Неотрицательные значения.

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

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

Далее просмотреть сценарии команда меню Сервис/Сценарии, появиться диалоговое окно Диспетчер сценариев ( Рис.7.)В нем перечислены сценарии текущего рабочего листа:МАКС1 и МИН1,ниже указаны адреса изменяемых ячеек $В$1:В$3$. Выделите в списке сценарий с именем МАКС1 и щелчок на кнопке Вывести. На рабочем листе появятся значения этого сценарияРис.8.

В ячейке В8 указано максимальное значение олова в сплаве - 75%

Вновь вызвать диспетчер сценариев Сервис/Сценарии выделить сценарий МИН1 и щелчок на кнопке Вывести ( Рис.9).В ячейке В8 при этом появится минимальное значение олово в сплаве - 55%.

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

Вывести оба сценария вместе в виде отчета, используя кнопку Отчет в окне Диспетчер сценариев. При выполнении этой команды появится диалоговое окно Отчет по сценарию. При выборе предлагается тип отчета: структура или сводная таблица. Установить переключатель Структура, поле ввода Ячейки результата, где уже выставлены адреса ячеек В5, В6,В8- не изменять. В книге появится новый рабочий лист Структура сценария (Рис.10).

Столбец Текущие значения (т.е. значения,которые выводились на рабочий лист в момент создания отчета) можно удалить.

Создать второй отчет в виде сводной таблицы. Вызвать Диспетчер сценариев, щелчок на кнопке Отчет, установить переключатель Сводная таблица. Появится новый рабочий лист Сводная таблица по сценарию (Рис.11).

Рис.8. Сценарий МАКС1

Рис.7

Рис.9 Сценарий МИН1

	Рис.10 Отчет по структуре сценария

	Рис11.Отчет в виде сводной таблицы

В этой таблице не выведены значения изменяемых ячеек В1:В3, а только приведены названия сценариев и значения целевой функции. Чтобы включить в таблицу значения В1:B3, необходимо вызвать Диспетчер сценариев и в окне Отчет по сценарию добавить в поле ввода Ячейки результата адрес блока В1:В3 перед адресами ячеек В5,В6,В8. В поле ввода должно быть В1:В3, В5,В6,В8. Сводная таблица будет иметь вид:

Задание 3

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

Предприятие производит три вида продукции (А, В,С),для выпуска каждого вида требуется определенное время обработки на всех четырех станках I,II,III,IV.(рис.12). Время работы на станках соответственно 84,42,21,42 часа.

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

Вид продукции	Время обработки в часах	Прибыль. долларах
I	II	III	IV
А
В
С

Целевая функция Ограничения

Ответ: параметр х (продукция А) =13.125;параметр у (продукция В) =2.625; параметр k (продукция С) =0; прибыль z =55.125$.

Упражнение 2

Дата добавления: 2014-10-31