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

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

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

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

“Технология решения задач линейного программирования с помощью Поиска решений приложения 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 решают с помощью Поиска решения.

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

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

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

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

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

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

Сохранение и загрузка модели

Загрузка модели оптимизации

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

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

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

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

4. Введите ссылку на область модели.

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

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

ПРИМЕР № 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 ₁– суточный объём изготовления продукции А, x ₂ – суточный объём изготовления продукции Б, x ₃– суточный объём изготовления продукции В, x ₄ – суточный объём изготовления продукции Г;

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

F=12* x₁+7* x₂+18* x₃+10* x_4,

поэтому цель состоит в том, чтобы среди всех допустимых значений x_1,x_2,x_3,x₄найти такие, которые максимизируют суммарную прибыль от изготовления продуктов F:

F=12* x₁+7* x₂+18* x₃+10* x₄max;

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

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

x₁≥ 0, x₂≥ 0, x₃≥ 0, x₄≥ 0;

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

1* x₁+2* x₂+1* x₃+0* x₄≤ 18,

1* x₁+1* x₂+2* x₃+1* x₄≤ 30,

1* x₁+3* x₂+3* x₃+2* x₄≤ 40,

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

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

F=12* x₁+7* x₂+18* x₃+10* x₄max;

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

1* x₁+2* x₂+1* x₃+0* x₄≤ 18,

1* x₁+1* x₂+2* x₃+1* x₄≤ 30,

1* x₁+3* x₂+3* x₃+2* x₄≤ 40,

x₁≥ 0, x₂≥ 0, x₃≥ 0, x₄≥ 0;

2. Подготовка листа рабочей книги MS Excel для вычислений – на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 7. Переменные задачи x_1,x_2,x_3,x₄находятся соответственно в 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

Рис.11.

Проведя уравнение (A) к виду прямой в отрезках, получим:

Аналогично, для ограничения (B) уравнение прямой в отрезках будет:

Построим обе прямые на плоскости. Множества точек, удовлетворяющие неравенствам (A) и (B) будут полуплоскости, лежащие под соответствующими прямыми, а множество допустимых значений переменных будет пересечением (общей частью) этих полуплоскостей, лежащее в первом квадранте: четырехугольник ABCD (см. рис.12)

2 (B)

1 (A)

1 2

Рис.12.

2) На множестве допустимых решений (ABCD) найдем точку, в которой целевая функция Z=2x₁+x₂ имеет максимальное значение. Для этого посмотрим линии уровня целевой функции. Линией уровня называется множество точек, на которых функция принимает постоянное значение:

Z = 2x₁ + x₂ = К ,

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

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

2x₁ + x₂ = 1

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

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

2x₁ + x₂ = 2 , или .

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

К=1

(B)

1 (A)

1 2 3

Рис. 13.

3) Вычисление координат оптимальной точки (С).

Точка C лежит на пересечении прямых (A) и (B), поэтому, чтобы определить ее координаты надо решить систему уравнений:

x₁ + 2x₂ = 3 (A)

3x₁ + x₂ = 3 (B)

Решение:

x₁^*= 0.6 ; x₂^*= 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 с.