Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Индивидуальные задания.




Решите систему линейных уравнений:

а) методом Крамера;

b) с помощью обратной матрицы.

Сделайте проверку.

 


Лабораторная работа № 13
Решение задач оптимизации

Задачи оптимизации занимают очень важное место в бизнесе, производстве, прогнозировании. Условно эти задачи можно разделить на следующие категории:

· транспортная задача – минимизация расходов на транспортировку товаров;

· задача о назначениях – составление штатного расписания с минимизацией денежных затрат на заработную плату или времени выполнения работ;

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

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

Задача оптимизации в общем виде формулируется следующим образом.

Найти значения переменных x1, x2, … , xn, такие, что целевая функция f(x1, x2, … , xn) примет максимальное, минимальное или заданное значения при ограничениях вида g(x1, x2, … , xn).

Таким образом, задача оптимизации содержит три основных компонента:

· переменные x1, x2, … , xn – определяемые величины;

· целевая функция – это цель, записанная математически в виде функции от переменных, принимающая максимальное, минимальное или заданное значения;

· ограничения – условия или соотношения, которым должны удовлетворять переменные.

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

Продемонстрируем эту возможность на примере решения следующей транспортной задачи.

Пример 1.Компания «Атлант» хранит свою продукцию на трех складах (первом, втором и третьем), расположенных в разных частях города. На этих складах хранится продукция в количествах 1000, 3000 и 2500 штук соответственно. Продукцию необходимо доставить четырем оптовым покупателям «Урал», «Купец», «Гелиос» и «Меркурий» с минимальными затратами, заявки которых составляют 1300, 800, 2700 и 1700 штук соответственно. Склады оптовых покупателей также расположены в разных частях города. Стоимости (в рублях) доставки одной штуки продукции со складов компании на склады покупателей показаны в следующей таблице.

Склады компании Оптовые покупатели
«Урал» «Купец» «Гелиос» «Меркурий»
№1
№2
№3

1. Построим математическую модель задачи: определим переменные, целевую функцию и ограничения.

Пусть:

· x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34 – количество продукции, перевозимой со складов компании на соответствующие склады покупателей;

· z=50 x11 + 150 x12 + 60 x13 + 75 x14 + 100 x21 + 30 x22 +100 x23 +40 x24+ +70x31+180 x32 + 210 x33 + 120 x34– целевая функция, общая стоимость доставки грузов покупателям;

· x11 + x12 + x13 + x14=1000,
x21 + x22 +x23 +x24=3000,
x31+x32 + x33 + x34=2500
– ограничения для складов компании;

· x11+ x21 + x31=1300,
x12 + x22 + x32=800,
x13 + x23 + x33=2700,
x14+ x24+ x34=1700
– ограничения для складов покупателей.

2. Имеем сбалансированную транспортную задачу, так как спрос покупателей (1300+800+2700+1700=6500) равен предложению производителей (1000+3000+2500=6500).

3. Запустите табличный процессор MS Excel. Переименуйте Лист 1 в Сбалансированная модель.

4. Составьте табличную модель Excel (рис. 49).

Рис. 49. Сбалансированная модель

5. Последняя таблица не обязательна. Целевую функцию можно было вычислить по формуле:

6. =СУММПРОИЗВ(В4:Е6;В13:Е15).

7. Выделите целевую ячейку и запустите надстройку Поиск решения (Данные 4 Анализ 4 Поиск решения).

8. В появившемся диалоговом окне Поиск решения укажите адреса целевой ячейки, диапазон изменяемых ячеек и ограничения (рис. 50). Целевую ячейку установите равной минимальному значению.

Рис. 50. Диалоговое окно «Поиск решения»

9. В диалоговом окне параметры Поиска решенияустановите флажки Линейная модель, Неотрицательные значения и Автоматическое масштабирование.

10. В диалоговом окне Поиск решения нажмите кнопку Выполнить.

11. Получаем оптимальное решение задачи (рис. 51).

Рис. 51. Оптимальное решение задачи

12. Скопируйте полученную табличную модель на Лист 2 рабочей книги и переименуйте его в Несбалансированная задача.

13. Решим эту же задачу, немного изменив условие.

14. Пусть на складе №1 хранится не 1000 штук продукции, а 500. В таком случае на трех складах компании хранится 6000 штук продукции, покупатели по-прежнему заказывают 6500 штук. Перед нами транспортная задача с дефицитом.

15. Несбалансированная задача решается аналогично сбалансированной. Изменения коснуться только ограничений. Причем в ограничениях для складов покупателей знак «=» заменяется знаком « ≤ ».

16. После выполнения надстройки Поиск решения (рис. 52) получаем, что покупатель «Гелиос» недополучит 500 ед. продукции, а минимальные транспортные расходы составят 479 000 (рис. 53).

Рис. 52. Поиск решения

 

Рис. 53. Оптимальное решение задачи

17. Покажите работу преподавателю.

 

Частным случаем транспортной задачи является задача о назначениях. В общем виде она формулируется следующим образом: имеется n различных работ и n рабочих. Известны стоимости выполнения каждого вида работ каждым работником. Необходимо так составить штатное расписание, чтобы все работы были выполнены, на выполнение каждой работы назначался только один работник, а затраты на заработную плату были минимальными. В данном случае задача является сбалансированной, так как количество работников равно количеству работ. Ограничения записываются в виде следующих равенств.

· x11 + x12 + …+ x1n=1,
x21 + x22 +… +x2n=1,


xn1+xn2 + … + xnn=1
– ограничения для работников (каждый работник может выполнять только один вид работ).

· x11 + x21 + …+ xn1=1,
x12 + x22 +… +xn2=1,


x1n+x2n + … + xnn=1
– ограничения для работ (каждый вид работ может быть выполнен только одним работником).

xij – это двоичные переменные, которые могут принимать только два значения: 1, если работник i назначается на выполнение работы j и 0, если не назначается.

Решение задачи о назначениях рассмотрим на примере.

Пример 2.В лингвистическом центре работают 4 преподавателя по следующим направлениям: «Английский для начинающих», «Деловой английский», «Подготовка к ЕГЭ» и «Английский для путешествий». Стоимость академического часа работы каждого преподавателя по каждому курсу представлена в таблице. Составьте оптимальное распределение нагрузки среди сотрудников таким образом, чтобы все курсы были проведены, каждый преподаватель был занят только на одном виде работ, а затраты на заработную плату были минимальными.

№ п/п ФИО преподавателя Название курса
Английский для начинающих Деловой английский Подготовка к ЕГЭ Английский для путешествий
Королев Д. А.
Воробьева А. С.
Соловьев Н. А.
Павлова Р. Г.

1. Построим математическую модель задачи: определим переменные, целевую функцию и ограничения.

Пусть:

· x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34 – двоичные переменные, которые могут принимать два значения: 1, если преподаватель i назначается на чтение курса j и 0, если не назначается;

· z=100 x11 + 300 x12 + 110 x13 + 250 x14 + 120 x21 + 180 x22 +100 x23 +150 x24+ +200 x31+200 x32 + 80 x33 + 170 x34 +300 x41+250 x42 + 150 x43 + 230 x44– целевая функция, общая стоимость работ;

· x11 + x12 + x13 + х14=1,
x21 + x22 +x23+ х24=1,
x31 + x32 +x33+ х34=1,
x41 + x42 +x43+ х44=1,
x11 + x21 + x31 + х41=1,

x21 + x22 +x23+ х24=1,
x13 + x23 +x33+ х43=1,
x14 + x24 +x34+ х44=1
– ограничения (каждый преподаватель может быть задействован на чтении только одного курса и каждый курс должен быть проведен).

2. На основе математической модели на рабочем листе Excel создадим табличную модель (рис. 54).

Рис. 54. Задача о назначениях

3. Целевая функция в данном случае вычисляется по формуле =СУММПРОИЗВ(C6:F9;C15:F18).

4. Выделите целевую ячейку и запустите надстройку Поиск решения (Данные 4 Анализ 4 Поиск решения).

5. В появившемся диалоговом окне Поиск решения укажите адреса целевой ячейки, диапазон изменяемых ячеек и ограничения (рис. 55). Целевую ячейку установите равной минимальному значению. В диалоговом окне Параметры поиска решения установите флажки Линейная модель и Автоматическое масштабирование.

Рис. 55. Поиск решения

6. В диалоговом окне Поиск решения (рис. 55) нажмите кнопку Выполнить.

7. Получаем оптимальное решение задачи (рис. 56).

Рис. 56. Оптимальное решение задачи





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:



©2015- 2021 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.