MathematicalOptimization

Санкт-Петербургский политехнический университет Петра Великого Институт Информационных Технологий и Управления

Кафедра компьютерных систем и программных технологий

Курсовая работа

Дисциплина: Методы оптимизации

Тема: Формулировка и решение задачи выбора оптимального решения с использованием различных математических моделей

Санкт-Петербург

2015

Содержание

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

1.2Выделение главного критерия . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1Максимизация выручки . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.2Максимизация прибыли . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3Свертка критериев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4Максимин или минимакс . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.5Метод последовательных уступок . . . . . . . . . . . . . . . . . . . . . . . . . 10

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

2.2Ход работы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3Результат . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

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

3.2Марковская модель принятия решений . . . . . . . . . . . . . . . . . . . . . . 25

3.3Метод итерации по стратегиям . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.4Метод линейного программирования . . . . . . . . . . . . . . . . . . . . . . . 28

4Поиск оптимальных параметров сети систем массового обслуживания. 32

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

4.2Алгоритм решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.3 Решение по алгоритму . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.4Решение дискретным линейным методом программирования . . . . . . . . . 38

2

1Варианты формализации многокритериальной задачи и их решение с использованием Optimization Toolbox системы Matlab.

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

Мебельная фабрика выпускает столы, стулья, бюро и книжные шкафы. При изготовлении используются два типа досок, причем фабрика имеет в наличии 1500 м досок первого типа и 1000 м досок второго типа. Кроме того, заданы трудовые ресурсы в количестве 800 чел/час. В таблице приводятся нормативы затрат каждого из видов ресурсов на изготовление 1 ед изделия и прибыль от реализации 1 ед изделия.

Таблица 1: Нормативы затрат ресурсов на единицу изделия

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

∙стол – 32 руб;

∙стул – 15 руб;

∙бюро – 12 руб;

∙книжный шкаф – 80 руб.

Вотчёте необходимо описать:

1.Осуществление перехода от многокритериальной задачи к однокритериальной с использованием различных подходов.

2.Решение задачи стохастического программирования для одной из однокритериаль-

ных задач, превратив детерминированное ограничение в вероятностное по схеме:

∑

( − ≤ 0) ≥

=1

3

Менять в следующем диапазоне 0.1 ≤ ≤ 0.9.

Считать случайной величиной или элементы { } -й строки матрицы { } (по выбору).

1.2Выделение главного критерия

Выбирается один из критериев, например , который наиболее полно отражает цель принятия решений. Остальные критерии учитываются только с точки зрения возможного указания их нижних границ ( ) ≥ , ̸= . Таким образом, исходная задача многокритериального принятия решений заменяется однокритериальной задачей с критерием , т.е.

* = arg max ( ), при ограничениях ( ) ≥ , ̸= .

Критерии:

∙(12 1 + 5 2 + 15 3 + 10 4) (прибыль)

∙(32 1 + 15 2 + 12 3 + 80 4) (выручка) Ограничения:

∙5 1 + 2 + 9 3 + 12 4 ≤ 1500 (доски первого типа)

∙2 1 + 3 2 + 4 3 + 1 4 ≤ 1000 (доски второго типа)

∙3 1 + 2 2 + 5 3 + 1 4 ≤ 800 (трудовые ресурсы)

1.2.1Максимизация выручки

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

= (−32 1 − 15 2 − 12 3 − 80 4)

Начальные условия:

0

⎜00 = 0

0

Ограничения:

4

5 1 9 12

2 3 4 1

3 2 5 1

0 0 0 −1

1500

1000

800

= 0

0

0

Результат:

∙ 1 = −0, 0000

5

∙2 = 300, 0000

∙3 = 0

∙4 = 100, 0000

∙1 = −2500

∙2 = −12500

1.2.2Максимизация прибыли

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

= (−12 1 − 5 2 − 15 3 − 10 4)

1500

1000

800

−12500

6

Листинг 2: Поиск оптимального решения для максимизация прибыли

Результат:

∙1 = 261, 2903

∙2 = 0

∙3 = 0, 0000

∙4 = 16, 1290

∙1 = −3296, 8

∙2 = −9651, 6

1.3Свертка критериев

Максимизируется критерий объединенной операции, получающийся в результате суммиро-

вания всех частных критериев:

( ) = ∑ ( )

=1

7

( ) = ( )*

* - оптимальное решение задачи по каждому критерию в отдельности, 1+ 2+· · ·+ = 1.

Листинг 3: Свертка критериев

1 x0 =[0;

20 ;

30 ;

40 ] ;

9−1 0 0 0 ;

100 −1 0 0 ;

110 0 −1 0 ;

12 0 0 0 −1];

В fmincon передается сумма нормированных значений (первый критерий делится на f1, второй на f2), каждое из которых умножено на определенный весовой коэффициент. Результат:

∙1 = 166, 4573

∙2 = 127, 8185

8

∙3 = −0, 0000

∙4 = 44, 9913

∙= −0, 9019 (суммарное)

1.4Максимин или минимакс

Максиминную свертку представим в следующем виде: ( ) = min ( )

Решение * является наилучшим, если для всех выполняется условие ( *) ≥ ( ), или* = arg max ( ) = arg max min ( ).

Решение задачи представлено как программа в среде Matlab, с использованием функции fminimax:

9

Так как в среде Matlab реализована только функция fminimax, которая минимизирует наихудшие значения системы функций нескольких переменных, начиная со стартовой оценки ( 0), то для реализации максиминной свертки необходимо в fminimax передавать функции, возведенные в степень 1"(функция funminmax).

Результат:

∙1 = 111, 6707

∙2 = 201, 6612

∙3 = −0, 0000

∙4 = 61, 6654

∙1 = 1, 0840

∙2 = 1, 0840

1.5Метод последовательных уступок

Для решения данной задачи была выбрана уступка = 10%. Решение задачи представлено как программа в среде Matlab, с использованием функции fmincon.

Целевые функции:

∙1 = −(12 1 + 5 2 + 15 3 + 10 4)

∙2 = −(32 1 + 15 2 + 12 3 + 80 4)

Для первого критерия:

10