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

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




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

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

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 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...