Принятие решений в условиях неопределенности

Принимаем, что aij, bi, cj подчинены нормальному закону распределения. В этом случае будет справедлива следующие детерминированные постановки:

- 
P - постановка целевой функции, максимизация:

где cj и sj - математическое ожидание и среднее квадратическое отклонение случайной величины cj.

- 
P - постановка целевой функции, минимизация:

Вероятностные ограничения:

где

-  соответственно, математические ожидания и дисперсии случайных величин aij и bi;

ta - значение центрированной нормированной случайной величины в нормальном законе распределения, соответствующей заданному уровню вероятности соблюдения ограничений ai.

Сделаем несколько замечаний к приведенным зависимостям:

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

- 
сравнение ограничения ресурса в стохастическом программировании и аналогичным ограничением в задаче линейного программирования показывает, что учет случайного характера величин aij и bi приводит к уменьшению располагаемого ресурса на величину

т.е. к необходимости в дополнительном ресурсе. Однако этот дополнительный ресурс может оказаться неиспользованным, но для гарантированного выполнения плана его иметь необходимо.[7]

2. Практическая часть

Задание 1

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

Предприятие выпускает продукцию двух разновидностей. Каждый вид продукции проходит обработку на трех станках. При обработке 1т продукции  А первый станок  используется  2 ч, второй станок – 3 ч, третий станок - 2 ч. При обработке 1 т продукции  В  первый станок используется 4 ч, второй станок – 2 ч, третий станок – не используется. Время работы станков ограничено и не может превышать для первого станка  174 ч, для второго - 157 ч, для третьего - 77 ч. При реализации 1 т продукции  А  предприятие получает прибыль 13 рублей, а при реализации 1 т продукции  В  - 19 рублей. Найти оптимальный план выпуска продукции каждого вида, дающий максимальную прибыль от реализации всей продукции.

Решение:

Пусть х1 – количество продукции вида А;

х2 - количество продукции вида В.

Математическая модель задачи:

F = 13x1 + 19x2  max

2x1 + 4x2  174

3x1 + 2x2  157

24x1  77

x1  0, x2  0

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

(1) 2x1 + 4x2  174

      2x1 + 4x2 = 174

Точка О (0;0):

0  174 - верно

(2) 3x1 + 2x2  157

      3x1 + 2x2 = 157

0  157 - верно

(3) 2x1  77

      2x1 = 77

      x1 = 38,5

0  38,5 - верно

(4) х1  0

      х1 = 0 – ось ОХ2.

(5) х2  0

      х2 = 0 – ось ОХ1  область решений системы ограничений находится только в первой четверти декартовой системы координат.

Пятиугольник ОАВСД – область решений системы ограничений.

Находим координаты точки В:

2x1 + 4x2 = 174

3x1 + 2x2 = 157       ·(-2)

2x1 + 4x2 = 174

-6x1 – 4x2 = -314

-4x1 = -140

   x1 = 35

2х2 = 157 – 3·35 = 52

х2 = 26

В (35; 26)

max (х) =

Ответ: максимальная прибыль от реализации всей продукции составит 949 рублей, если продукции вида А выпускать 35 тонн, и продукции вида В – 26 тонн.

Решим полученную задачу симплексным методом

Запишем задачу в каноническом виде:

F = 13x1 + 19x2  max

2x1 + 4x2 + х3 = 174

3x1 + 2x2 + х4 = 157

2x1 + х5 = 77

хj  0, j=1,2,3,4,5.

Первое допустимое базисное решение: (0, 0, 174, 157, 77)

¦(х1) = 

Первый базисное решение не является оптимальным, т.к. 1  0 и 2  0.

Второе базисное решение: (0, , 0, 70, 77)

¦(х2) = 

Второй базисное решение не является оптимальным, т.к. 1  0.

Третье базисное решение: (35, 26, 0, 0, 7)

¦(х3) = 

Третий базисное решение является оптимальным, т.к. все Dj  0.

Ответ:  max ¦(х) =  949 при допустимом базисном решении (35, 26, 0, 0, 7).

Т.е. максимальную прибыль от реализации всей продукции в размере 949 рублей можно получить, если продукции вида А выпускать 35 тонны и продукции вида В - 26 тонн.

Соответствие опорных решений и вершин допустимой области:

Х(0)опор. = {0; 0}   ↔   т. О (0; 0)

Х(1)опор. = {0; }   ↔   т. А (0; 43,5)

Хоптим. = {35; 26}   ↔   т. В (35; 26).

Задание 2

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

max Z = 0x1 + 4x2 - 2x3 + 4x4 - 3х5

-1x1 + 1x2 + 3x3 + 0х4 - 2х5 = 3

3x1 + 0x2 + 0x3 + 2х4 + 2х5 = 7

-3x1 + 1x2 + 2x3 + 0х4 + 2х5 = 1

xj  0, j = 1,2,3,4,5.

Решение:

Составляем М-задачу:

max Z = -0x1 + 4x2 - 2x3 + 4x4 - 3х5 – М·(у1 + у2 + у3)

-1x1 + 1x2 + 3x3 + 0х4 - 2х5 + у1 = 3

3x1 + 0x2 + 0x3 + 2х4 + 2х5 + у2 = 7

-3x1 + 1x2 + 2x3 + 0х4 + 2х5 + у3 = 1

хj  0, j=1,2,3,4,5;

у1 ≥ 0, у2 ≥ 0, у3 ≥ 0.

Первое допустимое базисное решение: (0, 0, 0, 0, 0, 3, 7, 1)

Z(х1у1) = -11М

2

2

Первый опорный план не является оптимальным, т.к. не все j ≥ 0.

Второе базисное решение: (0, 0, , 0, 0, , 7, 0)

Z(х2у2) =  -М - 1

Второй опорный план не является оптимальным, т.к. не все j ≥ 0.

Третье базисное решение: (, 0, , 0, 0, 0, , 0)

Z(х3у3) = 

Третий опорный план не является оптимальным, т.к. не все j ≥ 0.

Четвертое базисное решение: (, 0, , 0, )

Z(х4) = 

Четвертый опорный план не является оптимальным, т.к. не все j ≥ 0.

Пятое базисное решение: (, 0, , , 0)

Z(х5) = 

Пятый опорный план не является оптимальным, т.к. не все j ≥ 0.

Шестое базисное решение: (1, 4, 0, 2, 0)

Z(х6) =  24

Шестой опорный план является оптимальным, т.к. все j ≥ 0.

Ответ: max (х) = 24 при оптимальном решении (1, 4, 0, 2, 0).

Двойственная задача:

min F = 3у1 + 7у2 + 1у3

-1у1 + 3у2 - 3у3 ≥ 0

1у1 + 0у2 + 1у3 ≥ 4

3у1 + 0у2 + 2у3 ≥ -2

0у1 + 2у2 + 0у3 ≥ 4

-2у1 + 2у2 + 2у3 ≥ -3

yi – любого знака (i = 1,2,3)

Оптимальный план двойственный задачи (выписываем из последней симплекс-таблицы №6, из строки оценок тех векторов, которые входили в первоначальный базис):

у = (3; 2; 1)

min F =

Задание 3

Решить методом потенциалов транспортную задачу:

На станции А1,  А2,  А3,  А4,  А5  поступил однородный груз, который надо отвезти пяти заказчикам  В1,  В2,  В3,  В4,  В5.

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

Требуется спланировать перевозки так, чтобы общая сумма стоимости перевозок была наименьшей.