Задачи оптимизации (презентация к уроку)

Задача оптимизации имеет оптимальное решение, если выполняются два требования:

• имеется критерий , показывающий, в каком смысле принимаемое решение должно быть оптимальным
• допустимые решения существуют

Процесс решения задачи оптимизации состоит из следующих этапов:

• Построение математической модели
• Задание ограничений
• Задание критерия оптимизации
• Выбор поисковых переменных
• Выбор метода оптимизации
• Решение задачи оптимизации
• Анализ результатов решения

Решение оптимизационных задач

Задача 1 . Задача о перевозках

В городе имеются два склада муки и два хлебозавода . Ежедневно с 1- го склада вывозится 50 т муки, со 2 - го — 70 т . Эта мука доставляется на хлебозаводы , причем 1- й получает 40 т , 2 - й — 80 т . Допустим, что перевозка одной тонны муки с 1- го склада на 1- й завод составляет 120 руб ., с 1- го склада на 2 - й завод — 160 руб ., со 2 - го склада на 1- й завод - 80 руб. и со 2 - го склада на 2 - й завод - 100 руб.

Как нужно спланировать перевозки, чтобы их общая стоимость за один день была минимальной ?

X 4 по 1 0 0 руб .

X 3 по 8 0 руб .

X 2 по 1 6 0 руб.

Пусть x 1- количество муки , которое нужно перевезти с 1- го склада на 1- й завод , х2 - с 1- го склада на 2- й завод, х3 - со 2- го склада на 1- й завод , x 4 - со 2 - го склада на 2- й завод.

X1 по 120 руб.

1 склад муки

50 тонн

1 хлебозавод

40 тонн

2 хлебозавод

80 тонн

2 склад муки

70 тонн

0, для i = 1, 2, 3, 4 (2) В качестве критерия оптимизации выбираем общую стоимость перевозок: F ( X 1, X 2, X 3, X 4 ) = 120* X 1 + 160* X 2 + 80* X 3 + 100* X 4 (3) " width="640"

По условию задачи составим систему уравнений:

x 1+ x 2=50;

• x 1+ x 2=50;

x 3+ x 4=70;

x 1+ x 3=40; (1)

x 2+ x 4=80;

• x 3+ x 4=70; x 1+ x 3=40; (1) x 2+ x 4=80;

Где xi 0, для i = 1, 2, 3, 4 (2)

В качестве критерия оптимизации выбираем общую стоимость перевозок:

F ( X 1, X 2, X 3, X 4 ) = 120* X 1 + 160* X 2 + 80* X 3 + 100* X 4

(3)

Постановка задачи

Найти min F ( X 1, X 2, X 3, X 4) при ограничениях ( 1 ) и ( 2 )

Т.е. надо найти значения x 1, х2, х3, x 4 , удовлетворяющие ограничениям ( 1 ) и ( 2 ), минимизирующие критерий ( 3 )

Подставив ( 4 ) в ( 3 ),

получим: F ( X 1, X 2, X 3, X 4 ) = 14200 - 20 x 1 ( 5 )

Так как все х i  0 , то, используя ( 4 ), запишем ограничения на x 1 в виде следующих неравенств:

x 1  0

50- x 1  0

40- x 1  0

30+ x 1  0

Отсюда следует, что 0  x 1  40 ( 6 )

Теперь исходная задача оптимизации сводится к следующей:

надо найти x 1 из интервала ( 6 ), при котором функция ( 5 ) примет минимальное значение

Уравнение ( 5 ) — это уравнение прямой

Эта функция непрерывно убывающая и имеет минимум на границе интервала изменения аргумента

т. е. при x 1 min = 40 т.

Значение F min =134 00 руб.

Задача 2. Рациональное составление комбикорма

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

В единицах веса разных зерновых культур содержится разное количество (в некоторых единицах) каждого из

4-x питательных компонентов (ингредиентов).

Управляющий фермой стремится определить, какая из всех возможных смесей является самой дешевой.

Выбирается некоторый период планирования ( например, две недели ). Зерно на этот период закупается с учетом потребности в питательных компонентах.

Все данные, относящиеся к рассматриваемой задаче, приведены в табл. 1 и 2.

Таблица 1

Ингредиенты

Содержание ингредиентов в единице веса зерна

Зерно 1

Ингредиент А

Ингредиент В

Зерно 2

2

Ингредиент С

1

3

Минимальная суммарная потребность в ингредиентах на период планирования

Зерно 3

7

Ингредиент D

5

1

0

1250

3

0,6

250

0

0,25

900

1

232,5

Таблица 2

Зерно 1

Цена ( в долл .)

единицы зерна

Зерно 2

41

Вес зерна на период планирования

Зерно 3

35

X 1

96

X 2

X 3

Постановка задачи

Требуется минимизировать затраты на покупку зерна, т. е. найти min ( 41 x 1 + 35 x 2 + 96 х з ) (1)

при наличии ограничений :

2 x 1 + 3 x 2 + 7х з  1250

x 1 + x 2  250 5 x 1 + 3 x 2  900 0,6 x 1 + 0,25 x 2 + 1х з  232,5 ( 2 )

x 1  0

x 2  0 х з  0