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

Предмет рассматривает специальные модели математического программирования (оптимизационные задачи с ограничениями).

В модели математического программирования всегда входят 3 элемента:

1. Переменные решения (при рассмотрении задачи эти величины можно менять).

2. Целевая функция (математически-формализованная цель принятия управленческого решения).

3. Ограничения (математически-формализованные, в виде уравнений или неравенств, условия ограниченности ресурсов).

Задача 1 «Мебельный Цех»

Мебельный цех производит шкафы и тумбы. Для производства шкафа требуется 3,5 м² ДСП, 1 м² стекла, 1 трудодень. Для производства тумбы 1 м² ДСП, 2 м² стекла, 1 трудодень. Прибыль от продажи шкафа планируется 200 у.е., тумба принесет 100 у.е. За смену можно израсходовать 350 м² ДСП, 240 м² стекла, на предприятии работает 150 человек.

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

1) Предложим произвести 100 шкафов и 0 тумб.

Рассчитаем прибыль:

Р=200у.е.*100шт=20000

Обсудим допустимость плана по ресурсам:

ДСП=3.5 м² *100=350 м² ≤ 350!

Стекло = 1 м² *100=100 м² ≤ 240

Труд = 1 тд * 100= 100 ≤ 150

2) Предложим произвести 90 шкафов и 35 тумб.

Р=200*90+100*35=21500 у.е.

ДСП =3.5*90+1*35=350 м² ≤ 350!

Стекло = 1*90+2*35=160 м² ≤ 240

Труд = 1*90+1*35=125 тд ≤ 150

ПРОБЛЕМЫ:

Возможных производственных планов бесконечно много - оценить их прибыльность и допустимость по ресурсам не представляется возможным.

Применим метод математического программирования:

1. Составим математическую модель ситуации:

1) Назначим переменные решения:

Х₁ (шт) – выпуск шкафов за смену,

Х₂ (шт) –выпуск тумб.

2) Составим целевую функцию:

Р=200*Х₁+100*Х₂→ Мах

3) Назначим ограничения:

ДСП=3.5*Х₁+1*Х₂ ≤350

Стекло =1*Х₁+2*Х₂ ≤240

Труд =1*Х₁+1*Х₂ ≤150

Х₁,Х₂ ≥0

2. Решить задачу геометрическим методом:

1) Построим многоугольник допустимых производственных планов:

ДСП=3.5х₁ +1х₂ ≤350 –полуплоскость, начать построение необходимо с границы:

3.5х₁ +1х₂ =350,

х₁ =0; х₂=350

х₁ =100; х₂=0

Рассмотрим ограничение по стеклу:

1х₁ +2х₂≤240 –полуплоскость, построение начать с границы:

1х₁ +2х₂=240

х₁ =0; х₂=120

х₁ =240; х₂=0

Рассмотрим ограничение по труду:

1х₁ +1х₂≤150 –полуплоскость, построим границу:

1х₁ +1х₂=150

х₁=0; х₂=150

х₁ =150; х₂=0

2) Найдем оптимальный производственный план:

Утверждение: Оптимальный производственныйплан находится в одной из угловых точек. Если план находится в угловой точке, то в данном случае два вида сырья расходуются полностью –план претендует на оптимальность по прибыли.

Нахождение координат угловых точек с последующим вычислением значения целевой функции для решения прикладных задач неприемлемо. В реальных задачах переменных ориентировочно около 20, ограничений около 30, угловых точек около триллиона, подсчет займет уйму времени, поэтому для анализа подключают целевую функцию, точнее её линии уровня.

Р=200 х₁ +100х₂→Мах

Допустим нас устраивает прибыль в 10000 у.е.

Р=10000у.е.

10000=200 х₁ +100х₂ -прямая на плоскости

х₁ =0; х₂ =100

х₁ =50; х₂=0

Возьмем уровень прибыли в 15000 у.е.

Р=15000у.е.

15000= 200х₁ +100х₂

х₁ =0; х₂=150

х₁ =75; х₂=0

Перечислим свойства линий уровня прибыли:

Они параллельны, при сдвиге линий уровня вправо прибыль возрастает.

Итак выбираем одну линию уровня прибыли и производим параллельный перенос вправо, тем самым находя оптимальную угловую точку.

х₁ =80; х₂=70.

Найдем координаты угловой точки аналитически, точка на пересечении первой (ДСП) и третьей (труд) границы.

{3.5 х₁ +1х₂=350

{1х₁ +1х₂=150

х₂=150- х₁

3,5х₁ +150-х₁ =350

2,5х₁ =250

х₁ =200/2,5

х₁ =80

х₂=150-80

х₂=70

Итак: математическое моделирование рекомендует шкафов производить 80, тумб 70, сырья должно хватить, а прибыль будет максимальной!

Р=200*80+100*70=16000+7000=23000 у.е.

Проверим план на допустимость:

ДСП=3,5*80+1*70=280+70=350 ≤350!

Стекло=1*80+2*70=80+140=220 ≤240!

Труд=1*80+1*70=150 ≤150!

Заключительные замечания:

1. Геометрический метод применим только для простых задач математического программирования: переменных 2, ограничений 3.

2. Для решения прикладных задач (переменных решения >3) применяется алгоритм симплекс метода (интеллектуальный обход угловых точек: переход из одной точки в другую осуществляется только при улучшении целевой функции).

Рассмотрим другие задачи:

Задача 2 Компания Reddy Mikks

Компания Reddy Mikks производит краску для внутренних и наружных работ из сырья двух типов: М1 и М2. Следующая таблица представляет основные данные задачи:

Отдел маркетинга компании ограничил производство краски для внутренних работ до 2т. (из-за отсутствия надлежащего спроса), а так же поставил условие, чтобы ежедневное производство краски для внутренних работ не превышало более, чем на тонну аналогичный показатель производства краски для внешних работ. Компания хочет определить оптимальное (наилучшее) соотношение между видами выпускаемой продукции для максимизации ежедневного дохода.

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

1. Назначим переменные решения:

х₁ = выпуск краски для наружных работ,

х₂ = выпуск краски для внутренних работ.

2. Составим целевую функцию:

Р=5х₁ +4х₂ →Мах

3. Назначим ограничения:

М1: 6 х₁ +4х₂ ≤24

М2: 1х₁ +2х₂ ≤6

Ограничения отдела маркетинга:

х₁ ≤2

х₂ ≤1+х₁

х₁ ,х₂ ≥0

В задаче 2 переменных решения, в принципе, возможно решить геометрически.

Начнем построение с границ:

1) 6х₁+4х₂=24

Х₁=0, х₂=6;

Х₁=4, х₂=0

2) 1х₁+2х₂=6

Х₁=0, х₂=3;

Х1=6, х₂=0

Маркетинговые ограничения:

3) Х₁=2;

Х₂=х₁+1, х₂=1+2, х₂=3

Предположим, прибыль равна 20:

4) Р = 5х₁+4х₂=20

Х₁=0, х₂=5;

Х₁=4, х₂=0.

Компьютерное решение:

Итак: математическое моделирование рекомендует производить одинаковое количество краски как для внутренних, так и для наружных работ -по 2 тонны, сырья должно хватить, а прибыль будет максимальной!

Задача 3 «На кондитерской фабрике»

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

Мастер, используя свой 20-летний опыт, предлагает на глазок выпустить по 200 пакетов каждого продукта, утверждая, что ресурсов «должно хватить», а прибыль получится, очевидно, 1080 у.е.

Сын владельца фабрики, только что закончивший УИФР. Утверждает, что такие проблемы надо решать не на глазок, а с помощью линейного программирования. Умиленный отец обещает сыну всю прибыль сверх 1080 у.е., если он предложит лучший план, чем многоопытный мастер.

1. Обсудим план мастера:

Мастер предлагает производить по 200 пакетов конфет каждого вида. Проверим план на прибыльность:

Р=200*1+200*0.7+200*1.1+200*2+200*0.6=200+140+220+400+120=1080у.е.

Проверим план мастера на допустимость по ресурсам:

Т.ш.=200*0.8+200*0.5+200*1+200*2+200*1.1=160+100+200+400+220=1080кг≤1411

2. Применим научный подход, составим математическую модель задачи:

1) Назначим переменные решения:

Х₁-выпуск конфет «Ореховый звон»

Х₂-выпуск «Райский вкус»

Х₃-выпуск «батончиков»

Х₄-выпуск конфет «Белка»

Х₅-выпуск конфет «Ромашка»

2) Назначим целевую функцию:

Р=1х₁+0.7х₂+1.1х₃+2х₄+0.6х₅→Мах

3) Составим ограничения:

Т.Ш.=0.8х₁+0.5х₂+1х₃+2х₄+1.1х₅≤1411

С.Ш.=0.2х₁+0.1х₂+0.1х₃+0.1х₄+0.2х₅≤149

Сахар=0.3х₁+0.4х₂+0.6х₃+1.3х₄+0.05х₅≤815.5

Карамель=0.2х₁+0.3х₂+0.3х₃+0.7х₄+0.5х₅≤466

Орехи=0.7х₁+0.1х₂+0.9х₃+1.5х₄+0х₅≤1080

Х₁, х₂, х₃, х₄, х₅≥0

Геометрически задача не решается, решается она на компьютере Симплекс методом.

Итак: математическое моделирование рекомендует конфеты «Ореховый Звон» производить в количестве 454 пакета, «Райский вкус»-59 пакетов, «Батончики» исключить из производства, конфеты «Белка» -504 пакета, «Ромашка»-9 пакетов, сырья должно хватить, а прибыль будет максимальной!

Поиск по сайту: