Математическая модель задачи.
Обозначим за x 1 и x 2 количество изделий А и В в оптимальном плане производства.
Решение задачи в MS Excel.
Модели всех задач на оптимизацию состоят из следующих элементов:
1. Переменные - неизвестные величины, которые нужно найти при решении задачи.
2. Целевая функция - величина, которая зависит от переменных и является целью, ключевым показателем эффективности или оптимальности модели.
3. Ограничения - условия, которым должны удовлетворять переменные.
В качестве переменных х1 и х2 будем использовать ячейки E 2 и E 3 соответственно. Для значения целевой функции будем использовать ячейку E 9:
Далее выбираем пункт меню Данные/Поиск решения:
Перед нами открывается диалоговое окно Поиск решения. В нём указываем, что нам необходимо установить ячейку $ E $9 максимальному значению, изменяя ячейки $ E $2:$ E $3. Далее нажимаем кнопку Добавить для добавления ограничений. И добавляем следующие ограничения:
ограничения по фонду рабочего времени
ограничения по минимальному плану производства
количество изделий должно быть целым числом
После ввода каждого ограничения нажимаем кнопку Добавить. После ввода последнего ограничения нажимаем кнопку OK. И диалоговое окно Поиск решения принимает следующий вид:
Нажимаем кнопку Выполнить. И перед нами открывается диалоговое окно Результаты поиска решения:
|
|
Выбираем создание отчёта по результатам. Отчеты по устойчивости и пределам не создаются при использовании целочисленных ограничений на переменные. После нажатия кнопки OK в рабочей книге появляется новый лист с названием Отчет по результатам 1 содержащий отчёт по результатам, и получаем следующие результаты:
Деталь | Затраты времени на производсво одной детали, ч. | Прибыль от реализации одной детали, ден. ед. | Минимальный план выпуска, штук | Оптимальный план производства, штук | |||
А | 3 | 80 | 100 | 100 | |||
В | 2 | 60 | 200 | 300 | |||
|
|
| |||||
Фонд рабочего времени, человеко-часов |
|
| |||||
составляет |
| 900 |
|
| |||
задействовано |
| 900 |
|
| |||
|
|
|
|
| |||
Максимальная прибыль от реализации, ден. ед. | 26000 | ||||||
Отчёт по результатам.
Целевая ячейка (Максимум) |
|
|
|
| ||||
| Ячейка | Имя | Исходное значение | Результат |
|
| ||
| $E$9 | Максимальная прибыль от реализации, ден. ед. Оптимальный план производства, штук | 0 | 26000 |
|
| ||
|
|
|
|
|
| |||
|
|
|
|
|
| |||
Изменяемые ячейки
|
|
|
|
| ||||
| Ячейка | Имя | Исходное значение | Результат |
|
| ||
| $E$2 | А Оптимальный план производства, штук | 0 | 100 |
|
| ||
| $E$3 | В Оптимальный план производства, штук | 0 | 300 |
|
| ||
|
|
|
|
|
| |||
|
|
|
|
|
| |||
Ограничения |
|
|
|
| ||||
| Ячейка | Имя | Значение | Формула | Статус | Разница | ||
| $C$7 | задействовано Прибыль от реализации одной детали, ден. ед. | 900 | $C$7<=$C$6 | связанное | 0 | ||
| $D$2 | А Минимальный план выпуска, штук | 100 | $D$2<=$E$2 | связанное | 0 | ||
| $D$3 | В Минимальный план выпуска, штук | 200 | $D$3<=$E$3 | не связан. | 100 | ||
| $E$2 | А Оптимальный план производства, штук | 100 | $E$2=целое | связанное | 0 | ||
| $E$3 | В Оптимальный план производства, штук | 300 | $E$3=целое | связанное | 0 |
1.1.4
Анализ отчета показывает, что фонд рабочего времени задействован на 100%.
Электронная таблица в режиме формул.
Электронная таблица в режиме значений.
Пример 2.Компания «Атлант» хранит свою продукцию на трех складах (первом, втором и третьем), расположенных в разных частях города. На этих складах хранится продукция в количествах 1000, 3000 и 2500 штук соответственно. Продукцию необходимо доставить четырем оптовым покупателям «Урал», «Купец», «Гелиос» и «Меркурий» с минимальными затратами, заявки которых составляют 1300, 800, 2700 и 1700 штук соответственно. Склады оптовых покупателей также расположены в разных частях города. Стоимости (в рублях) доставки одной штуки продукции со складов компании на склады покупателей показаны в следующей таблице7.
|
|
Таблица 7
Стоимость доставки продукции
Склады компании | Оптовые покупатели | |||
«Урал» | «Купец» | «Гелиос» | «Меркурий» | |
№1 | 50 | 150 | 60 | 75 |
№2 | 100 | 30 | 100 | 40 |
№3 | 70 | 180 | 210 | 120 |
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+ +70 x31+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 (рис. 65).
Рис. 65. Сбалансированная модель
5. Последняя таблица не обязательна. Целевую функцию можно было вычислить по формуле:
=СУММПРОИЗВ(В4:Е6;В13:Е15).
6. Выделите целевую ячейку и запустите надстройку Поиск решения (Данные 4 Анализ 4 Поиск решения).
7. В появившемся диалоговом окне Поиск решения укажите адреса целевой ячейки, диапазон изменяемых ячеек и ограничения (рис. 66). Целевую ячейку установите равной минимальному значению.
Рис. 66. Диалоговое окно «Поиск решения»
8. В диалоговом окне параметры Поиска решенияустановите флажки Линейная модель, Неотрицательные значения и Автоматическое масштабирование.
9. В диалоговом окне Поиск решения нажмите кнопку Выполнить.
10. Получаем оптимальное решение задачи (рис. 67).
Рис. 67. Оптимальное решение задачи
11. Скопируйте полученную табличную модель на Лист 2 рабочей книги и переименуйте его в Несбалансированная задача.
12. Решим эту же задачу, немного изменив условие.
13. Пусть на складе №1 хранится не 1000 штук продукции, а 500. В таком случае на трех складах компании хранится 6000 штук продукции, покупатели по-прежнему заказывают 6500 штук. Перед нами транспортная задача с дефицитом.
14. Несбалансированная задача решается аналогично сбалансированной. Изменения коснуться только ограничений. Причем в ограничениях для складов покупателей знак «=» заменяется знаком « ≤ ».
15. После выполнения надстройки Поиск решения (рис. 68) получаем, что покупатель «Гелиос» недополучит 500 ед. продукции, а минимальные транспортные расходы составят 479 000 (рис. 69).
Рис. 68. Поиск решения
Рис. 69. Оптимальное решение задачи
16. Покажите работу преподавателю.
Частным случаем транспортной задачи является задача о назначениях. В общем виде она формулируется следующим образом: имеется n различных работ и n рабочих. Известны стоимости выполнения каждого вида работ каждым работником. Необходимо так составить штатное расписание, чтобы все работы были выполнены, на выполнение каждой работы назначался только один работник, а затраты на заработную плату были минимальными. В данном случае задача является сбалансированной, так как количество работников равно количеству работ. Ограничения записываются в виде следующих равенств.
x11 + x12 + …+ x1 n=1,
x21 + x22 +… + x2 n=1,
…
xn1+ xn2 + … + xnn=1 – ограничения для работников (каждый работник может выполнять только один вид работ).
x11 + x21 + …+ xn1=1,
x12 + x22 +… +xn2=1,
…
x1n+x2n + … + xnn=1 – ограничения для работ (каждый вид работ может быть выполнен только одним работником).
xij – это двоичные переменные, которые могут принимать только два значения: 1, если работник i назначается на выполнение работы j и 0, если не назначается.
Решение задачи о назначениях рассмотрим на примере.
Пример 3. В лингвистическом центре работают 4 преподавателя по следующим направлениям: «Английский для начинающих», «Деловой английский», «Подготовка к ЕГЭ» и «Английский для путешествий». Стоимость академического часа работы каждого преподавателя по каждому курсу представлена в таблице 8. Составьте оптимальное распределение нагрузки среди сотрудников таким образом, чтобы все курсы были проведены, каждый преподаватель был занят только на одном виде работ, а затраты на заработную плату были минимальными.
Таблица 8
Стоимость обучения
№ п/п | ФИО преподавателя | Название курса | |||
Английский для начинающих | Деловой английский | Подготовка к ЕГЭ | Английский для путешествий | ||
1 | Королев Д. А. | 100 | 300 | 110 | 250 |
2 | Воробьева А. С. | 120 | 180 | 100 | 150 |
3 | Соловьев Н. А. | 200 | 200 | 80 | 170 |
4 | Павлова Р. Г. | 300 | 250 | 150 | 230 |
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 создадим табличную модель (рис. 70).
Рис. 70. Задача о назначениях
3. Целевая функция в данном случае вычисляется по формуле =СУММПРОИЗВ(C6:F9;C15:F18).
4. Выделите целевую ячейку и запустите надстройку Поиск решения (Данные 4 Анализ 4 Поиск решения).
5. В появившемся диалоговом окне Поиск решения укажите адреса целевой ячейки, диапазон изменяемых ячеек и ограничения (рис. 71). Целевую ячейку установите равной минимальному значению. В диалоговом окне Параметры поиска решения установите флажки Линейная модель и Автоматическое масштабирование.
6. В диалоговом окне Поиск решения (рис. 71) нажмите кнопку Выполнить.
Рис. 71. Поиск решения
7. Получаем оптимальное решение задачи (рис. 72).
Рис. 72. Оптимальное решение задачи
Дата добавления: 2018-11-24; просмотров: 377; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!