(5 оценок, среднее: 4,80 из 5)
Загрузка...
Учебная работа. Курсовая работа: Технология решения задач линейного программирования с помощью Поиска решений приложения Excel
Павловский филиал
Курсовая работа
по информатике на тему:
“Разработка решения задач линейного программирования при помощи Поиска решений приложения
Excel”
.
Выполнила
: Бородулина Д.А.
Группа 05-АМ.
Проверила
: Ловыгина М.Б.
Павлово 2006 г.
Содержание
Введение……………………………………………………………………………стр.
3
Решение задач при помощи надстройки Поиск решения
Сохранение и загрузка модели
Вычисления и результаты решения задачки………………………………..стр.
10
Просмотр промежных поисковых результатов решения……………стр.11
Возникающие задачи и сообщения процедуры поиска решения……стр.12
Итоговые сообщения процедуры поиска решения……………………….стр.13
Примеры выполнения задач
Вывод……………………………………………………………………………….стр.24
Перечень литературы…………………………………………………………….стр.25
Введение
Линейная оптимизация
– это раздел математического программирования, посвящённый нахождению экстремума линейных функций нескольких переменных при доп линейных ограничениях, которые налагаются на переменные. способы, при помощи которых решаются задачки, разделяются на всепригодные (к примеру, симплексный способ) и особые. При помощи всепригодных способов решаются любые задачки линейного программирования. Индивидуальностью задач линейного программирования будет то, что экстремум мотивированной функции достигается на границе области допустимых решений.
Внедрение электрических таблиц обширно всераспространено для решения бессчетных и различных задач, связанных с учётом и контролем результатов управленческой деятель: торгово-закупочных операций, производственных планов, бухучёта и т. п. вкупе с тем форма электрической таблицы оказывается весьма комфортной при решении почти всех аналитических задач управления Деятельностью, и а именно задач исследования операций и поиска хороших решений.
В экономике оптимизационные задачки появляются в связи с многочисленностью вероятных вариантов функционирования определенного экономического объекта, когда возникает ситуация выбора варианта, лучшего по некому правилу, аспекту, характеризуемому соответственной мотивированной функцией (к примеру, иметь минимум издержек, максимум продукции).
Такие задачки в Excel решают при помощи Поиска решения
.
Процедура Поиск решения
представляет собой мощнейший инструмент для выполнения сложных вычислений. Она дозволяет отыскивать значения переменных, удовлетворяющих обозначенным аспектам оптимальности, при условии выполнения данных ограничений.
Решение задач при помощи надстройки Поиск решения
1. установка программки Поиск решения
В меню Сервис
изберите команду Надстройки.
В диалоговом окне Надстройки
установите флаг Поиск решения.
Если диалоговое окно Надстройки
не содержит команды Поиск решения
, нажмите клавишу Обзор
и укажите диск и папку, в какой содержится файл надстройки Solver.
xla
(как правило, это папка Library
Solver
folder) либо запустите программку Setup
, если отыскать файл не удаётся.
Надстройка, обозначенная в диалоговом окне Надстройки
, остаётся активной до того времени, пока она не будет удалена.
2. Диалоговое окно Поиск решения
Окно Поиск решения
(рис. 1) вызывается командой меню Сервис>Поиск решения.
Поле Установить мотивированную ячейку
служит для указания мотивированной ячейки,
Рис.1.Диалоговое окно
Поиск решения.
Клавиша Равной
служит для выбора варианта с данным значением мотивированной ячейки. Чтоб установить данное число, введите его в поле.
Поле Изменяя ячейки
служит для указания ячеек, значения которых меняются в процессе поиска решения до того времени, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, обозначенной в поле Установить мотивированную
ячейку.
В поле Изменяя ячейки
вводятся имена либо адреса изменяемых ячеек, разделяя их запятыми. Изменяемые ячейки должны быть прямо либо косвенно соединены с мотивированной ячейкой. Допускается установка до 200
изменяемых ячеек.
Поле Представить
употребляется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить мотивированную
ячейку. Итог поиска отображается в поле Изменяя ячейки.
Поля Ограничения
служат для отображения перечня граничных критерий, налагаемые на переменные задачки. Допускаются ограничения в виде равенств, неравенств, также – требование целочисленности переменных. Ограничения добавляются по одному при помощи клавиши Добавить.
Команда Поменять
служит для отображения диалогового окна Изменение ограничения.
Команда Удалить
служит для снятия обозначенного курсором ограничения.
Команда Выполнить
служит для пуска поиска решения поставленной задачки.
Команда Закрыть
служит для выхода из окна диалога без пуска поиска решения поставленной задачки. При всем этом сохраняются установки, изготовленные в окнах диалога, появлявшихся опосля нажатий на клавиши характеристики, Добавить, Поменять
либо Удалить.
Клавиша характеристики
служит для отображения диалогового окна характеристики поиска решения
, в каком можно загрузить либо сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.
Клавиша Вернуть
служит для чистки полей окна диалога и восстановления значений характеристик поиска решения, применяемых по дефлоту.
3.Ввод и редактирование ограничений
Диалоговые окна конфигурации и прибавления ограничений схожи, рис.2.
В поле ссылка на ячейку
вводится адресок либо имя ячейки либо спектра, на значения которых накладываются ограничения.
Изберите из раскрывающегося перечня условный оператор, который нужно расположить меж ссылкой и её ограничением. Это знаки операторов: не наиболее, не наименее, равно и т. д.
В поле Ограничения
введите число, формулу либо имя ячейки либо спектра содержащих либо вычисляющих ограничивающие значения.
Чтоб приступить к набору новейшего условия, нажмите клавишу Добавить.
Чтоб возвратиться в диалоговое окно Поиск решения,
нажмите клавишу ОК.
Условные операторы целого и двоичного типа можно использовать лишь при наложении ограничений на изменяемые ячейки.
Рис.2.Диалоговое окно
Изменение ограничения.
4. Настройка характеристик метода и программки
Настройка характеристик метода и программки делается в диалоговом окне характеристики поиска решения
, рис. 3.
В окне инсталлируются ограничения на время решения задач, выбираются методы, задаётся точность решения, предоставляется возможность для сохранения вариантов модели и их следующей загрузки. значения и состояния частей управления, применяемые по дефлоту, подступают для решения большинства задач.
Рис. 3. Диалоговое окно
характеристики поиска решения.
Поле Наибольшее время
служит для ограничения времени, отпускаемого на поиск решения задачки. В поле можно ввести время (в секундах) не превышающее 32767;
Поле Предельное число итераций
служит для управления временем решения задачки, путём ограничения числа промежных вычислений. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, применяемое по дефлоту, подступает для решения большинства обычных задач.
При достижении отведённого временного интервала либо при выполнении отведённого числа итераций, на дисплее возникает диалоговое окно Текущее состояние поиска решения.
Поле Относительная погрешность
служит для задания точности (допустимой погрешности), с которой определяется соответствие ячейки мотивированному значению либо приближение к обозначенным границам. Поле обязано содержать число из интервала от 0 (нуля) до1. Низкая точность соответствует введённому числу, содержащему наименьшее количество десятичных символов, чем число, применяемое по дефлоту, к примеру, 0,0001. Высочайшая точность прирастит время, которое требуется для того, чтоб сошёлся процесс оптимизации. Чем меньше введённое число, тем выше точность результатов.
Поле Допустимое отклонение
служит для задания допуска на отклонение от рационального решения, если огромное количество значений влияющей ячейки ограничено обилием целых чисел. При указании огромного допуска поиск решения завершается резвее.
Поле Сходимость
поисковых результатов решения применяется лишь к нелинейным задачкам. Когда относительное изменение значения в мотивированной ячейке за крайние 5 итераций становится меньше числа, обозначенного в поле Сходимость
, поиск прекращается. Условием сходимости служит дробь из интервала от 0 (нуля) до 1. Наилучшую сходимость охарактеризовывает большее количество десятичных символов, к примеру, 0,0001 – это наименьшее относительное изменение, чем 0,01. Чем меньше его больше времени на поиск рационального решения.
Флаг Линейная модель
служит для убыстрения поиска решения линейной задачки оптимизации либо линейной аппроксимации нелинейной задачки.
Флаг Неотрицательные значения
дозволяет установить нулевую нижнею границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение
диалогового окна Добавить ограничение
.
Флаг Автоматическое масштабирование
служит для включения автоматической нормализации входных и выходных значений, отменно различающихся по величине, к примеру, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.
Флаг Демонстрировать результаты итераций
служит для приостановки поиска решения для просмотра результатов отдельных итераций.
Клавиши Оценки
служат для указания способа экстраполяции (линейная либо квадратичная), применяемого для получения начальных оценок значений переменных в любом одномерном поиске.
Линейная
служит для использования линейной экстраполяции вдоль касательного вектора.
Квадратичная
служит для использования квадратичной экстраполяции, которая даёт наилучшие результаты при решении нелинейных задач.
Клавиши Разности
(производные) служат для указания способа численного дифференцирования (прямые либо центральные производные), который употребляется для вычисления личных производных мотивированных и ограничивающихся функций.
Прямые
употребляется для гладких непрерывных функций.
Центральные
употребляется для функций, имеющих разрывную производную. Не глядя на то, что данный метод просит больше вычислений, он может посодействовать при получении итогового сообщения о том, что процедура поиска решения не может сделать лучше текущий набор влияющих ячеек.
Клавиши способ поиска
служат для выбора метода оптимизации (способ Ньютона либо сопряжённых градиентов).
Клавиша Ньютона
служит для реализации квазиньютоновского способа, в каком запрашивается больше памяти, но производится меньше итераций, чем в способе сопряжённых градиентов. тут рассчитываются личные производные второго порядка.
Клавиша Сопряжённых градиентов
служит для реализации способа сопряжённых градиентов, в каком запрашивается меньше памяти, но производится больше итераций, чем в способе Ньютона. Данный способ следует употреблять, если задачка довольно велика и нужно сберегать память, также если итерации дают очень маленькое отличие в поочередных приближениях.
Для решения линейных задач употребляются методы симплексного способа. Для решения целочисленных задач употребляется способ веток и границ.
Команда Сохранить модель
служит для отображения на дисплее диалогового окна Сохранить модель,
в каком можно задать ссылку на область ячеек, созданную для хранения модели оптимизации. Данный вариант предусмотрен для хранения на листе наиболее одной модели оптимизации. 1-ая модель сохраняется автоматом.
Команда Загрузить модель
служит для отображения на дисплее диалогового окна Загрузить модель,
в каком можно задать ссылку на область ячеек, содержащих загружаемую модель.
Сохранение и загрузка модели
1. Сохранение модели оптимизации
изберите команду Поиск решения.
Возникает окно Сохранить модель,
рис. 4.
введите ссылку на верхнюю ячейку столбца, в каком желаете расположить модель оптимизации.
Рис. 4. Диалоговое окно
Сохранить модель.
значения частей управления диалоговых окон Поиск решения
и характеристики поиска решения
записываются на лист. Чтоб употреблять на листе несколько моделей оптимизации, необходимо сохранить их в различных спектрах (столбцах).
Предлагаемый спектр содержит ячейку для всякого ограничения, также ещё три ячейки. Можно также ввести ссылку лишь на верхнюю ячейку столбца, в каком следует сохранить модель.
Диалоговое окно Загрузить модель
употребляется для задания ссылки на область загружаемой модели оптимизации. ссылка обязана адресовать область модели полностью, недостаточно указать лишь первую ячейку.
2. загрузка модели оптимизации
Перед тем как употреблять данную функцию, нужно сохранить хотя бы одну модель.
1 В меню Сервис
изберите команду Поиск решения.
2. Нажмите клавишу характеристики.
3. Нажмите клавишу Загрузить модель.
Возникает окно, аналогичное окну Сохранить модель.
4. Введите ссылку на область модели.
Диалоговое окно Загрузить модель
употребляется для задания ссылки на область загружаемой (ранее сохранённой) модели оптимизации. ссылка обязана адресовать область модели полностью не довольно указать лишь первую ячейку.
Вычисления и результаты решения задачки
Для пуска оптимизатора нажмите клавишу Выполнить в окне Поиск решения.
программка начинает работать, в строке сообщений (слева понизу листа) возникает сообщение Постановка задачки… Ваша таблица с моделью и параметрами метода автоматом приводится к эталонам постановки задач математического программирования. Это преимущество Excel. В остальных пакетах Для вас пришлось бы оторваться от экономической сущности задачки и заниматься формальной математической постановкой задачки. Опосля шага постановки решается задачка.
Чтоб оборвать поиск решения, нажмите кнопку ESC. Microsoft Excel перечтет лист с учётом отысканных значений влияющих ячеек.
По окончании счёта возникает диалоговое окно Поисковые результаты решения, рис. 5.
Рис. 5. Диалоговое окно
Поисковые результаты решения.
Нажав подобающую клавишу можно сохранить отысканное решение во влияющих ячейках модели либо вернуть начальные значения.
Поле Тип отчёта
служит для указания типа отчёта, размещаемого на отдельном листе книжки.
отчет Результаты
употребляется для сотворения отчёта, состоящего из мотивированной ячейки и перечня влияющих ячеек модели, их начальных и конечных значений, также формул ограничений и доп сведений о наложенных ограничениях.
отчет Устойчивость
употребляется для сотворения отчёта, содержащего сведения о чувствительности решения к малым изменениям в формуле модели либо в формулах ограничений. Таковой отчет не создаётся для моделей, значения в каких ограничены обилием целых чисел. В случае нелинейных моделей отчёт содержит данные для градиентов и множителей Лагранжа. В отчет по нелинейным моделям врубаются ограниченные Издержки, фиктивные цены, также спектры ограничений.
отчет Пределы
употребляется для сотворения отчёта, состоящего из мотивированной ячейки и перечня влияющих ячеек модели, их значений, также нижних и верхних границ. Таковой отчет не создаётся для моделей, значения в каких ограничены обилием целых чисел. Нижним пределом является меньшее время как значения других влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно верхним пределом именуется наибольшее
К огорчению, эти отчеты весьма неудобны. Они перегружены плохо читаемыми абсолютными ссылками со знаками бакса. Хочет наилучшего и перевод с британского на российский.
Клавиша Сохранить сценарий
служит для отображения диалогового окна Сохранение сценария
, в каком можно сохранить сценарий решения задачки, чтоб употреблять его в предстоящем при помощи диспетчера сценариев Microsoft Excel. В поле Заглавие сценария
введите имя сценария. Чтоб сделать сценарий, не сохраняя отысканное решение и не отображая результатов на листе, сохраните сценарий в диалоговом окне Поисковые результаты решения
, а потом изберите Вернуть начальные
значения.
Просмотр промежных поисковых результатов решения
Режим пошагового решения задач употребляется при отладке моделей.
В диалоговом окне Поиск решения
нажмите клавишу характеристики.
Чтоб получить возможность просмотра текущих значений влияющих ячеек каждой итерации, установите флаг Демонстрировать результаты итераций,
нажмите клавишу ОК, а потом клавишу Выполнить.
На дисплее покажется диалоговое окно Текущее состояние поиска решения
, рис. 6, а действующие ячейки листа изменят свои значения.
Чтоб приостановить поиск решения и вывести на экран диалоговое окно Поисковые результаты решения,
нажмите клавишу Стоп.
Рис.6. Диалоговое окно
Текущее состояние поиска решения.
Чтоб выполнить последующую итерацию и просмотреть её результаты, нажмите
клавишу Продолжить.
Возникающие задачи и сообщения процедуры поиска решения
Среднее решение не найдено
Поиск решения может тормознуть до заслуги рационального решения по последующим причинам.
юзер оборвал процесс поиска.
Команда Демонстрировать результаты итераций
в диалоговом окне характеристики
поиска решения выбрана перед Выполнить.
юзер надавил клавишу Стоп
в режиме пошагового выполнения итераций, по истечении времени, отведённого на работу процедуры, либо опосля выполнения данного числа итераций.
Установлен флаг Линейная модель
в диалоговом окне характеристики
поиска решения, в то время как решаемая задачка не линейна.
Установить мотивированную
диалогового окна Поиск решения
, неограниченно возрастает либо миниатюризируется. нужно уменьшить значения полей Наибольшее время
либо Итерации
в диалоговом окне характеристики поиска решения.
В случае задач, значения в каких ограничены обилием целых чисел, нужно уменьшить Допустимое отклонение
диалогового окна характеристики поиска решения
, что дозволит отыскать наилучшее решение.
В случае нелинейных задач нужно уменьшить значение в поле Сходимость
диалогового окна Характеристики поиска решения
, что дозволит продолжать поиск решения, когда
Если значения влияющих ячеек либо значения влияющей и мотивированной ячеек различаются на несколько порядков, нужно установить флаг Автоматическое масштабирование
в диалоговом окне характеристики поиска решения.
Занесите нужные конфигурации и запустите функцию поиска решения опять.
Если отысканное решение нелинейной задачки значительно различается от ожидаемого результата, запустите функцию поиска решения с иными исходными значениями влияющих ячеек. Если задать такие значения влияющих ячеек, которые близко размещены от экстремальной точки мотивированной функции, можно существенно уменьшить время поиска решения.
Итоговые сообщения процедуры поиска решения
1. Если поиск решения удачно завершён, в диалоговом окне Поисковые результаты решения
выводится одно из последующих сообщений.
Решение найдено. Все ограничения и условия оптимальности выполнены.
Все ограничения соблюдены с установленной точностью и найдено данное
Поиск свёлся к текущему решению. Все ограничения выполнены.
Относительное изменение значения в мотивированной ячейке за крайние 5 итераций сделалось меньше установленного значения параметра Сходимость
в диалоговом окне Характеристики поиска решения
. Чтоб отыскать наиболее четкое решение, установите наименьшее Сходимость
, но это займёт больше времени.
2. Если поиск не может отыскать среднее решение, в диалоговом окне Поисковые результаты решения
выводится одно из последующих сообщений.
Поиск не может сделать лучше текущее решение. Все ограничения выполнены.
В процессе поиска решения недозволено отыскать таковой набор значений влияющих ячеек, который был бы лучше текущего решения. Ориентировочное решение найдено, но или предстоящее уточнение нереально, или данная погрешность очень высока. Измените погрешность на наименьшее число и запустите функцию поиска решения опять.
3. Поиск остановлен (истекло данное на поиск время).
Время, отпущенное на решение задачки, исчерпано, но достигнуть удовлетворительного решения не удалось. Чтоб при последующем запуске процедуры поиска решения не повторять выполненные вычисления, установите переключатель Сохранить отысканное
решение
либо Сохранить сценарий
.
4. Поиск остановлен (достигнуто наибольшее число итераций).
Произведено разрешённое число итераций, но достигнуть удовлетворительного решения не удалось. Повышение числа итераций может посодействовать, но следует разглядеть результаты, чтоб осознать предпосылки остановки. Чтоб при последующем запуске процедуры поиска решения не повторять выполненные вычисления установите переключатель Сохранить отысканное
решение
либо Сохранить сценарий
.
5. значения мотивированной ячейки не сходятся.
Значение мотивированной ячейки неограниченно возрастает (либо миниатюризируется), даже если все ограничения соблюдены.Может быть, следует в задачке снять одно ограничение либо сходу несколько, либо наложить доп ограничения. Изучите процесс расхождения решения, проверьте ограничения и запустите задачку опять. к примеру, в задачке о хороших ранцах банков, если не наложить ограничение на портфель вербования ресурсов, то недозволено создать итерацию, которая удовлетворяла бы всем ограничениям при данной точности. возможно, ограничения противоречивы. Обследуйте лист на предмет вероятных ошибок в формулах ограничений либо в выборе ограничений.
7. Поиск остановлен по просьбе юзера.
Нажата клавиша Стоп в диалоговом окне Текущее состояние поиска решения
опосля прерывания поиска решения в процессе выполнения итераций.
8. Условия для линейной модели не удовлетворяются.
Установлен флаг Линейная модель
, но итоговый пересчёт порождает такие значения, которые не согласуются с линейной моделью. Это значит, что решение недействительно для данных формул листа. Чтоб проверить линейность задачки, установите флаг Автоматическое масштабирование и повторно запустите задачку. Если это сообщение снова покажется на дисплее, снимите флаг Линейная модель
и опять запустите задачку.
9. При поиске решения найдено неверное
При пересчёте значений ячеек найдена ошибка в одной формуле либо в нескольких сходу. Найдите мотивированную ячейку либо ячейку ограничения, порождающие ошибку, и измените их формулы так, чтоб они возвращали подходящее числовое
Набрано неправильное имя либо формула в окне Добавить ограничение либо окне Поменять ограничение либо в поле Ограничения были заданы целое либо двоичное ограничение. Чтоб ограничить значения ячейки обилием целых чисел, изберите оператор целого ограничения в перечне условных операторов. Чтоб установить двоичное ограничение, изберите оператор для двоичного ограничения.
10. Не много памяти для решения задачки.
Система не смогла выделить память, нужную для поиска решения. Закройте некие файлы либо приложения, и попробуйте опять выполнить функцию поиска решения.
Примеры выполнения задач
ПРИМЕР № 1
Для производства четырёх видов продукции употребляют три вида сырья. Припасы сырья, нормы его расхода и Прибыль от реализации всякого продукта приведены в таблице.
Какое количество продукции всякого вида обязано изготовляться, чтоб Доход от реализации был наибольшим?
Тип сырья
Нормы расхода сырья на одно изделие
Припасы сырья
А
Б
В
Г
I
1
2
1
0
18
II
1
1
2
1
30
III
1
3
3
2
40
ЦЕНА ИЗДЕЛИЯ
12
7
18
10
Решение
1. Формулировка математической модели задачки
:
· переменные для решения задачки: x
1
– дневной объём производства продукции А, x
2
– дневной объём производства продукции Б, x
3
– дневной объём производства продукции В, x
4
–
дневной объём производства продукции Г;
· определение функции цели (аспекта оптимизации). Суммарная дневная Прибыль от производства всех видов продукции равна:
F=12* x1
+7* x2
+18* x3
+10* x4,
потому цель заключается в том, чтоб посреди всех допустимых значений x1,
x2,
x3,
x4
отыскать такие, которые максимизируют суммарную Прибыль от производства товаров F:
F=12* x1
+7* x2
+18* x3
+10* x4
max;
· ограничения на переменные:
1. объём производства продукции не быть может отрицательным, т. е.
x1
≥ 0, x2
≥ 0, x3
≥ 0, x4
≥ 0;
2. расход начального продукта для производства всех видов продукции не может превосходить очень вероятного припаса данного начального продукта, т. е.
1* x1
+2* x2
+1* x3
+0* x4
≤ 18,
1* x1
+1* x2
+2* x3
+1* x4
≤ 30,
1* x1
+3* x2
+3* x3
+2* x4
≤ 40,
Таковым образом, получаем последующую математическую модель задачки:
· Отыскать максимум последующей функции:
F=12* x1
+7* x2
+18* x3
+10* x4
max;
· При ограничениях вида:
1* x1
+2* x2
+1* x3
+0* x4
≤ 18,
1* x1
+1* x2
+2* x3
+1* x4
≤ 30,
1* x1
+3* x2
+3* x3
+2* x4
≤ 40,
x1
≥ 0, x2
≥ 0, x3
≥ 0, x4
≥ 0;
2. Подготовка листа рабочей книжки
MS
Excel для вычислений
–
на рабочий лист вводим нужный текст, данные и формулы в согласовании с рис. 7. Переменные задачки x1,
x2,
x3,
x4
находятся соответственно в 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
задачка распределения ресурсов
Предприятие делает и реализует краску 2-ух видов: для внутренних и наружных работ. Для производства краски употребляется два начальных продукта A и B. Расходы товаров A и B на 1 т. соответственных красок и припасы этих товаров на складе приведены в таблице:
Начальный
Расход товаров (в тоннах на 1 т. краски)
Припас продукта на
продукт
краска для внутренних работ
краска для наружных работ
складе
( тонн )
A
1
2
3
B
3
1
3
Продажная стоимость за 1 тонну краски для внутренних работ составляет 2 000 рублей, краска для внешних работ продается по 1 000 рублей за 1 тонну. Требуется найти какое количество краски всякого вида следует создавать предприятию, чтоб получить наибольший Доход.
Разглядим поэтапное решение данной задачки графическим методом с внедрением процедуры « Поиск решения » Excel.
I.
Составление математической модели задачки.
1) Переменные задачки.
Обозначим: x1
— количество производимой краски для
внутренних работ;
x2
— соответственное количество краски
для внешних работ.
2) Ограничения,
которым должны удовлетворять переменные задачки:
x1
, x2
0;
по расходу продукта A: x1
+ 2×2
3;
по расходу продукта B: 3×1
+ x2
3;
В левых частях крайних 2-ух неравенств определены расходы товаров A и B, а в правых частях неравенств записаны припасы этих товаров.
3) Мотивированная функция задачки.
Обозначим Z Доход от реализации краски (в тыщах рублей), тогда мотивированная функция задачки записывается так:
Z = 2×1
+ x2
,
таковым образом, задачка заключается в том, чтоб отыскать max Z=2×1
+x2
, при ограничениях:
x1
+ 2×2
3 (A)
3×1
+ x2
3 (B)
x1
, x2
0 .
Потому что переменные задачки x1
и x2
входят в мотивированную функцию и ограничения задачки линейно
, то соответственная задачка оптимизации именуется задачей линейного программирования (ЛП)
В рассматриваемом примере содержатся лишь две переменные x1
и x2
, потому задачку можно решить графически.
1) На плоскости x1
, x2
строим область допустимых значений переменных, определяемую ограничениями задачки:
x1
+ 2×2
3 (A)
3×1
+ 1×2
3 (B)
x1
, x2
0 .
Крайнее ограничение описывает 1-ый квадрант плоскости. Чтоб выстроить огромное количество точек удовлетворяющих неравенству (А) нанесем на плоскость график прямой, определяющий границу этого огромного количества: x1
+2×2
=3 (A).
Приведем это уравнение к виду: 
. А это уравнение прямой «в отрезках» и для построения данной прямой употребляются две точки (a , 0) и (0 , b). (См. набросок 11).
b
a 
Рис.11.
Проведя уравнение (A) к виду прямой в отрезках, получим:
Аналогично, для ограничения (B) уравнение прямой в отрезках будет:
Построим обе прямые на плоскости. Огромного количества точек, удовлетворяющие неравенствам (A) и (B) будут полуплоскости, лежащие под надлежащими прямыми, а огромное количество допустимых значений переменных будет пересечением (общей частью) этих полуплоскостей, лежащее в первом квадранте: четырехугольник ABCD (см. рис.12)
3
2 (B)
B
C
1 (A)
A
3
D
1 2
Рис.12.
2) На огромном количестве допустимых решений (ABCD) найдем точку, в какой мотивированная функция Z=2×1
+x2
имеет наибольшее полосы уровня
мотивированной функции. Линией уровня именуется огромное количество точек, на которых функция воспринимает неизменное
Z = 2×1
+ x2
= К ,
где К — задаваемая неизменная.
При К = 1 уравнение полосы уровня будет:
2×1
+ x2
= 1
либо (в отрезках) :
При К = 2, аналогично:
2×1
+ x2
= 2 , либо 
.
Нанеся полосы уровня на область допустимых решений (рис.13), получим, что при увеличении значения Z соответственная линия уровня {перемещается} параллельно предшествующей на Право и ввысь. Таковым образом, точкой из многоугольника ABCD в какой мотивированная функция Z имеет наибольшее задачки.
3
К=1
(B)
B
C
1 (A)
A
D
1 2 3
Рис. 13.
3) Вычисление координат хорошей точки (С).
Точка C лежит на пересечении прямых (A) и (B), потому, чтоб найти ее координаты нужно решить систему уравнений:
x1
+ 2×2
= 3 (A)
3×1
+ x2
= 3 (B)
Решение:
x1
*
= 0.6 ; x2
*
= 1.2 ;
наибольшее
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. Стрейвер А. «Теория линейного и целочисленного программирования» в 2-ух томах, том 1: перевод с британского. – Москва: мир, 1991. – 360 с.
6. Ашманов С.А.«Линейное программирование». — М.: Наука, 1981.
7. Банди Б. «Базы линейного программирования»: Пер. с англ. — М.: Радио и связь, 1989.
8. Кораблин М. А. «Информатика поиска управленческих решений», Москва, СОЛОН-Пресс, 2003.
9. Габасов Р., Кириллова Ф.М. способы линейного программирования. Ч.1. Общие задачки, Минск, Изд-во БГУ им. В.И. Ленина, 1977. — 176 с.
]]>