5348

Информационная технология поиска решения

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

Информатика, кибернетика и программирование

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

Русский

2012-12-08

89 KB

54 чел.

Информационная технология поиска решения

Цель работы: ознакомиться со средствами поиска решения MS Excel на примере задач линейного программирования.

Краткая теория

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

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

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

Задачи линейного и нелинейного программирования ограниченной размерности эффективно решаются в среде MS Excel с использованием специальной надстройки  Поиск решения (Сервис/Надстройка). Основным ограничением модели в Excel является максимальное число переменных (200).

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

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

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

Задание 1

Разработайте математическую модель и решите следующую задачу линейного программирования средствами MS Excel.

Условие задачи

Предприятие располагает тремя производственными ресурсами (сырьем, оборудованием, электроэнергией) и может организовать производственный процесс двумя различными способами. При первом способе за один месяц предприятие выпускает 3 тыс. изделий, при втором – 4 тыс. изделий.

Исходные данные приведены в таблице:

Производственный ресурс

Расход ресурсов за месяц

Общий ресурс

1 –й способ

2 –й способ

Сырье

1

2

4

Оборудование

1

1

3

Электроэнергия

2

1

8

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

Порядок выполнения задания:

  1.  На рабочем листе определите блок ячеек для переменных х1 и х2.  Под заголовками имен переменных оставьте пустые ячейки для значений переменных (a4:b4). Эти ячейки используются для ссылок на переменные в формулах и вывода результатов поиска решения
  2.  Создайте блок клеток для целевой функции. Введите заголовок (a6) и в смежной ячейке (b6)   запишите функцию цели, как это показано на рисунке 1. Аргументами в формуле являются ссылки на пустые ячейки для значений переменных (a4 и b4). После ввода формулы в ячейке b6 появится нулевое значение.
  3.  Создайте блок клеток, содержащих ограничения, накладываемые на переменные. Введите заголовок и формулы ограничений в виде текста (a9:a12). В смежном столбце введите левые части неравенств системы ограничений (ячейки b10:b12), а в ячейки c10:c12 – правые части ограничений. Аргументами в формулах также будут являться ссылки на свободные ячейки для значений переменных. Результат подготовленных данных разработанной математической модели на рабочем листе MS Excel представлен на рисунке 1.

A

B

C

1

2

3

x1

x2

4

5

6

функция

=3*A4+4*B4 

7

8

9

ограничения

10

x1+2*x2<=4

0

4

11

x1+x2<=3

0

3

12

2x1+х2<=8

0

8

Рисунок 1 – Пример решения задачи линейного программирования

  1.  Выполните команду Сервис/ Поиск решения. В диалоговом окне Поиск решения сформируйте модель задачи оптимизации.
  2.  Нажмите кнопку Параметры в окне Поиск решения и при необходимости измените  параметры решения задачи.
  3.  Запустите задачу на выполнение нажатием кнопки  Выполнить.
  4.  Сохраните результаты в виде сценария и сформируйте отчет Результаты по полученному решению оптимизационной задачи.
  5.  Выберите пункт меню Сервис/ Сценарии и выведите отчет по созданному в п.7 сценарию в виде сводной таблицы.
  6.  Сохраните результаты работы.
  7.  Перейдите на новый рабочий лист и выполните задание 2.

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

Задание 2

Предположим, что предприятие имеет 4 фабрики и четыре пункта, в которые поставляется продукция. Фабрики располагаются в пунктах А, Б, В, Г с производственными возможностями 20, 60, 50 и 30 ед. продукции ежедневно. В пункты поставки К, Л, М, Н предприятие должно отправлять ежедневно 25, 35, 80 и 20 ед. продукции соответственно. Хранение на фабрике единицы продукции, не поставленной вовремя, в день обходится предприятию 15 ден. ед. Штраф за просроченную поставку единицы продукции составляет 50 ден.ед. в день.

Транспортные расходы приведены в таблице 1.

Таблица 1 – Транспортные расходы

Стоимость перевозки единицы продукции

6

3

4

5

5

2

3

3

3

4

2

4

5

6

2

7

Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы.

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

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

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

Для решения задачи рассмотрим ее математическую модель. Неизвестными в этой задаче являются объемы перевозок. Пусть объем перевозок с i-той фабрики в j-тый центр поставок Xij. Функция цели – это суммарные транспортные расходы, т.е.

Где Cij – стоимость перевозки единицы продукции с I-той фабрики в j-тый центр поставок.

Неизвестные в этой модели должны удовлетворять следующим условиям:

  •  Объем перевозок не может быть отрицательным
  •  Так как модель сбалансирована, то вся продукция должна быть вывезена с фабрик, а заказы поставщиков должны быть выполнены.

В результате получается следующая модель:

Минимизировать

При ограничениях   

Где ai – объем производства на i-той фабрике, bj – спрос j- того центра поставок.

Выполним решение задачи средствами MS Excel.

Порядок действий:

  1.  Ввести исходные данные о стоимости перевозок в диапазон A2:D5.

Рисунок 2 – Вид рабочего листа с данными и формулами

  1.  В ячейки A13:D13 ввести формулы, вычисляющие объем продукции, ввозимой в пункты поставок.
  2.  В ячейки E9:E12 ввести формулы, вычисляющие объем продукции, вывозимой с фабрик.
  3.  В ячейку E13 ввести целевую функцию =СУММПРОИЗВ(A2:D6;A9:D12).
  4.  Выполнить команду меню Сервис/ Поиск решения и заполнить диалоговое окно Поиск решения.
  5.  Заполним диалоговое окно следующим образом:
    •  Установить целевую функцию                 $E$13

  •  Минимальному значению                              0

  •  Изменяя ячейки                                            $A$9:$D$12

  •  Ограничения                                                 $A$13:$D$13=$A$14:$D$14

                                                                                    $A$9:$D$12>=0

                                                                                    $E$9:$E$12=$F$9:F$12

  1.  В Параметрах поиска решения установите флажок Линейная модель.
  2.  После нажатия кнопки Выполнить средство поиска решения найдет оптимальный план поставок продукции и соответствующие ему транспортные расходы.

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

Задание 1

Фирма выпускает изделия двух типов А и Б. Виды и нормы расхода сырья каждого вида на единицу изделия приведены в таблице.

Изделие

Сырье

1

2

3

4

А

2

1

0

2

Б

3

0

1

1

Запасы сырья первого вида составляют 21 ед., второго вида – 4 ед., третьего вида – 6 ед. и четвертого – 10 ед. Выпуск одного изделия типа А приносит доход 300 ден. ед., одного изделия типа Б – 200 ден. ед.

Составить план производства, обеспечивающий фирме наибольший доход.

Задание 2

Сформулируйте задание, постройте модель и решите транспортную задачу, используя средство «Поиск решения».

2

7

7

6

15

1

1

1

2

50

5

5

3

1

10

2

8

1

4

25

3

2

1

5

10

40

30

20

20

Содержание отчета

  1.  Титульный лист с постановкой задач
  2.  Результаты решения задания 1 (с формулами)
  3.  Результаты решения задания 1 (с рассчитанными значениями)
  4.  Результаты решения задания 2 (с формулами)
  5.  Результаты решения задания 2 (с рассчитанными значениями)

 Пример ввода формулы


 

А также другие работы, которые могут Вас заинтересовать

81426. Лабильность пространственной структуры белков и их денатурация. Факторы, вызывающие денатурацию 100.13 KB
  Под лабильностью пространственной структуры белка понимают способность структуры белковой молекулы претерпевать конформационные изменения под действием различных физикохимических факторов. Под денатурацией следует понимать нарушение общего плана уникальной структуры нативной молекулы белка преимущественно ее третичной структуры приводящее к потере характерных для нее свойств растворимость электрофоретическая подвижность биологическая активность и т. При непродолжительном действии и быстром удалении денатурирующих агентов возможна...
81427. Шапероны - класс белков, защищающий другие белки от денатурации в условиях клетки и облегчающий формирование их нативной конформации 105.78 KB
  Шаперо́ны (англ. chaperones) — класс белков, главная функция которых состоит в восстановлении правильной третичной структуры повреждённых белков, а также образование и диссоциация белковых комплексов. Термин «молекулярный шаперон» впервые был использован в работе Ласкей и других при описании ядерного белка нуклеоплазмина
81428. Многообразие белков. Глобулярные и фибриллярные белки, простые и сложные. Классификация белков по их биологическим функциям и по семействам: (сериновые протеазы, иммуноглобулины) 106.76 KB
  Глобулярные и фибриллярные белки простые и сложные. Так белки можно классифицировать: по форме молекул глобулярные или фибриллярные; по молекулярной массе низкомолекулярные высокомолекулярные и др.; по химическому строению наличие или отсутствие небелковой части; по выполняемым функциям транспортные защитные структурные белки и др.; по локализации в организме белки крови печени сердца и др.
81429. Иммуноглобулины, особенности строения, избирательность взаимодействия с антигеном. Многообразие антигенсвязывающих участков Н- и L-цепей. Классы иммуноглобулинов, особенности строения и функционирования 108.05 KB
  Домены тяжёлых цепей IgG имеют гомологичное строение с доменами лёгких цепей. Специфичность пути разрушения комплекса антигенантитело зависит от класса антител которых существует 5 типов: Ig IgD IgE IgG IgM. Созревающие Влимфоциты синтезируют мономерные бивалентные молекулы IgM по структуре похожие на рассматриваемые выше IgG которые встраиваются в плазматическую мембрану клеток и играют роль первых антигенраспознающих рецепторов. В количественном отношении IgG доминируют в крови и составляют около 75 от общего количества этих...
81430. Физико-химические свойства белков. Молекулярный вес, размеры и форма, растворимость, ионизация, гидратация 103.82 KB
  Молекулярный вес размеры и форма растворимость ионизация гидратация Индивидуальные белки различаются по своим физикохимическим свойствам: форме молекул молекулярной массе суммарному заряду молекулы соотношению полярных и неполярных групп на поверхности нативной молекулы белка растворимости белков а также степени устойчивости к воздействию денатурирующих агентов. Различия белков по молекулярной массе. Молекулярная масса белка зависит от количества аминокислотных остатков в полипептидной цепи а для олигомерных белков и от...
81431. Методы выделения индивидуальных белков: осаждение солями и органическими растворителями, гель-фильтрация, электрофорез, ионообменная и аффинная хроматография 104.42 KB
  Метод выделения белков основанный на различиях в их растворимости при разной концентрации соли в растворе. Соли щелочных и щёлочноземельных металлов вызывают обратимое осаждение белков т. Чаще всего для разделения белков методом высаливания используют разные концентрации солей сульфата аммония NH42SO4.
81432. Методы количественного измерения белков. Индивидуальные особенности белкового состава органов. Изменения белкового состава органов при онтогенезе и болезнях 110.81 KB
  Индивидуальные особенности белкового состава органов. Изменения белкового состава органов при онтогенезе и болезнях. Для определения количества белка в образце используется ряд методик: Биуретовый метод один из колориметрических методов количественного определения белков в растворе.
81433. История открытия и изучения ферментов. Особенности ферментативного катализа. Специфичность действия ферментов. Зависимость скорости ферментативных реакций от температуры, рН, концентрации фермента и субстрата 143.03 KB
  Особенности ферментативного катализа. Зависимость скорости ферментативных реакций от температуры рН концентрации фермента и субстрата. Собственно ферментами от лат. Важнейшие особенности ферментативного катализа эффективность специфичность и чувствительность к регуляторным воздействиям.
81434. Классификация и номенклатура ферментов. Изоферменты. Единицы измерения активности и количества ферментов 123.9 KB
  Единицы измерения активности и количества ферментов. Все изоферменты одного и того же фермента выполняют одну и ту же каталитическую функцию но могут значительно различаться по степени каталитической активности по особенностям регуляции или другим свойствам. Одна международная единица активности ME соответствует такому количеству фермента которое катализирует превращение 1 мкмоль субстрата за 1 мин при оптимальных условиях проведения ферментативной реакции. Количество единиц активности nME определяют по формуле: В 1973 г.