Составление математической модели задачи.

Решение.

План лекции

Решение задач оптимизации

ПЛАН-КОНСПЕКТ ЛЕКЦИИ

с помощью MS excel»

Разработал:

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

1. Представление о задачах оптимизации. 3

2. Решение задачи линейного программирования. 5

3. Решение транспортной задачи. 8

Содержание лекции

1. Представление о задачах оптимизации

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

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

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

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

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

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

Определение. Допустимое решение , которое доставляет максимум или минимум целевой функции , называется оптимальным планом (решением) задачи.

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

Пример простейшей задачи оптимизации. Лодка инспектора рыбнадзора находится на расстоянии 3 км от ближайшей точки берега А. Инспектору необходимо достигнуть села В, в окрестностях которого были замечены браконьеры. Село В находится на берегу реки на расстоянии 5 км. от А. Лодка проплывает по 4 км/ч, а инспектор, выйдя из лодки, может в час пройти 5 км. К какому пункту берега (т.е. на каком расстоянии от А) должна пристать лодка, чтобы инспектор достиг села В в кратчайшее время?

Сделаем схематический чертёж.

2. Решение задачи линейного программирования

Постановка задачи. Стандартом предусмотрено, что октановое число автомобильного бензина А-76 должно быть не ниже 76, а содержание серы в нем – не более 0,3%. Для изготовления такого бензина на заводе используется смесь из четырех компонентов. Данные о ресурсах смешиваемых компонентов, их себестоимости и их октановом числе, а также о содержании серы приведены в таблице

Приказом директора завода-изготовителя установлен следующий расход каждого компонента: 1 – 550 т, 2 – 10 т, 3 – 150 т, 4 – 290 т. Требуется определить, сколько на самом деле тонн каждого компонента следует использовать для получения 1000 т автомобильного бензина А-76, чтобы его себестоимость была минимальной. Какова упущенная выгода предприятия при производстве каждых 1000 т бензина при таком решении дирекции?

Построение математической модели. Составим математическую модель задачи. Пусть – количество в смеси компонента с номером С учетом этих обозначений задача минимума себестоимости принимает вид

Соотношения (1), (2) образуют математическую модель данной задачи. Первое функциональное ограничение отражает необходимость получения заданного количества смеси (1000 т), второе и третье – ограничения по октановому числу и содержанию серы в смеси, остальные – ограничения на имеющиеся объемы соответствующих ресурсов (компонентов).

Решение. Решим задачу линейного программирования (1), (2) с помощью возможностей табличного процессора MS Excel.

1. Запускаем MS Excel.

2. На Листе текущей Книги в ячейки зарезервированные для управляемых переменных , , , соответственно, введём любые начальные значения. Пусть это будет

3. В ячейку введём формулу

4. В ячейку формулу

5. В ячейку формулу

6. В ячейку формулу

7. Запускаем режим «Поиск решения» (Меню: Сервис Поиск решения или Данные Поиск решения).

8. В появившемся диалоговом окне введём информацию:

· Установить целевую ячейку:

· Равной: минимальному значению;

· Изменяя ячейки:

· Ограничения:

9. Нажимаем кнопку «Выполнить».

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

Оптимальное решение задачи имеет вид:

у.е.

Решение дирекции:

у.е.

.

Таким образом, упущенная выгода предприятия при производстве каждой 1000 т бензина при таком решении дирекции составляет 407 у.е.

3. Решение транспортной задачи

Постановка задачи. Рассмотрим пример задачи о перевозках, которую также часто называют транспортной задачей. Имеется боевых подразделений ОВД (поставщики). Во время боевой тревоги из этих подразделений нужно отправить усиление на блок-постов (потребители). Известны затраты на перевозку одного человека от каждого поставщика к каждому потребителю. Необходимо так спланировать распределение личного состава по блок-постам, чтобы суммарные затраты на доставку были минимальными.

Введём обозначения:

− подразделения ОВД,

− блок-посты,

− численность подразделения ,

− потребность в усилении блок-поста ,

− затраты (ден. ед.) на перевозку одного человека из в ;

− количество человек, доставляемых из в .

В данном случае задача имеет размерность

Если суммарная численность подразделений равна суммарной потребности блок-постов, то задача является закрытой, в противном случае − открытой. Если задача является открытой, то добавляют фиктивного поставщика или фиктивного потребителя для того, чтобы задача стала закрытой. Стоимость перевозки одного человека от фиктивного поставщика (или фиктивного потребителя) полагают равной наибольшему из значений , которые известны по условию задачи. Математическую модель транспортной задачи составляют следующие соотношения:

Задачу (1), (2) можно решить аналитически с помощью математических методов (например, распределительный метод и метод потенциалов) без привлечения компьютерных технологий. Однако в реальных условиях при большой размерности задачи её решение «вручную» может оказаться очень громоздким, требующим больших временных затрат и большого числа итераций. Использование возможностей MS Excel позволяет решить транспортную задачу практически любой размерности каждому человеку, не имеющему даже представления о математических методах решения задач такого класса.

Решение задачи. Рассмотрим закрытую задачу при Численности подразделений ОВД, потребности в усилении блок-постов и стоимости перевозок заданы в следующей таблице:

Требуется определить такой план перевозок, при котором суммарные затраты на перевозки будут минимальными.

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

1. Запускаем MS Excel. На рабочем Листе сформируем две матрицы (или таблицы).

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

2. В ячейку запишем формулу . Затем содержимое этой ячейки скопируем в ячейки

3. В ячейку запишем формулу . Затем содержимое этой ячейки скопируем в ячейки

В результате получим таблицу:

4. В ячейку введём формулу

5. Запускаем режим «Поиск решения» (Меню: Сервис Поиск решения или Данные Поиск решения).

6. В появившемся диалоговом окне установим режимы и ограничения:

· Установить целевую ячейку:

· Равной: минимальному значению;

· Изменяя ячейки:

· Ограничения:

7. Нажимаем кнопку «Выполнить».

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

Отсюда делаем вывод, что оптимальным планом перевозок является план:

.

При этом плане стоимость всех перевозок будет минимальной и составит ден. ед.

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

Дата добавления: 2017-02-01; Просмотров: 57; Нарушение авторских прав?; Мы поможем в написании вашей работы!