Решение задач по методам оптимальных решений

Размещено на http://www.allbest.ru/

Задание №1. Решение задач оптимизации с помощью надстройки «Поиск решения» MS Excel

Цель работы: Построить математическую модель задачи линейного программирования и найти оптимальное решение с помощью надстройки «Поиск решения» MS Excel.

Фабрика выпускает три вида тканей, причем суточное плановое задание составляет не менее 90 м тканей первого вида, 70 м - второго и 60 м - третьего. Суточные ресурсы фабрики следующие: 780 единиц производственного оборудования; 850 единиц сырья; 790 единиц электроэнергии, расход которых на единицу сырья представлен в таблице:

Таблица 1

Цена 1 м ткани I вида равна 80 ден. ед., II вида -- 70 ден. ед., III вида -- 60 ден. ед. Сколько надо произвести ткани, чтобы получить максимальный доход?

Решение:

Обозначим через Х₁, Х₂, Х₃ виды ткани

Целевая функция - выражение, которое необходимо максимизировать:

80Х1 + 70Х2 + 60Х3max

Ограничения по ресурсам:

2Х₁ + 3Х₂ + 4Х₃ ? 780

1Х₁ + 4Х₂ + 5Х₃ ? 850

3Х₁ + 4Х₂ + 2Х₃ ? 790

Х₁?90, Х₂?70, Х₃?60

Вводим данные и формулы в рабочий лист Excel.

Рисунок 1. Исходные данные и формулы на листе Excel

В меню ДанныеПоиск решения указываем ограничения. Для ввода ограничений используем кнопку Добавить.

математический затраты excel оптимальный

Рисунок 2. Диалоговое окно «Параметры поиска решения» для указания ограничений.

Рисунок 3. Результат

Вывод: Целевая функция равна 21700.

Задание №2. Модели транспортных задач, решение в MS Excel

Цель работы: Составить математическую модель транспортной задачи и найти оптимальный план перевозок с помощью надстройки «Поиск решения» MS Excel, приобрести навыки решения задач целочисленного программирования.

Варианты заданий: Исходные данные приведены в таблице: внутри прямоугольника заданы транспортные затраты на перевозку единицы груза, слева указаны мощности поставщиков, сверху - мощности потребителей.

Таблица 1

Решение:

Обозначим через Х₁, Х₂, Х_3, Х₄ поставщиков

Ограничения для условия реализации всех мощностей:

Х₁₁ + Х₁₂ + Х₁₃ + Х₁₄ = 70

Х₂₁ + Х₂₂ + Х₂₃ + Х₂₄ = 80

Х₃₁ + Х₃₂ + Х₃₃ + Х₃₄ = 70

Х₄₁ + Х₄₂ + Х₄₃ + Х₄₄ = 110

Общий объем поставок 70+80+90+110=350.

Ограничения для удовлетворения спросов всех потребителей:

Х₁₁ + Х₂₁ + Х₃₁ + Х₄₁ = 150

Х₁₂ + Х₂₂ + Х₃₂ + Х₄₂ = 40

Х₁₃ + Х₂₃ + Х₃₃ + Х₄₃ = 110

Х₁₄ + Х₂₄ + Х₃₄ + Х₄₄ = 50

Общие потребности 150+40+110+50=350. Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует ввести дополнительное ограничение: Х ? 0.

Целевая функция:

9Х₁₁ + 5Х₁₂ + 10Х₁₃ + 7Х₁₄ + 11Х₂₁ + 8Х₂₂ + 9Х₂₃ + 6Х₂₄+ 7Х₃₁ + 6Х₃₂ + 5Х₃₃ + 4Х₃₄ + 6Х₄₁ + 4Х₄₂ + 3Х₄₃ + 2Х₄₄min

Вводим данные и формулы в рабочий лист Excel рис. 4.

В меню ДанныеПоиск решения указываем ограничения. Для ввода ограничений используем кнопку Добавить рис. 5.

Вывод: Минимальные суммарные затраты на перевозку груза равны 2060.

Рисунок 4. Исходные данные и формулы на листе Excel

Рисунок 5. Диалоговое окно «Поиск решения» для указания ограничений.

Рисунок 6. Результат

Задание №3. Методы решения транспортных задач

Три предприятия могут производить некоторую однородную продукцию в количествах соответственно равных 180, 350 и 20 ед. Эта продукция должна быть поставлена пяти потребителям в количествах равных 110, 90, 120, 80 и 150 ед. Затраты, связанные с производством и доставкой единицы продукции, задаются матрицей:

Таблица 3

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

Решение:

Таблица 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.

Размещено на Allbest.ru