Задание №1. Решение задач оптимизации с помощью надстройки «Поиск решения» MS Excel
Цель работы: Построить математическую модель задачи линейного программирования и найти оптимальное решение с помощью надстройки «Поиск решения» MS Excel.
Фабрика выпускает три вида тканей, причем суточное плановое задание составляет не менее 90 м тканей первого вида, 70 м - второго и 60 м - третьего. Суточные ресурсы фабрики следующие: 780 единиц производственного оборудования; 850 единиц сырья; 790 единиц электроэнергии, расход которых на единицу сырья представлен в таблице:
Таблица 1
|
Ресурсы |
Ткани |
|||
|
I |
II |
III |
||
|
Оборудование |
2 |
3 |
4 |
|
|
Сырьё |
1 |
4 |
5 |
|
|
Электроэнергия |
3 |
4 |
2 |
Цена 1 м ткани I вида равна 80 ден. ед., II вида -- 70 ден. ед., III вида -- 60 ден. ед. Сколько надо произвести ткани, чтобы получить максимальный доход?
Решение:
Обозначим через Х1, Х2, Х3 виды ткани
Целевая функция - выражение, которое необходимо максимизировать:
80Х1 + 70Х2 + 60Х3max
Ограничения по ресурсам:
2Х1 + 3Х2 + 4Х3 ? 780
1Х1 + 4Х2 + 5Х3 ? 850
3Х1 + 4Х2 + 2Х3 ? 790
Х1?90, Х2?70, Х3?60
Вводим данные и формулы в рабочий лист Excel.
Рисунок 1. Исходные данные и формулы на листе Excel
В меню ДанныеПоиск решения указываем ограничения. Для ввода ограничений используем кнопку Добавить.
математический затраты excel оптимальный
Рисунок 2. Диалоговое окно «Параметры поиска решения» для указания ограничений.
Рисунок 3. Результат
Вывод: Целевая функция равна 21700.
Задание №2. Модели транспортных задач, решение в MS Excel
Цель работы: Составить математическую модель транспортной задачи и найти оптимальный план перевозок с помощью надстройки «Поиск решения» MS Excel, приобрести навыки решения задач целочисленного программирования.
Варианты заданий: Исходные данные приведены в таблице: внутри прямоугольника заданы транспортные затраты на перевозку единицы груза, слева указаны мощности поставщиков, сверху - мощности потребителей.
Таблица 1
|
Потребители Поставщики |
150 |
40 |
110 |
50 |
|
|
70 |
9 |
5 |
10 |
7 |
|
|
80 |
11 |
8 |
9 |
6 |
|
|
90 |
7 |
6 |
5 |
4 |
|
|
110 |
6 |
4 |
3 |
2 |
Решение:
Обозначим через Х1, Х2, Х3, Х4 поставщиков
Ограничения для условия реализации всех мощностей:
Х11 + Х12 + Х13 + Х14 = 70
Х21 + Х22 + Х23 + Х24 = 80
Х31 + Х32 + Х33 + Х34 = 70
Х41 + Х42 + Х43 + Х44 = 110
Общий объем поставок 70+80+90+110=350.
Ограничения для удовлетворения спросов всех потребителей:
Х11 + Х21 + Х31 + Х41 = 150
Х12 + Х22 + Х32 + Х42 = 40
Х13 + Х23 + Х33 + Х43 = 110
Х14 + Х24 + Х34 + Х44 = 50
Общие потребности 150+40+110+50=350. Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует ввести дополнительное ограничение: Х ? 0.
Целевая функция:
9Х11 + 5Х12 + 10Х13 + 7Х14 + 11Х21 + 8Х22 + 9Х23 + 6Х24+ 7Х31 + 6Х32 + 5Х33 + 4Х34 + 6Х41 + 4Х42 + 3Х43 + 2Х44min
Вводим данные и формулы в рабочий лист Excel рис. 4.
В меню ДанныеПоиск решения указываем ограничения. Для ввода ограничений используем кнопку Добавить рис. 5.
Вывод: Минимальные суммарные затраты на перевозку груза равны 2060.
Рисунок 4. Исходные данные и формулы на листе Excel
Рисунок 5. Диалоговое окно «Поиск решения» для указания ограничений.
Рисунок 6. Результат
Задание №3. Методы решения транспортных задач
Три предприятия могут производить некоторую однородную продукцию в количествах соответственно равных 180, 350 и 20 ед. Эта продукция должна быть поставлена пяти потребителям в количествах равных 110, 90, 120, 80 и 150 ед. Затраты, связанные с производством и доставкой единицы продукции, задаются матрицей:
Таблица 3
|
7 |
12 |
4 |
6 |
5 |
|
|
1 |
8 |
6 |
5 |
3 |
|
|
6 |
13 |
8 |
7 |
4 |
Составить такой план прикрепления потребителей к поставщикам, при котором общие затраты являются минимальными.
Решение:
Таблица 4
Таблица 5 Метод северо-западного угла
F=7*110+12*70+8*20+6*120+5*80+3*130+4*20=3360
Таблица 6 Метод минимального элемента
F=12*60+4*120+1*110+8*10+5*80+3*150+13*20=2420
Таблица 7 Метод аппроксимации Фогеля
F=4*120+6*60+1*110+8*90+5*20+3*130+4*20=2240.