Компьютерное моделирование. Решение транспортной задачи, задачи линейного программирования и задачи о назначениях.. Компьютерное моделирование отчет. Задача Линейное программирование Задание

• Название: Задача Линейное программирование Задание
• Анкор: Компьютерное моделирование. Решение транспортной задачи, задачи линейного программирования и задачи о назначениях
• Дата: 13.06.2022
• Размер: 358.55 Kb.
• Имя файла: Компьютерное моделирование отчет.docx
• Тип: Задача; #587356

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

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

Задача 1. Линейное программирование

Задание:

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



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

Решение: Составим математическую модель задачи.

Обозначим переменные: Объем произведенных столов – x₁;Объем произведенных шкафов–x₂

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

0,2*х₁+0,1*х₂≤ 40

0,1*х₁+0,3*х₂≤ 60

1,2*х₁+1,5*х₂≤ 371,4 (1.1)

х₁≥ 0

х₂≥ 0

Прибыль от реализации продукции составит:

F = 6* х₁+8* х₂ (1.2)

Среди всех неотрицательных решений системы (1.1) линейных неравенств требуется найти такое, при котором функция прибыли F принимает максимальное значение Fmax.

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

1. 
   Занесем исходные данные в MS Excel (Рис. 1.1).
   

Рисунок 1.1 - Исходные данные задачи в MS Excel

2. 
   Далее сформируем шаблон для расчета (Рис. 1.2). В ячейках В32:С32 будут рассчитаны неизвестные нам оптимальные объемы производства. В ячейках В33:С33 содержится прибыль от реализации продукции. В ячейках В38:С40 отображен расход ресурсов на единицу производства изделия (столы и шкафы) предельно допустимые значения выпуска каждого вида.
   

В ячейке D33 происходит вычисление целевой функции с использованием функции =СУММПРОИЗВ(B33:C33;B32:C32).



Рисунок 1.2- Подготовка к решению задачи

В ячейки D38:D40 введены формулы для расчета ограничений по ресурсам.

3. 
   Выделим ячейку с формулой целевой функции. Запустим надстройку «Поиск решения». В диалоговом окне в поле ввода «Оптимизировать целевую функцию» уже содержится ячейка $D$33. Установим переключатель «Равной максимальному значению». В поле ввода «Изменяя ячейки» нужно указать неизвестные оптимальные объёмы выпуска продукции, т.е. выбрать ячейки $B$32:$C$32 (Рис. 3).
   

Рисунок 1.3 - Окно «Поиск решения»

4. 
   Щелкаем кнопку «Добавить». И в появившееся диалоговое окно «Добавление ограничения» пропишем необходимые ограничения по имеющимся ресурсам.
   

0,2*х₁+0,1*х₂≤ 40

0,1*х₁+0,3*х₂≤ 60

1,2*х₁+1,5*х₂≤ 371,4

х₁≥ 0

х₂≥ 0

5. 
   Нажимаем кнопку «Найти решение». И получим необходимые значения (Рис. 4).
   

Рисунок 1.4 - Результаты решения задачи

Таким образом, максимальная прибыль 1940 ден. ед. достигается путем производства 102 столов и 166 шкафов.

Задача 2. Транспортная задача

Задание:

Производственное объединение в своём составе имеет n филиалов Аi, i=1, 2, …, n, которые производят однородную продукцию в количестве аi, i=1, 2, …, n. Эту продукцию получают m потребителей Bj, j=1, 2, …, m, расположенных в разных местах. Их потребности соответственно равны bj, j=1, 2, …, m. Тарифы перевозок единицы продукции от каждого из филиалов потребителям задаются матрицей Сij (i=1, 2, …, n; j=1, 2, …, m).



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

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

Решение: Составим математическую модель задачи.

Обозначим переменные:

хᵢⱼ – количество товара, перевозимое с i-го филиала j-му потребителю (i = 1, 2, 3,4; j = 1, 2, 3, 4);

сᵢⱼ – тариф перевозки товара с i-го филиала j-му потребителю (i = 1, 2, 3, 4; j = 1, 2, 3, 4);

aᵢ – объем производства на i-м филиале (i = 1, 2, 3, 4);

bⱼ – объем потребления j-м потребителем (j = 1, 2, 3, 4).

Математическая постановка транспортной задачи состоит в определении минимального значения функции:



при условиях:







Функция (2.1) называется целевой функцией задачи. Поскольку переменные xᵢⱼ удовлетворяют системам линейных уравнений (2.2) и (2.3) и условию неотрицательности (2.4), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки. План X*=(x*ᵢⱼ)(i=1,2…m; j=1,2…n), при котором функция (2.1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, то есть выполняется равенство (2.5), то модель такой транспортной задачи будет закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.



В таком случае, решение транспортной задачи при помощи MS Excel будет иметь следующий алгоритм:

1. 
   Занесем исходные данные в MS Excel (Рис. 2.1).
   

Рисунок 2.1. - Исходные данные транспортной задачи в MS Excel

Проверяем – открытая модель или закрытая. Для этого необходимо проверить выполняется ли уравнение:



где ai - объем производства на i-м филиале (i = 1, 2, 3, 4); bj - объем потребления j-м потребителем (j = 1, 2, 3, 4).

В нашем случае модель закрытая (180+160+140+220 = 150+250+120+180 = 700).

2. 
   Обозначим Xij – количество товара, перевозимое от i-го поставщика j-му потребителю (i = 1, 2, 3, 4; j = 1, 2, 3, 4). Выделим под переменные Xij ячейки B13:E16 (Рис. 2.2).
   

Рисунок 2.2 - Подготовка к решению транспортной задачи

3. 
   В ячейках B17:E17 будем рассчитывать сумму поставок каждому потребителю. Для этого воспользуемся функцией СУММ. Аналогично в ячейках F13:F16 рассчитаем суммарные поставки каждого поставщика.
   
4. 
   В ячейку B20 запишем целевую функцию – суммарные затраты на осуществление всех поставок.
   

+12 +7 +4 →min

Эта функция вычисляется как сумма произведения величин поставок X_ij на соответствующую им стоимость. Для этого воспользуемся функцией СУММПРОИЗВ (Рис. 2.2).

5. 
   Выделим ячейку с формулой целевой функции. Запустим надстройку «Поиск решения». В диалоговом окне в поле ввода «Оптимизировать целевую функцию» уже содержится ячейка $В$20. Установим переключатель «Равной минимальному значению». В поле ввода «Изменяя ячейки» нужно указать величины поставок Xij, т.е. выбрать ячейки B13:E16 (Рис. 2.3).
   

Рисунок 2.3 - Окно «Поиск решения»

6. 
   Щелкаем кнопку «Добавить». И в появившееся диалоговое окно «Добавление ограничения» пропишем необходимые ограничения по суммарным спросу и мощности.
   
7. 
   Нажимаем кнопку «Найти решение». И получим необходимые значения (Рис. 2.4).
   

Рисунок 2.4 - Результаты решения задачи

В ячейке В20 указано 2490 ден.ед. Это минимальные затраты на перевозку. В ячейках B13:Е16 указаны значения для рассчитанного оптимального плана поставок:

1-й филиал должен доставить 60 единиц груза 2-му потребителю и 120 единиц груза 3-му потребителю.

2-й филиал должен доставить 10 единиц груза 1-му потребителю и 150 единиц груза 4-му потребителю.

3-й филиал должен доставить 140 единиц груза 1-му потребителю.

4-й филиал должен доставить 190 единиц груза 2-му потребителю и 30 единиц груза 4-му потребителю.

Задача 3. Задача о назначении

Задание:

На n типовых операций необходимо назначить n рабочих. Стоимость Cij выполнения i-м рабочим j-й операции приведена в таблице. Требуется найти такие назначения рабочих, при которых все операции были бы выполнены, каждый рабочий занят только на выполнении одной операции, суммарная стоимость работ при этом была минимальной.

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

Решение:

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



сᵢⱼ – время выполнения i-м рабочим j-й операции (i=1, 2, 3, 4, j=1, 2, 3, 4). Математическая постановка данной задачи состоит в определении минимального значения целевой функции:



при условиях, что:





С учетом исходных данных целевая функция имеет вид:

+40 +52 +72 →min

при условиях:








В таком случае, решение задачи о назначении при помощи MS Excel будет иметь следующий алгоритм:

1. 
   Занесем исходные данные в MS Excel (Рис. 3.1).
   

Рисунок 3.1 - Исходные данные задачи о назначении в MS Excel

Блок ячеек С28:F31 содержит затраты времени i-м рабочим на j-ю операцию

В ячейках G35:G38 суммарное количество рабочих в операциях.

В ячейках С35: F38 суммарное количество операций.

В ячейку С42 введем запишем целевую функцию – суммарные затраты на осуществление всех поставок.

+40 +52 +72 →min

Эта функция вычисляется как сумма произведения затрат времени на операцию на вакантных рабочих. Для этого воспользуемся функцией СУММПРОИЗВ (Рис. 3.1).

2. 
   Выделим ячейку с формулой целевой функции. Запустим надстройку «Поиск решения». В диалоговом окне в поле ввода «Оптимизировать целевую функцию» уже содержится ячейка $С$42. Установим переключатель «Равной минимальному значению». В поле ввода «Изменяя ячейки» нужно указать адреса ячеек со значениями искомых переменных С35:F38 (Рис. 3.2).
   

Рисунок 3.2 - Окно «Поиск решения»

3. 
   Щелкаем кнопку «Добавить». И в появившееся диалоговое окно «Добавление ограничения» пропишем необходимые ограничения:
   

А также обязательное ограничение на переменные, которые принимают значения 1 или 0 - выбрать в раскрывающемся списке «бин», в поле Ограничение автоматически отобразится бинарное (Рис. 3.2).

3. 
   Нажимаем кнопку «Найти решение». И получим необходимые значения (Рис. 3.3).
   

Рисунок 3.3 - Результаты решения задачи

В результате решения задачи получили суммарное время выполнения всех операций 165 ед. При этом распределение рабочих по операциям следующее:

1-й рабочий выполняет III операцию; 2-й – II операцию; 3-й – IV операцию; 4-й – I операцию.

Список литературы

1. 
   Акулич, И. Л. Математическое программирование в примерах и задачах: учеб. пособие / И. Л. Акулич. – СПб.: Лань, 2009. – 532 с.
   
2. 
   Иванов, И. Microsoft Excel 2010 для квалифицированного пользователя/ И. Иванов. – М.: Академия АЙТИ, 2011. – 244 с.
   
3. 
   Мелихова, Е. В. Математическое моделирование и анализ в АПК: метод. рекомендации для выполнения лабораторных и самостоятельных работ / Е. В. Мелихова, Н. Ю. Мильченко; ФГБОУ ВО Волгогр. ГАУ. - Волгоград: Волгоградский ГАУ, 2017. - 80 с.
   
4. 
   Решение задач оптимизации управления с помощью MS Excel 2010//НОУ «ИНТУИТ» [Электронный ресурс]. – Режим доступа: http://www.intuit.ru/studies/courses/4751/1020/info
   
5. 
   Справка и инструкции по Excel // Поддержка по Microsoft Office [Электронный ресурс]. – Режим доступа: http://office.microsoft.com/ruru/excel-help