Моделирование и оптимизация деятельности предприятия. Анализ и корректировка оптимального плана
Автор работы: Пользователь скрыл имя, 12 Октября 2017 в 12:53, курсовая работа
Описание работы
Исследование операций — научная дисциплина, занимающаяся
разработкой и практическим применением методов оптимизации.
Примерами задач исследования операций, являются следующие задачи,
которые были рассмотрены и решены в данной курсовой работе:
- оптимизация производственной деятельности предприятия;
- решение матричной игры общего вида;
- решение биматричной игры;
- решение задачи о максимальном потоке.
Содержание работы
Введение ....................................................................................................................................... 3
1 Моделирование и оптимизация деятельности предприятия. Анализ и
корректировка оптимального плана ...................................................................................... 4
1.1 Модель оптимизации производственной деятельности предприятия ........... 4
1.2 Построение и анализ производственной функции предприятия ................... 14
1.3 Расчет оптимального плана предприятия. Анализ, корректировка ............ 17
2 Решение матричной игры сведением к задаче линейного программирования ...... 30
3 Решение биматричной игры ............................................................................................... 36
4 Решение задачи о максимальном потоке ......................................................................... 40
Список литературы ...............................................................
Файлы: 1 файл
2
Содержание
Введение ....................................................................................................................................... 3
1 Моделирование и оптимизация деятельности предприятия. Анализ и
корректировка оптимального плана ...................................................................................... 4
1.1 Модель оптимизации производственной деятельности предприятия ........... 4
1.2 Построение и анализ производственной функции предприятия ................... 14
1.3 Расчет оптимального плана предприятия. Анализ, корректировка ............ 17
2 Решение матричной игры сведением к задаче линейного программирования ...... 30
3 Решение биматричной игры ............................................................................................... 36
4 Решение задачи о максимальном потоке ......................................................................... 40
Список литературы .................................................................................................................. 45
Приложение А. Контрольные примеры. Инструкция пользователю программы,
реализующей симплекс-метод .............................................................................................. 46
3
Введение
Исследование операций — научная дисциплина, занимающаяся
разработкой и практическим применением методов оптимизации.
Примерами задач исследования операций, являются следующие задачи,
которые были рассмотрены и решены в данной курсовой работе:
- оптимизация производственной деятельности предприятия;
- решение матричной игры общего вида;
- решение биматричной игры;
- решение задачи о максимальном потоке.
В решении задачи оптимизации производства и матричной игры
общего вида сведением к задаче линейного программирования был
использован симлекс-метод. Для численной реализации симплексного
алгоритма была разработана оригинальная программа, средаразработки
Microsoft Visual C#.
4
1 Моделирование и оптимизация деятельности предприятия.
Анализ и корректировка оптимального плана
1.1 Модель оптимизации производственной деятельности предприятия
Постановка задачи линейного программирования
Рассматривается производство обуви четырех моделей. На развитие
производства данного вида продукции выделяются денежные средства.
Известны потребности населения в каждом виде обуви, а именно
дорогой (модной) и дешевой (массовой). Также известны текущие затраты на
производство, прочие затраты на производство и количество часов
затрачиваемых на производство одной пары обуви.
Необходимо максимизировать прибыль от производства обуви,
учитывая все затраты на производство, для этого необходимо определить
какое количество пар обуви каждой модели будет производиться, количество
материалов, необходимых для производства и определить объем инвестиций,
выделяемых на производство.
Модель задачи линейного программирования
Условные обозначения для формирования общей структуры табличной
формы модели линейного программирования максимизации прибыли от
производства обуви.
, =1, , - количество производимых пар j-го вида обуви модных моделей;
, = + 1, , - количество пар j-го вида обуви массовых моделей,
производимых за период;
, = 1, , - количество пар j-го вида обуви, реализуемых по основной цене;
, = + 1, , - количество пар j-го вида обуви, реализуемых по заниженной цене;
, = 1, , – количество единиц закупаемого i-го материала;
Ф( ), = 1,2, … – k-ый вариант суммы выделяемых средств;
T – фонд чистого рабочего времени (часов за сезон);
, j=1, , - нормативы затрат рабочего времени (часов на изготовление
одной пары обуви j-ой модели);
, = 1, , = 1, ,– нормативы затрат единиц каждого i-го материала
на изготовление одной пары обуви j-ой модели;
5
З , = 1, , –цена за единицу i-го материала;
С , = 1, , – издержки в расчете на одну пару обуви j-ой модели;
П , = 1, , –удельная прибыль от одной пары обуви j-ой модели, при
продаже по основной цене;
П , = + 1, , –удельная прибыль от одной пары обуви j-ой модели,
при продаже по заниженной цене.
Модель параметрической задачи линейного программирования в общем виде:
ц = П
+ П
− З → max (1.1)
≤ , = , (1.2)
≥ , =1, , (1.3)
≥ + , = + 1, , (1.4)
≤ , =1,
, (1.5)
≤ , (1.6)
≤ + ∆ , (1.7)
≤ , (1.8)
+ З
≤ Ф( ) , = 1,2, …, (1.9)
≥ 0, = 1, , (1.10)
≥ 0, = 1, ,
(1.11)
≥0, = + 1, ,
(1.12)
≥ 0, = 1, . (1.13)
6
Параметром в данной задаче является Ф( ), k = 1,2, … -сумма
выделяемых средств.
Интерпретация целевой функции и ограничений:
(1.1) – целевая функция отражает максимизацию суммарной прибыли
от вложенных средств, с учетом затрат;
(1.2) – суммарные затраты каждого вида закупаемого материала не
должны превышать количество используемого материала;
(1.3) – количество пар обуви дорогих моделей не должно быть меньше
количества пар обуви дорогих моделей, продаваемых по основной цене;
(1.4) – количество пар массовой обуви не должно быть меньше
количества пар массовой обуви по основной и заниженной цене;
(1.5) – количество пар модной обуви, продаваемых по основной цене
не должно превышать спрос на модели модной обуви;
(1.6) –количество пар массовой обуви, продаваемой по основной цене не
должно превышать спрос на модели массовой обуви по основной цене;
(1.7) –количество пар массовой обуви, продаваемой по заниженной цене
не должно превышать спрос на модели массовой обуви по заниженной цене;
(1.8) – суммарные затраты рабочего времени на производство пары
обуви не должны превышать фонда рабочего времени;
(1.9) – суммарные затраты на производство пар обуви не должны
превышать сумму выделяемых средств;
(1.10)–(1.13) – условие не отрицательности.
Числовая модель задачи линейного программирования
Таблица1 - Формирование числовых данных
Число и номер
моделей обуви
Число и
номер видов
материалов
Значения параметров для расчета числовых данных
α
β
σ
m = 4
M1,2,3,4
n = 4
№1,2,3,4
1,1
1,2
1,1
1
1,2
1,1
7
Таблица 2 - Удельные нормативы затрат и цены на обувь
Модели
обуви
Удельные
затраты на
оборудование
и
инструменты,
ден.ед. на 1
пару обуви
Затраты
рабочего
времени на
изготовление,
чел. часы на 1
пару
Затраты материалов,
единиц на 1 пару
Основная
цена,
ден.ед. на
1 пару
Удельные
издержки на
аренду
помещения,
эл. Энергию
и др., ден.ед.
на 1 пару
М
атери
ала
№
1
М
атери
ала
№
2
М
атери
ала
№
3
М
атери
ала
№
4
1
2
3
4
5
6
7
8
9
M1
38,5
5
1
2 0,2 0,1
300
18
M2
48,4
6
1,2 2 0,25 0,12
360
18
M3
880
8
2,1 3 0,2 0,15
4800
20
M4
220
6
1,5 2 0,22 0,14
960
18
Цены на
материалы,
ден.ед. на 1
ед.
-
-
50 30 280 320
-
-
Ограничения по спросу на обувь:
- спрос на массовую обувь 1-ой и 2-ой модели, продаваемой по
основной цене равен 44 пары;
- спрос на массовую обувь 1-ой и 2-ой модели, продаваемой по
заниженной цене равен 220 пар;
- спрос на массовую обувь 1-ой и 2-ой модели равен 60 пар и 108 пар,
соответственно;
Снижение цен допускается до 80%, т.е. β = (1-0,8) = 0,2 .
Коэффициент амортизации оборудования α = 0,1.
Трудовые затраты составляют T = 2310.
Сумма выделяемых средств Ф = 47327 денежных единиц.
8
Для данного варианта задания определено следующее
число переменных:
-число и номера моделей обуви m = 4;
-число и номера видов материалов по обуви n = 4.
Таким образом, общее количество основных переменных 14.
Введем сквозную нумерацию переменных:
− количество пар модной обуви 1-ой модели;
−количество пар модной обуви 2-ой модели;
−количество пар массовой обуви 1-ой модели;
−количество пар массовой обуви 2-ой модели;
−количество пар модной обуви 1-ой модели по основной цене;
−количество пар модной обуви 2-ой модели по основной цене;
−количество пар массовой обуви 1-ой модели по основной цене;
−количество пар массовой обуви 2-ой модели по основной цене;
−количество пар массовой обуви 1-ой модели по заниженной цене;
−количество пар массовой обуви 2-ой модели по заниженной цене;
− количество материала 1, затраченного на производство пар обуви;
−количество материала 2, затраченного на производство пар обуви;
− количество материала 3, затраченного на производство пар обуви;
−количество материала 4, затраченного на производство пар обуви;
Прибыль при продаже по основной цене рассчитывается по формуле:
П = Ц − − , j=1, .
Прибыль при продаже по заниженной цене рассчитывается по формуле:
П =
Ц − − , j= , + 1,
где Ц − реализационная цена пары обуви − ой модели; −
затраты на приобретение оборудования и инструментов, в расчете на одну
9
пару обуви; − коэффициент амортизации изнашиваемости на одну
пару обуви.
Числовая модель имеет вид:
ц = 278,15 + 337,16 + 4692 + 768 + 852 + 154 − 50 −
−30 − 280 − 320 → (1.14)
+ 2 + 0,2 + 0,1 − ≤ 0,
1,2 + 2 + 0,25 + 0,12 − ≤ 0,
(1.15)
2,1 + 3 + 0,2 + 0,15 − ≤ 0,
1,5 + 2 + 0,22 + 0,14 − ≤ 0,
− ≥ 0,
− ≥ 0,
(1.16)
− − ≥ 0,
− − ≥ 0,
(1.17)
≤ 60,
≤ 108,
(1.18)
+ ≤ 44,(1.19)
+ ≤ 264,(1.20)
5 + 6 + 8 + 6 ≤ 2310,(1.21)
18 + 18 + 20 + 18 + 50 + 30 + 280 + 320 ≤ Ф( ),(1.22)
≥ 0, = 1,14 .(1.23)
Интерпретация целевой функции и ограничений:
(1.14) – целевая функция отражает максимизацию суммарной прибыли
от вложенных средств;
(1.15) – суммарные затраты каждого вида используемого материала
не должны превышать количество используемого материала;
(1.16) – количество пар обуви дорогих моделей не должно быть
меньше количества пар обуви дорогих моделей по основной цене;
(1.17) – количество пар массовой обуви не должно быть меньше
количества пар массовой обуви по основной и заниженной цене;
(1.18) – количество пар модной обуви по основной цене не должно
превышать спрос на модели модной обуви;
10
(1.19) – количество пар массовой обуви по основной цене не должно
превышать спрос на модели массовой обуви по основной цене;
(1.20) – количество пар массовой обуви по заниженной цене не должно
превышать спрос на модели массовой обуви по заниженной цене;
(1.21) – суммарные затраты рабочего времени на производство пары
обуви не должны превышать фонда рабочего времени;
(1.22) – суммарные затраты на производство пар обуви не должны
превышать сумму выделяемых средств;
(1.23)– условие не отрицательности.
Табличная форма задачи линейного программирования
Таблица 3 -Табличная форма задачи линейного программирования
№
У
слови
я
Е
ди
н
иц
ы
и
зм
ерен
и
я
Перечень и структура способов
Т
и
п
отн
ош
ен
ий
П
равая часть
С
одерж
ан
и
е услови
я
С
пособ №
1
(производство дорогой обуви)
С
пособ №
2
(производство
м
ассовой обуви)
С
пособ №
3
(производство
обуви по основной
цене)
С
пособ №
4
(производство
обуви по
заниж
еннойцене)
М
атериалы
,
используем
ы
е на
производстве
Перемен-
ные
Условия
пар пар пар пар пар пар пар пар пар пар м2 м2 м2 м2
0 Ден.ед. 0
0 0
0
278,15
337,16
4692
768
852
154
-50
-30
-280
-320
= max (1.24)
1
м2
1 2 0,2 0,1 0 0 0 0 0 0 -1 0 0 0 ≤ 0 (1.25)
2
м2
1,2 2 0,25 0,12 0 0 0 0 0 0 0 -1 0 0 ≤ 0 (1.26)
3
м2
2,1 3 0,2 0,15 0 0 0 0 0 0 0 0 -1 0 ≤ 0 (1.27)
4
м2
1,5 2 0,22 0,14 0 0 0 0 0 0 0 0 0 -1 ≤ 0 (1.28)
5 Пар
1 0 0 0 -1 0 0 0 0 0 0 0 0 0 ≥ 0 (1.29)
6 Пар
0 1 0 0 0 -1 0 0 0 0 0 0 0 0 ≥ 0 (1.30)
7 Пар
0 0 1 0 0 0 -1 0 -1 0 0 0 0 0 ≥ 0 (1.31)
8 Пар
0 0 0 1 0 0 0 -1 0 -1 0 0 0 0 ≥ 0 (1.32)
9 Пар
0 0 0 0 1 0 0 0 0 0 0 0 0 0 ≤ 60 (1.33)
10 Пар
0 0 0 0 0 1 0 0 0 0 0 0 0 0 ≤ 108 (1.34)
11 Пар
0 0 0 0 0 0 1 1 0 0 0 0 0 0 ≤ 44 (1.35)
12 Пар
0 0 0 0 0 0 0 0 1 1 0 0 0 0 ≤ 264 (1.36)
13 Пар
5 6 8 6 0 0 0 0 0 0 0 0 0 0 ≤ 2310 (1.37)
14 Ден.ед. 18 18 20 18 0 0 0 0 0 0 50 30 280 320 ≤ Ф( ) (1.38)
11
Примечание к таблице 3:
(1.24) - максимизация прибыли от производства обуви, с учетом затрат ;
(1.25) - ограничение по материалам для производства обуви модели 1;
(1.26) - ограничение по материалам для производства обуви модели 2;
(1.27) - ограничение по материалам для производства обуви модели 3;
(1.28) - ограничение по материалам для производства обуви модели 4;
(1.29) - ограничение производства и реализации модной обуви модели 1;
(1.30) - ограничение производства и реализации модной обуви модели 2;
(1.31) - ограничение производства и реализации массовой обуви модели 1;
(1.32) - ограничение производства и реализации массовой обуви модели 2;
(1.33) - ограничение по спросу на модную обувь модели 1;
(1.34) - ограничение по спросу на модную обувь модели 2;
(1.35) - ограничение по спросу на массовую обувь модели 1 и 2;
(1.36) -ограничение по дополнительному спросу на массовую обувь модели 1 и 2;
(1.37) - ограничение по фонду рабочего времени на производство модной
обуви 1-ой и 2-ой модели, и на производство массовой обуви модели 1 и 2.
(1.38) - ограничение на количество выделяемых средств.
Модель задачи линейного программирование с каноническойсистемой
ц = 278,15 + 337,16 + 4692 + 768 + 852 + 154 − 50
− 30 − 280 − 320 − − − − →
Баланс по материалам:
+ 2 + 0,2 + 0,1 − + = 0,
1,2 + 2 + 0,25 + 0,12 − + = 0,
2,1 + 3 + 0,2 + 0,15 − + = 0,
1,5 + 2 + 0,22 + 0,14 − + = 0.
Баланс по реализации:
− − + = 0,
− − + = 0,
12
− − − + = 0,
− − − + = 0.
Ограничение по спросу:
+ = 60,
+ = 108,
+ + = 44,
+ + = 264.
Ограничение по фонду рабочего времени:
5 + 6 + 8 + 6 + = 2310.
Ограничение по сумме выделяемых средств:
18 + 18 + 20 + 18 + 50 + 30 + 280 + 320 + = Ф( ), = 1,2, …
Условие неотрицательности:
≥ 0, = 1,32 .
Приведем интерпретацию переменных.
- Основные переменные:
− количество пар дорогой обуви 1-ой модели;
−количество пар дорогой обуви 2-ой модели;
−количество пар массовой обуви 1-ой модели;
−количество пар массовой обуви 2-ой модели;
−количество пар модной обуви 1-ой модели по основной цене;
−количество пар модной обуви 2-ой модели по основной цене;
−количество пар массовой обуви 1-ой модели по основной цене;
−количество пар массовой обуви 2-ой модели по основной цене;
−количество пар массовой обуви 1-ой модели по заниженной цене;
−количество пар массовой обуви 2-ой модели по заниженной цене;
− количество материала 1 , затраченного на производство пар обуви;
−количество материала 2 , затраченного на производство пар обуви;
−количество материала 3 , затраченного на производство пар обуви;
−количество материала 4 , затраченного на производство пар обуви;
13
- Дополнительные переменные:
− недоиспользование по модной обуви 1-ой модели;
− недоиспользование по модной обуви 2-ой модели;
− недоиспользование по массовой обуви 1-ой модели;
− недоиспользование по массовой обуви 2-ой модели;
− перевыполнение по модной обуви 1-ой модели по основной цене;
−перевыполнение по модной обуви 2-ой модели по основной цене;
− перевыполнение по массовой обуви 1-ой и 2-ой модели по основной цене;
− перевыполнение по массовой обуви 1-ой и 2-ой модели по заниженной цене;
− недоиспользование по спросу на модную обувь 1-ой модели по основной цене;
− недоиспользование по спросу на модную обувь 2-ой модели по основной цене;
− недоиспользование спроса на массовую обувь 1-ой и 2-ой модели по основной цене;
− недоиспользование спроса на массовую обувь 1-ой и 2-ой модели по заниженной цене;
− недоиспользование по фонду рабочего времени;
− недоиспользование выделяемых средств.
- Искусственные переменные:
− недовыполнение по модной обуви 1-ой модели по основной цене;
− недовыполнение по модной обуви 2-ой модели по основной цене;
− недовыполнение по массовой обуви 1-ой и 2-ой модели по основной цене;
− недовыполнение по массовой обуви 1-ой и 2-ой модели по заниженной цене;
Численные расчеты и анализ по модели
Решим параметрическую задачу линейного программирования вида
(1.11)-(1.20)для данной ситуации. Параметром выступает сумма средств (в
денежных единицах), выделяемая на развитие предпринимательской
деятельности. Целевая функция отражает максимизацию прибыли от
вложенных средств, с учетом затрат на закупку материалов. Используя
программу, реализующую симплекс-метод, найдем решение данной ЗЛП,
14
при объеме инвестиций Ф( ), = 1,2, … , с шагом изменения инвестиций
Ф( ) = 2500 (денежных единиц).
В результате получим производственную функцию, которая показана в
таблице4.
Таблица 4 - Значения производственной функции
Ф( )
П( , Ф( ))
0
61325,49
2500
69373,09
5000
138746,18
7500
201362,37
10000
212163,17
12500
222963,96
15000
233764,75
17500
244565,5
20000
255366,3
22500
266167,1
25000
276967,9
27500
287768,7
30000
298569,5
32500
309370,3
35000
320171,1
37500
330971,8
40000
341772,69
42500
352573,4
45000
363374,27
47327
373423,87
1.2 Построение и анализ производственной функции предприятия
Пользуясь программой, которая реализует метод наименьших
квадратов, найдем аналитическое представление производственной функции.
Аналитическое представление показано на рисунке 1.
Уравнение квадратичной регрессии имеет вид:
= −0,0001 + 12,6469 + 61325,4966
15
Рисунок 1.1 - График квадратичной регрессии
Предположим, что при объеме инвестиций 0 ден.ед получим прибыль
от реализации равную 61325,4966ден.ед, а при 2500 ден.ед прибыль от
реализации составит 69373,09 ден.ед, разница между эффектами составила
8047,59ден.ед; при объеме инвестиций 5000 ден.ед прибыль от реализации
составит 138746,18 ден.ед, разница между эффектами 2500 и 5000 составила
69373,09 ден.ед; при объеме инвестиций 7500 ден.ед прибыль от реализации
составит 201362,37 ден.ед, разница между эффектами 5000 и 7500 составила
62616,19ден.ед; при объеме инвестиций 10000 ден.ед прибыль от реализации
составит 212163,17 ден.ед, разница между эффектами 7500 и 10000 составила
10800,8 ден.ед;при объеме инвестиций 12500 ден.ед прибыль от реализации
составит 222963,96 ден.ед, разница между эффектами 10000 и 12500
составила 10800,8 ден.ед; возьмем объем инвестиций равный 15000 ден.ед,
тогда прибыль от реализации равна 233764,75 ден.ед, разница с предыдущим
значением инвестиций составила 10800,8 ден.ед; ; возьмем объем
инвестиций равный 17500 ден.ед, тогда прибыль от реализации равна
244565,5 ден.ед, разница с предыдущим значением инвестиций составила
10800,8 ден.ед; ; возьмем объем инвестиций равный 20000 ден.ед, тогда
прибыль от реализации равна 255366,3 ден.ед, разница с предыдущим
значением инвестиций составила 10800,8 ден.ед; при объеме инвестиций
22500 ден.ед прибыль от реализации составит 266167,1 ден.ед, разница
16
между эффектами 20000 и 22500 составила 10800,8 ден.ед; при объеме
инвестиций 25000 ден.ед прибыль от реализации составит 276967,9 ден.ед,
разница между эффектами 22500 и 25000 составила 10800,8ден.ед; при
объеме инвестиций 27500 ден.ед прибыль от реализации составит 287768,7
ден.ед, разница между эффектами 25000 и 27500 составила 10800,8 ден.ед;
возьмем объем инвестиций равный 30000 ден.ед, тогда прибыль от
реализации равна 298569,5 ден.ед, разница с предыдущим значением
инвестиций составила 10800,8 ден.ед; возьмем объем инвестиций равный
32500 ден.ед, тогда прибыль от реализации равна 309370,3 ден.ед, разница с
предыдущим значением инвестиций составила 10800,8 ден.ед; возьмем
объем инвестиций равный 35000 ден.ед, тогда прибыль от реализации равна
320171,1 ден.ед, разница с предыдущим значением инвестиций составила
10800,8 ден.ед; возьмем объем инвестиций равный 37500 ден.ед, тогда
прибыль от реализации равна 330971,8 ден.ед, разница с предыдущим
значением инвестиций составила 10800,8 ден.ед; при объеме инвестиций
40000 ден.ед прибыль от реализации составит 341772,69 ден.ед, разница
между эффектами 37500 и 40000 составила 10800,8 ден.ед; при объеме
инвестиций 42500 ден.ед прибыль от реализации составит 352573,4 ден.ед,
разница между эффектами 40000 и 42500 составила 10800,8 ден.ед; при
объеме инвестиций 45000 ден.ед прибыль от реализации составит 363374,27
ден.ед, разница между эффектами 42500 и 45000 составила 10800,8
ден.ед;возьмем объем инвестиций равный 47327ден.ед, тогда прибыль от
реализации равна 373423,875 ден.ед, разница с предыдущим значением
инвестиций составила 10049,605 ден.ед.
Таким образом, мы установили, что значение целевой функции от
параметра максимально при значения Ф( ) = 47327. Будем считать
целесообразным выбор параметра Ф( ) = 47327, так как при дальнейшем
увеличении инвестиций не будет наблюдаться рост эффекта.
17
1.3 Расчет оптимального плана предприятия. Анализ, корректировка
Проведем анализ решения задачи линейного программирования при
оптимальном значении параметра (объем денежных средств, выделяемый на
развитие предпринимательской деятельности) для производства.
Руководство к пользованию программой, реализующей численной
решение симплексного алгоритма, которая была разработана в среде
разработки Microsoft Visual C#, представлена в приложении А.
Последняя симплекс таблица для производственной функции
предприятия со значением параметра Ф( ) = 47327 имеет вид,
представленный в таблице 5.
18
Таблица 5 – Симплекс-таблица оптимального плана
F 0
0 0 0 0 0 278,15 337,16 4692 768 852 154 -50 -30 -280 -320 0
0
0
0 0 -M 0 -M 0 -M 0 -M 0 0 0 0 0 0
C b X b b i X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14 X15 X16 X17 X18 X19 X20 X21 X22 X23 X24 X25 X26 X27 X28 X29 X30 X31 X32
0 X4
0 0 0 0 1 0
0 0 -1 0 -1 0 0 0 0 0
0
0
0 0
0
0
-1
0 0 0 0 0 0
-50 X11 57,75 0 0 0 0 0 0,02 0 0,03 0 0,03 1 0 0 0 -0,93 0,03 0,34 0,39 0
0,02
0
0,03
0 0 0 0 0 0,0012
-30 X12 72,18 0 0 0 0 0 0,52 0 0,05 0 0,05 0 1 0 0 0,07 -0,95 0,42 0,48 0
0,52
0
0,052
0 0 0 0 0 0,0015
-280 X13 57,75 0 0 0 0 0 -0,97 0 -0,01 0 -0,01 0 0 1 0 0,06 0,03 -0,65 0,39 0
-0,97
0
-0,01
0 0 0 0 0 0,0012
0 X1
0 1 0 0 0 -1
0 0
0 0 0 0 0 0 0 0
0
0
0 -1
0
0
0
0 0 0 0 0 0
0 X2
0 0 1 0 0 0
-1 0
0 0 0 0 0 0 0 0
0
0
0 0
-1
0
0
0 0 0 0 0 0
0 X3 288,75 0 0 1 0 0 10,11 0 0,69 0 0,69 0 0 0 0 0,3 0,18 1,7 1,95 0
10,11
0
0,69
0 0 0 0 0 0,0061
-320 X14 63,52 0 0 0 0 0 0,22 0 0,012 0 0,012 0 0 0 1 0,06 0,04 0,37 -0,57 0
0,22
0
0,012
0 0 0 0 0 0,0013
0 X27 60 0 0 0 0 1
0 0
0 0 0 0 0 0 0 0
0
0
0 0
0
0
0
1 0 0 0 0 0
0 X28 108 0 0 0 0 0
1 0
0 0 0 0 0 0 0 0
0
0
0 0
0
0
0
0 1 0 0 0 0
4692 X7
44 0 0 0 0 0
0 1
1 0 0 0 0 0 0 0
0
0
0 0
0
0
0
0 0 1 0 0 0
0 X30 19,25 0 0 0 0 0 -10,11 0 0,3 0 0,3 0 0 0 0 -0,3 -0,18 -1,7 -1,95 0
-10,11
-1
-0,69
0 0 1 1 0 -0,006
0 X31 0,061 0 0 0 0 0 -74,92 0 0,46 0 0,46 0 0 0 0 -2,44 -1,46 -13,66 -15,61 0
-74,92
0
0,46
0 0 0 0 1 -0,04
852 X9 244,75 0 0 0 0 0 10,11 0 -0,3 1 0,69 0 0 0 0 0,3 0,18 1,7 1,95 0
10,11
1
0,69
0 0 -1 0 0 0,006
Zстр 373423,87 0 0 0 0 278,15 8465,92 0 3657,32 0 431,32 0 0 0 0 266,01 159,6 1489,68 1702,5 0
8803,08
852
585,3
0 0 3840 0 0 4,32
19
Анализ оптимального плана
1) Приведем интерпретацию переменных.
Основные переменные:
− количество пар дорогой обуви 1-ой модели;
−количество пар дорогой обуви 2-ой модели;
−количество пар массовой обуви 1-ой модели;
−количество пар массовой обуви 2-ой модели;
−количество пар модной обуви 1-ой моделипо основной цене;
−количество пар модной обуви 2-ой модели по основной цене;
−количество пар массовой обуви 1-ой моделипо основной цене;
−количество пар массовой обуви 2-ой моделипо основной цене;
−количество пар массовой обуви 1-ой моделипо заниженной цене;
−количество пар массовой обуви 2-ой модели по заниженной цене;
− количество материала 1 , затраченного на производство пар обуви;
−количество материала 2 , затраченного на производство пар обуви;
−количество материала 3 , затраченного на производство пар обуви;
−количество материала 4 , затраченного на производство пар обуви.
Дополнительные переменные:
− недоиспользование по модной обуви 1-ой модели;
−недоиспользование по модной обуви 2-ой модели;
−недоиспользование по массовой обуви 1-ой модели;
−недоиспользование по массовой обуви 2-ой модели;
− перевыполнение по модной обуви 1-ой моделипо основной цене;
−перевыполнение по модной обуви 2-ой моделипо основной цене;
− перевыполнение по массовой обуви 1-ой и 2-ой модели по основной цене;
− перевыполнение по массовой обуви 1-ой и 2-ой моделипо заниженной цене;
−недоиспользование по спросу на модную обувь 1-ой моделипо основной цене;
−недоиспользование по спросу на модную обувь 2-ой моделипо основной цене;
−недоиспользование спроса на массовую обувь 1-ой и 2-ой моделипо основной цене;
20
−недоиспользование спроса на массовую обувь 1-ой и 2-ой моделипо заниженной цене;
−недоиспользование по фонду рабочего времени;
−недоиспользование выделяемых средств.
Искусственные переменные:
− недовыполнение по модной обуви 1-ой модели по основной цене;
− недовыполнение по модной обуви 2-ой модели по основной цене;
− недовыполнение по массовой обуви 1-ой и 2-ой модели по основной цене;
− недовыполнение по массовой обуви 1-ой и 2-ой модели по заниженной цене.
Из таблицы получили оптимальное значение целевой функции ц =
373423,875, оптимальный план:
= 0, = 0, = 288,75, = 0, = 0, = 0, = 44, = 0,
= 0, = 244,75, = 57,75, = 72,18, = 57,75, = 63,52.
Проведем анализ решения задачи линейного программирования при
оптимальном значении параметра (сумме средств, выделяемых на развитее
предпринимательской деятельности).
Последняя симплекс таблица с объемом денежных единиц 47500
представлена в таблице 5.
2) Анализ решения.
Анализируя оптимальный план, можно сказать, что в него вошли:
- производство массовой обуви 1-ой модели в количестве 288 пар,
производство пар массовой обуви 1-ой модели, продаваемой по основной
цене в количестве 44 пар, производство массовой обуви 1-ой модели,
продаваемой по заниженной цене в количестве 244 пар,производства модной
обуви 1-ой модели в количестве 0 пар, производства модной обуви 2-ой
модели в количестве 0 пар, производство массовой обуви 2-ой модели в
количестве 0 пар, производство массовой обуви 2-ой модели в количестве 0
пар;1-ый, 2-ой, 3-ей и 4-ый материалы, используемые для производства
обуви в количестве 57 единиц на пару , 72 единиц на пару , 57 единиц на
пару и 63 единиц на пару, соответственно; производство модной обуви 1-ой
21
модели , продаваемой по основной цене не выполняется, производство
модной обуви 2-ой модели, продаваемой по основной цене не выполняется,
производство массовой обуви 2-ой модели, продаваемой по основной цене не
выполняется, производство массовой обуви 2-ой модели, продаваемой по
заниженной цене не выполняется;
- недоиспользование по спросу на модную обувь 1-ой модели ,
продаваемую по основной цене составило 60 пар, недоиспользование по
спросу на модную обувь 2-ой модели, продаваемую по основной цене
составило 108 пар, недоиспользование по спросу на массовую обувь 1-ой и 2-
ой моделей, продаваемую по заниженной цене составило 19 пар,
недоиспользование рабочего времени составило 0чел. часов.
3) Анализ с использованием оценок:
- производство модной обуви 1-ой модели рентабельно, объем
производства равен 0 пар, если увеличить объем производства на единицу, то
эффект улучшится, т.е. увеличится на 0 пар, если уменьшить объем
производства на единицу, то эффект уменьшится на 0 пар; производство
модной обуви 2-ой модели рентабельно, объем производства равен 0 пар,
если увеличить объем производства на единицу, то эффект улучшится, т.е.
увеличится на 0 пар, если уменьшить объем производства на единицу, то
эффект уменьшится на 0 пар; производство массовой обуви 1-ой модели
рентабельно, объем производства равен 288 пар, если увеличить объем
производства на единицу, то эффект улучшится, т.е. увеличится на 288 пар,
если уменьшить объем производства на единицу, то эффект уменьшится на
288 пар; производство массовой обуви 2-ой модели рентабельно, объем
производства равен 0 пар, если увеличить объем производства на единицу, то
эффект улучшится, т.е. увеличится на 0 пар, если уменьшить объем
производства на единицу, то эффект уменьшится на 0 пар; производство
модной обуви 1-ой модели, продаваемой по основной цене нерентабельно,
оценка нерентабельности равна 278, если увеличить объем производства на
единицу, то эффект ухудшится, т.е. уменьшится на 278пар, если уменьшить
22
объем производства на единицу, то эффект увеличится на 278пару;
производство модной обуви 2-ой модели, продаваемой по основной цене
нерентабельно, оценка нерентабельности равна 8465, если увеличить объем
производства на единицу, то эффект ухудшится, т.е. уменьшится на 8465пар,
если уменьшить объем производства на единицу, то эффект увеличится на
8465пару; производство массовой обуви 1-ой модели, продаваемой по
основной цене рентабельно, объем производства равен 44 пары, если
увеличить объем производства на единицу, то эффект улучшится, т.е.
увеличится на 44 пары, если уменьшить объем производства на единицу, то
эффект уменьшится на 44 пары; производство массово обуви 2-ой модели,
продаваемой по основной цене нерентабельно, оценка нерентабельности
равна 3657, если увеличить объем производства на единицу, то эффект
ухудшится, т.е. уменьшится на 3657пар, если уменьшить объем производства
на единицу, то эффект увеличится на 3657пару; производство массовой
обуви 1-ой модели, продаваемой по заниженной цене рентабельно, объем
производства равен 244 пар, если увеличить объем производства на единицу,
то эффект улучшится, т.е. увеличится на 244 пар, если уменьшить объем
производства на единицу, то эффект уменьшится на 244 пар; производство
массовой обуви 2-ой модели, продаваемой по заниженной цене
нерентабельно, оценка нерентабельности равна 431, если увеличить объем
производства на единицу, то эффект ухудшится, т.е. уменьшится на 431 пар,
если уменьшить объем производства на единицу, то эффект увеличится на
431пар; использование 1-го материала рентабельно, объем используемого
материала равен 57 м2, если увеличить объем производства на единицу, то
эффект улучшится, т.е. увеличится на 57м2, если уменьшить объем
производства на единицу, то эффект уменьшится на 57м2; использование 2-го
материала рентабельно, объем используемого материала равен 72м2, если
увеличить объем производства на единицу, то эффект улучшится, т.е.
увеличится на 72м2, если уменьшить объем производства на единицу, то
эффект уменьшится на 72м2; использование 3-го материала рентабельно,
23
объем используемого материала равен 57м2, если увеличить объем
производства на единицу, то эффект улучшится, т.е. увеличится на 57м2, если
уменьшить объем производства на единицу, то эффект уменьшится на
57м2;использование 4-го материала рентабельно, объем используемого
материала равен 63м2, если увеличить объем производства на единицу, то
эффект улучшится, т.е. увеличится на 63м2, если уменьшить объем
производства на единицу, то эффект уменьшится на 63м2;
- недоиспользование по модной обуви 1-ой модели дефицитно, оценка
дефицитности 266, если увеличить объем на единицу, то эффект улучшится
на 266 пар, если объем уменьшить на единицу, то эффект ухудшится на 266
пар; недоиспользование по модной обуви 2-ой модели дефицитно, оценка
дефицитности 159, если увеличить объем на единицу, то эффект улучшится
на 159 пар, если объем уменьшить на единицу, то эффект ухудшится на 159
пар; недоиспользование по массовой обуви 1-ой модели дефицитно, оценка
дефицитности 1489, если увеличить объем на единицу, то эффект улучшится
на 1489 пар, если объем уменьшить на единицу, то эффект ухудшится на
1489 пар; недоиспользование по массовой обуви 2-ой модели дефицитно,
оценка дефицитности 1702, если увеличить объем на единицу, то эффект
улучшится на 1702 пар, если объем уменьшить на единицу, то эффект
ухудшится на 1702 пар; спрос на массовую обувь 1-ой и 2-ой моделей,
продаваемую по основной цене, дефицитен, оценка дефицитности 3840, если
увеличить объем на единицу , то эффект улучшится на 3840 пар, если объем
уменьшить на единицу, то эффект ухудшится на 3840 пар; фонд рабочего
времени недефицитен, остаток равен 0 чел. часов; спрос на модную обувь 1-
ой модели недефицитен, остаток равен 60 пар; спрос на модную обувь 2-ой
модели, продаваемой по основной цене недефицитен, остаток равен 108 пар;
спрос на массовую обувь 1-ой и 2-ой модели, продаваемой по заниженной
цене недефицитен, остаток равен 19 пар;
24
- 1-ое, 2-ое, 3-е и 4-ое плановые задания жесткие, степень жесткости
равна 0, 8803, 852, 585, соответственно. Если 1-ое плановое задание
увеличить на единицу, то эффект ухудшится на 6217; если 2-ое плановое
задание увеличить на единицу, то эффект ухудшится на 8803; если 3-ое
плановое задание увеличить на единицу, то эффект ухудшится на 852; если 4-
ое плановое задание увеличить на единицу, то эффект ухудшится на 585.
Корректировка оптимального плана
Корректировка оптимального плана по нерентабельной продукции
Из анализа оптимального плана мы имеем несколько видов
нерентабельных производств, самым нерентабельным из которых является
производство массовой обуви 2-ой модели, продаваемой по основной цене,
степень его нерентабельности равна 3657пар.
Определим верхнюю границу изменения объема производства
массовой обуви 2-ой модели, продаваемой по основной цене. Для этого
найдем верхнюю границу изменения переменной по формуле:
= ′
= ,
,
; ,
,
; ,
,
; ,
,
; ; ,
,
; ,
,
= 0,13.
Ввиду того, что граница увеличения меньше 1, корректировку
производить нецелесообразно.
Корректировка оптимального плана по ресурсу
Из анализа оптимального плана мы имеем несколько видов
дефицитной продукции, самым дефицитным из которых является спрос на
массовую обувь 1-ой и 2-ой моделей, продаваемые по основной цене, степень
дефицитности 3840 пар.
Корректировка по ресурсу в сторону увеличения.
Пусть нужно увеличить спрос на массовую обувь 1-ой и 2-ой моделей,
продаваемые по основной цене.
Определим границу дефицитного ресурса. Для этого вычислим
нижнюю границу изменения переменной :
25
=
= ,
= 244,75.
Условие увеличения объема производства на 100 пар лежит в
допустимых пределах ,∆=100 .
Корректировочная таблица имеет вид:
−
н = − (− )
Примечание
0
0
0
0+0=0
Не изменилось
57
0
0
57+0=57
Не изменилось
72
0
0
72+0=72
Не изменилось
57
0
0
57+0=57
Не изменилось
0
0
0
0+0=0
Не изменилось
0
0
0
0+0=0
Не изменилось
288
0
0
288+0=288
Не изменилось
63
0
0
63+0=63
Не изменилось
60
0
0
60+0=60
Не изменилось
108
0
0
108+0=108
Не изменилось
44
1
-100
44+100=144
Увеличилось на 100
19
1
-100
19+100=119
Увеличилось на 100
244
-1
100
244-100=144
Уменьшилось на 100
173
0
0
173+0=173
Не изменилось
стр
3 7 3 4 2 3 , 8 7 5 3840 -384000 373423,875+384000=7
57423,875
Увеличилось на 384000
Вывод.
При увеличении спроса на массовую обувь 1-ой и 2-ой моделей,
продаваемые по основной цене, на 100 пар, получаем:
- количество пар массовой обуви 2-ой модели не изменится;
- количество используемого 1-го материалане изменится;
- количество используемого 2-го материала не изменится;
- количество используемого 3-го материала не изменится;
- количество пар модной обуви 1-ой модели не изменится;
- количество пар модной обуви 2-ой модели не изменится;
- количество массовой обуви 1-ой модели не изменится;
- количество используемого 4-го материала не изменится;
- недоиспользование по спросу на модную обувь 1-ой модели,
продаваемую по основной цене не изменится;
26
- недоиспользование по спросу на модную обувь 2-ой модели,
продаваемую по основной цене не изменится;
- количество пар массовой обуви 1-ой модели, продаваемой по
основной цене, увеличится на 100 пар;
- недоиспользование по спросу на массовую обувь 1-ой и 2-ой модели,
продаваемой по заниженной цене, увеличится на 100 пар;
- количество пар массовой обуви 1-ой модели, продаваемой по
заниженной цене, уменьшится на 100 пар;
- недоиспользование выделяемых средств не изменится;
- прибыль увеличится на 384000 ден.ед.
Таким образом, увеличение спроса на массовую обувь 1-ой и 2-ой
моделей, продаваемые по основной цене, происходит за счет производства
пар массовой обуви 1-ой модели, продаваемой по заниженной цене;
количество используемых материалов не изменилось; из оборота средства не
были исключены.
Рекомендация: производству выгодно увеличение спроса на массовую
обувь 1-ой и 2-ой моделей, продаваемые по основной цене, так как при этом
суммарная прибыль увеличивается на 384000 ден.ед, что целесообразно.
Корректировка по ресурсу в сторону уменьшения.
Пусть нужно уменьшить спрос на массовую обувь 1-ой и 2-ой моделей,
продаваемые по основной цене.
Определим границу дефицитного ресурса. Для этого вычислим
верхнюю границу изменения переменной :
=
= ; , = 19,25.
Условие увеличения объема производства на 10 пар лежит в
допустимых пределах ,∆=10 .
27
Корректировочная таблица имеет вид:
н = −
Примечание
0
0
0
0-0=0
Не изменилось
57
0
0
57-0=57
Не изменилось
72
0
0
72-0=72
Не изменилось
57
0
0
57-0=57
Не изменилось
0
0
0
0-0=0
Не изменилось
0
0
0
0-0=0
Не изменилось
288
0
0
288-0=288
Не изменилось
63
0
0
63-0=63
Не изменилось
60
0
0
60-0=60
Не изменилось
108
0
0
108-0=108
Не изменилось
44
1
10
44-10=344
Уменьшилось на 10
19
1
10
19-10=9
Уменьшилось на 10
244
-1
-10
244+10=254
Увеличилось на 10
173
0
0
173-0=173
Не изменилось
стр
373423,875 3840 38400 373423,875-
38400=335023,875
Уменьшилось на 38400
Вывод.
При уменьшении спроса на массовую обувь 1-ой и 2-ой моделей,
продаваемые по основной цене, на 10 пар, получаем:
- количество пар массовой обуви 2-ой модели не изменится;
- количество используемого 1-го материалане изменится;
- количество используемого 2-го материала не изменится;
- количество используемого 3-го материала не изменится;
- количество пар модной обуви 1-ой модели не изменится;
- количество пар модной обуви 2-ой модели не изменится;
- количество массовой обуви 1-ой модели не изменится;
- количество используемого 4-го материала не изменится;
- недоиспользование по спросу на модную обувь 1-ой модели,
продаваемую по основной цене не изменится;
- недоиспользование по спросу на модную обувь 2-ой модели,
продаваемую по основной цене не изменится;
- количество пар массовой обуви 1-ой модели, продаваемой по основной
цене, уменьшится на 10 пар;
28
- недоиспользование по спросу на массовую обувь 1-ой и 2-ой модели,
продаваемой по заниженной цене, уменьшится на 10 пар;
- количество пар массовой обуви 1-ой модели, продаваемой по
заниженной цене, увеличится на 10 пар;
- недоиспользование выделяемых средств не изменится;
- прибыль увеличится на 384000 ден.ед.
Таким образом, уменьшение спроса на массовую обувь 1-ой и 2-ой
моделей, продаваемые по основной цене, происходит за счет введения в
производство 10 пар массовой обуви 1-ой модели, продаваемой по
заниженной цене; количество используемых материалов не изменилось; из
оборота средства не были исключены.
Рекомендация: производству не выгодно уменьшение спроса на
массовую обувь 1-ой и 2-ой моделей, продаваемые по основной цене, так как
при этом суммарная прибыль уменьшается на 38400 ден.ед, что
нецелесообразно.
Корректировка оптимального плана по плановой продукции
Из анализа оптимального плана мы имеем несколько видов плановой
продукции, самым жестким из которых является 2-ое плановое задание,
степень его жесткости равна 8803пар.
Корректировка по плановой продукции в сторону увеличения.
Пусть нужно увеличить 2-ое плановое задание.
Определим границу увеличения. Для этого вычислим верхнюю границу
изменения переменной :
=
= ,
,
; ,
,
;
,
,
; ,
,
;
,
,
= 24,2.
Условие увеличения объема производства на 10 пар лежит в
допустимых пределах, ∆=10 .
29
Корректировочная таблица имеет вид:
н = −
Примечание
0
0
0
0-0=0
Не изменилось
57
0,02
0,2
57-0,2=56,8
Уменьшилось на 0,2
72
0,52
5,2
72-5,2=66,98
Уменьшилось на 5
57
-0,97
-9,7
57+9,7=66,3
Увеличилось на 9
0
0
0
0-0=0
Не изменилось
0
-1
-10
0-0=0
Не изменилось
288
10,11
101,1
288-101,1=187,9
Уменьшилось на 101
63
0,22
2,2
63-2,2=61,8
Уменьшилось на 2
60
0
0
60-0=60
Не изменилось
108
0
0
108-0=108
Не изменилось
44
0
0
44-0=44
Не изменилось
19
-10,11
-101,1
19+101,1=120,1
Увеличилось на 101
0,061
-74,92
-749,2
0,061+749,2=749,261
Увеличилось на 749
244
10,11
101,1
244-101,1=142,9
Уменьшилось на101
стр
373423,8
8803,08 88030,8
373423,8-88030,8=461454,6
Уменьшилось на 88030
Вывод.
При уменьшении 2-го планового задания на 10 пар , получаем:
- количество пар массовой обуви 2-ой модели не изменится;
- количество используемого 1-го материала уменьшится на 0,2;
- количество используемого 2-го материала уменьшится на 5;
- количество используемого 3-го материала увеличится на 9;
- количество пар модной обуви 1-ой модели не изменится;
- количество пар модной обуви 2-ой модели не изменится;
- количество массовой обуви 1-ой модели не изменится;
- количество используемого 4-го материала уменьшится на101;
- недоиспользование по спросу на модную обувь 1-ой модели,
продаваемую по основной цене уменьшится на 2;
- недоиспользование по спросу на модную обувь 2-ой модели,
продаваемую по основной цене не изменится;
- количество пар массовой обуви 1-ой модели, продаваемой по основной
цене, не изменится;
30
- недоиспользование по спросу на массовую обувь 1-ой и 2-ой модели,
продаваемой по заниженной цене, увеличится на 101;
- количество пар массовой обуви 1-ой модели, продаваемой по
заниженной цене, увеличится на 749;
- недоиспользование рабочего времени уменьшится на 101;
- прибыль уменьшится на 88030 ден.ед.
Таким образом, увеличение 2-го планового задания произошло за счет
производства массовой обуви 1-ой модели.
Рекомендация: производству не выгодно увеличение 2-го планового
задания, так как при это суммарная прибыль уменьшится на 88030 ден.ед.
Корректировка по плановой продукции в сторону уменьшения.
Пусть нужно уменьшить 2-ое плановое задание.
Определим границу увеличения. Для этого вычислим нижнюю границу
изменения переменной :
=
= ,
,
; ; ,
,
; ,
,
= 0.
Граница изменения переменной меньше единицы, производить
корректировку нецелесообразно.
2 Решение матричной игры сведением к задаче линейного
программирования
Постановка задачи
Конечная игра двух игроков задана платежной матрицей (таблица 6),
число стратегий первого игрока (А) равно 8, второго игрока (В) равно 10.
Необходимо найти цену игры и оптимальные векторы стратегий игроков.
Таблица 6 – Платежная матрица игры
i
j
B1
B2
B3
B4
B5
B6
B7
B8
B9
B10
А1
96
62
48
51
31
49
18
86
68
-1
А2
98
40
47
26
24
79
38
-1
75
91
А3
22
87
12
54
39
93
56
47
42
-6
А4
19
29
35
82
18
60
18
68
41
13
А5
43
62
87
-5
78
15
18
90
-7
-1
А6
58
0
34
94
82
57
39
-7
48
70
А7
52
74
44
29
29
26
20
33
-7
-5
А8
14
39
-9
45
19
18
13
-9
35
0
31
Решение игры
Введем обозначения:
m– количество стратегий первого игрока;
n– количество стратегий второго игрока;
V* – цена игры;
p̅ * - оптимальный вектор стратегий игрока А, p̅ * = (p*1, … , p*m),
где p*1, … , p*m – вероятности принятия игроком А своих оптимальных
стратегий;
q̅ * - оптимальный вектор стратегий игрока B, q̅ * = (q*1, … , q*n),
где q*1, … , q*n – вероятности принятия игроком B своих оптимальных
стратегий.
1) Проверим, есть ли решение в чистых стратегиях:
- определим нижнюю чистую цену игры и максимальную стратегию:
= max min
= max(−1, −1, −6, 13, −7, −7, −7, −9) = 13; ;
-определим верхнюю чистую цену игры и минимальную стратегию:
= minmax = min(98, 87, 87, 94, 82, 93, 56, 90, 75, 91) = 56; ;
≠, решения в чистых стратегиях нет. Будем искать решение в
смешанных стратегиях.
Запишем в общем случае условие оптимальности стратегий,условие
нормировки и ограничения на знак для двух игроков:
а) для игрока А:
∗ ≥ ∗, = 1, − чистые,
∗ = 1,
∗ ≥ 0, = 1, ;
32
б) для игрока В:
∗ ≤ ∗, = 1, − чистые,
∗ = 1,
∗ ≥ 0, = 1, .
Запишем условие максимизации гарантированного выигрыша игроков:
-для игрока А
∗ → ;
- для игрока В
∗ → .
Положив для первого игрока ∗
∗ = , = 1, , а для второго игрока
∗
∗ = , = 1, ,сведем решение игры к решению задачи линейного
программирования.
Для игрока А задача линейного программирования имеет вид:
ц = →
≥ 1, = 1, ,
≥ 0, = 1, .
Для игрока В задача линейного программирования имеет вид:
ц = →
≤ 1, = 1, ,
≥ 0, = 1, .
Для решения поставленной задачи сведением к задаче линейного
программирования необходимо выполнение условия V* > 0.
33
Для этого получим матрицу линейным преобразованием =
+ , где b=1, c=10.
Таблица 7 – матрица
Запишем задачу линейного программирования для игрока В:
ц = + + + + + + + + + →
106 + 72 + 58 + 61 + 41 + 59 + 28 + 96 + 78 + 9 ≤ 1,
108 + 50 + 57 + 36 + 34 + 89 + 48 + 9 + 85 + 101 ≤ 1,
32 + 97 + 22 + 64 + 49 + 103 + 66 + 57 + 52 + 4 ≤ 1,
29 + 39 + 45 + 92 + 28 + 70 + 28 + 78 + 51 + 23 ≤ 1,
53 + 72 + 97 + 5 + 88 + 25 + 28 + 100 + 3 + 9 ≤ 1,
68 + 10 + 44 + 104 + 92 + 67 + 49 + 3 + 58 + 80 ≤ 1,
62 + 84 + 54 + 39 + 39 + 36 + 30 + 43 + 3 + 5 ≤ 1,
24 + 49 + 1 + 55 + 29 + 28 + 23 + 1 + 45 + 10 ≤ 1,
≥ 0, = 1,10 .
Сведем общую задачу линейного программирования к каноническому виду:
ц = + + + + + + + + + →
106 + 72 + 58 + 61 + 41 + 59 + 28 + 96 + 78 + 9 + = 1,
108 + 50 + 57 + 36 + 34 + 89 + 48 + 9 + 85 + 101 + = 1,
32 + 97 + 22 + 64 + 49 + 103 + 66 + 57 + 52 + 4 + = 1,
29 + 39 + 45 + 92 + 28 + 70 + 28 + 78 + 51 + 23 + = 1,
53 + 72 + 97 + 5 + 88 + 25 + 28 + 100 + 3 + 9 + = 1,
68 + 10 + 44 + 104 + 92 + 67 + 49 + 3 + 58 + 80 + = 1,
62 + 84 + 54 + 39 + 39 + 36 + 30 + 43 + 3 + 5 + = 1,
24 + 49 + 1 + 55 + 29 + 28 + 23 + 1 + 45 + 10 + = 1,
≥ 0, = 1,18 .
106
72
58
61
41
59
28
96
78
9
108
50
57
36
34
89
48
9
85
101
32
97
22
64
49
103
66
57
52
4
29
39
45
92
28
70
28
78
51
23
53
72
97
5
88
25
28
100
3
9
68
10
44
104
92
67
49
3
58
80
62
84
54
39
39
36
30
43
3
5
24
49
1
55
29
28
23
1
45
10
34
Решим задачу симплекс-методом.
Симплекс-таблица нулевого шага имеет вид
Fц
0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
C b X b b i X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14 X15 X16 X17 X18
0
X11 1 106 72 58 61 41 59 28 96 78 9 1 0 0 0 0 0 0 0
0
X12 1 108 50 57 36 34 89 48 9 85 101 0 1 0 0 0 0 0 0
0
X13 1 32 97 22 64 49 103 66 57 52 4 0 0 1 0 0 0 0 0
0
X14 1 29 39 45 92 28 70 28 78 51 23 0 0 0 1 0 0 0 0
0
X15 1 53 72 97 5 88 25 28 100 3 9 0 0 0 0 1 0 0 0
0
X16 1 68 10 44 104 92 67 49 3 58 80 0 0 0 0 0 1 0 0
0
X17 1 62 84 54 39 39 36 30 43 3 5 0 0 0 0 0 0 1 0
0
X18 1 24 49 1 55 29 28 23 1 45 10 0 0 0 0 0 0 0 1
Z строка 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0
Оптимальная симплекс-таблица имеет вид
Fц
0
1
1 1 1 1
1 1 1 1 1 0 0 0 0 0 0 0 0
C b X b b i X1 X2 X3 X4 X5 X6 X7X8 X9 X10 X11 X12 X13 X14 X15 X16X17 X18
1 X8 0,00724 0,69533 0,42209 0,90908 0 0,64402 -0,08830 0 1 0,07877 0 0,00497 -0,00097 -0,00482 0 0,00806 0 0 0
1 X4 0,00052 0,99610 0,03015 -0,63149 1 -0,79328 0,60084 0 0 1,34491 0 0,01821 -0,00007 -0,00034 0 -0,01728 0 0 0
0 X14 0,04106 -112,17567 -25,40514 13,82759 0 21,62851 -11,72177 0 0 -76,39752 0 -1,52551 -0,15345 0,05051 1 0,66951 0 0 0
0 X16 0,11 -77,18901 -41,99526 48,94322 0 117,19212 -60,67041 0 0 -103,67295 0 -1,11075 -0,79423 -0,21572 0 1,23076 1 0 0
1 X10 0,00523 1,20091 -0,06656 0,65087 0 0,11111 0,17903 0 0 0,65165 1 0,00360 0,00987 -0,00905 0 0,00081 0 0 0
1 X7 0,00808 -1,15436 1,07996 0,12113 0 0,94874 1,04339 1 0 -0,62380 0 -0,02217 0,00031 0,02020 0 0,00975 0 0 0
0 X17 0,39993 21,87917 32,60814 32,64958 0 13,22762 -15,83237 0 0 -37,38291 0 -0,27694 -0,01412 -0,33988 0 0 0 1 0
0 X18 0,72617 -16,93938 22,74619 25,52841 0 49,05448 -30,74590 0 0 -21,21801 0 -0,53268 -0,10095 -0,35036 0 0,71016 0 0 1
Z с т р о к а 0,02107 0,73798 0,46565 0,04959 0 0,08941 1 0,73495 0 0 0,45153 0 0,00462 0,00913 0,00598 0 0,00134 0 0 0
Из последней симплекс-таблицы имеем:
оптимальное значение функции цели ц
∗ =0,02107,
вектора решений сопряженных задач.
= (0, 0, 0, 0.00052 , 0, 0, 0.00808, 0.00724, 0, 0.00523),
= (0.00462, 0.00913, 0.00598, 0, 0.00134 , 0, 0, 0 ).
Найдем решение игры с платежной матрицей A'.
Цена игры ∗ =
ц
∗ = 47,46.
Определим вектора оптимальных стратегий.
Для игрока А расчет производится по формуле:
′∗ = ∗ ′∗, = 1,8 .
Тогда:
∗ = 0,00462 ∙ 47,46 = 0,2192,
35
′∗ = 0,00913 ∙ 47,46 = 0,4333 ,
′∗ = 0,00598 ∙ 47,46 = 0,2838 ,
′∗ = 0 ∙ 47,46 = 0 ,
′∗ = 0,00134 ∙ 47,46 = 0,0635 ,
′∗ = 0 ∙ 47,46 = 0 ,
′∗ = 00 ∙ 47,46 = 0 ,
′∗ = 0 ∙ 47,46 = 0 .
Вектор оптимальных стратегий имеет вид ′ ∗ = (0.2192, 0.4333,
0.2838, 0, 0.0635, 0, 0, 0).
Для игрока B расчет производится по формуле:
′∗ = ∗ ′∗, = 1,10 .
′∗ = 0 ∙ 47,46 = 0,
′∗ = 0 ∙ 47,46 = 0 ,
′∗ = 0 ∙ 47,46 = 0 ,
′∗ = 0,00052 ∙ 47,46 = 0,0246 ,
′∗ = 0 ∙ 47,46 = 0 ,
′∗ = 0 ∙ 47,46 = 0 ,
′∗ = 0,00808 ∙ 47,46 = 0,3835 ,
′∗ = 0,00724 ∙ 47,46 = 0,3436 ,
′∗ = 0 ∙ 47,46 = 0 ,
′∗ = 0,00523 ∙ 47,46 = 0,2482 .
Вектор оптимальных стратегий имеет вид ′ ∗ = (0, 0, 0, 0.0246, 0,
0, 0.3835 ,0.3436 , 0, 0.2482).
Найдем цену игры с платежной матрицей А.
Цена игры равна ∗ =
∗
= 37, 46.
Ответ
Цена игры равна ∗ = 37, 46;
Вектор оптимальных стратегий игрока А:
̅∗ = (0.2192, 0.4333, 0.2838, 0, 0.0635, 0, 0, 0);
Вектор оптимальных стратегий игрока B:
∗ = (0, 0, 0, 0.0246, 0, 0, 0.3835 , 0.3436 , 0, 0.2482).
36
3 Решение биматричной игры
Постановка задачи
Конечная игра двух игроков первого (А) и второго (В) задана
платежными матрицами игроков, у каждого игрока по 2 стратегии.
Необходимо найти оптимальные векторы стратегий и выигрыши игроков.
Платежные матрицы игроков:
=
96 62
98 40
, = 48 51
47 26
Решение игры
Имеем игру двух игроков; количество стратегий у каждого игрока
равно двум; интересы игроков не противоположны. Игра является
биматричной.
Оптимальными векторами стратегий игроков в биматричной игре
являются те, при которых выполняется ситуация равновесия, т.е. стратегии
игроков являются приемлемыми одновременно для обоих игроков.
Принимаем для игрока Авероятность принятия 1-ой стратегии =
, тогда по условию нормировки вероятность принятия 2-ой стратегии =
1−;
для игрока B принимаем вероятности принятия 1-ой и 2-ой стратегий
= , =1−, соответственно.
Таким образом, найдем решение игры, используя не весь вектор
стратегий, а только вероятности принятия 1-й стратегии игроками.
Для игрока А определим , и по формулам:
= − − + ,
= − ,
= .
Для игрока В определим , и по формулам:
= − − + ,
= − ,
= .
37
Тогда равновесные ситуации найдем из пересечения решений систем 2.1 и 2.2:
(1 − ) − (1 − ) ≤ 0,
− ≥ 0.
(2.1)
(1 − ) − (1 − ) ≤ 0,
− ≥ 0.
(2.2)
Для игрока А имеем:
= −24 < 0,
= −22,
=
=
22
24
.
Так как < 0, то решение системы 2.1 для игрока А будет выглядеть так:
Решение системы A
Приемлемые ситуации A
= 0; ≥
22
24
(0, ),
22
24
.≤ ≤1
= 1; ≤
22
24
(1, ), 0 ≤ ≤
22
24
.
0< <1, =
22
24
,
22
24
. ,0< <1
Для игрока В имеем:
= −24 < 0,
= −21,
=
21
24
.
Так как < 0, то решение системы 2.2для игрока B запишется так:
Решение системы
Приемлемые ситуации
= 0, ≥
21
24
( , 0),
21
24
≤ ≤1
= 1, ≤
21
24
( , 1), 0 ≤ ≤
21
24
0< <1, =
21
24
21
24
, ,0< <1
Обозначим множество приемлемых ситуаций игрока − , игрока
− , тогда множество ситуаций равновесия найдем как пересечения
множеств приемлемых ситуаций игроков равно = ∩
38
Рисунок 2.1 – Графики множеств приемлемых ситуаций игроков
Точка пересечения множеств приемлемых ситуаций три (0, 1),(1,0) и ( , ).
Запишем вектора оптимальных стратегий игроков:
1) ̅∗ = (0, 1), ∗ = (1, 0).
Таким образом, получили решение в чистых стратегиях.
Найдем выигрыши игроков по формулам:
( ∗, ∗) =
∗ ∗,
( ∗, ∗) =
∗ ∗.
Выигрыш первого игрока: ( ∗, ∗) = 98.
Выигрыш второго игрока: ( ∗, ∗) = 51.
2) ̅∗ = (1, 0), ∗ = (0, 1).
Таким образом, получили решение в чистых стратегиях.
Найдем выигрыши игроков по формулам:
39
( ∗, ∗) =
∗
,
∗
( ∗, ∗) =
∗ ∗.
Выигрыш первого игрока: ( ∗, ∗) = 62;
Выигрыш второго игрока: ( ∗, ∗) = 47.
3) ̅∗ = ( , ), ∗ = ( , ).
Таким образом, получили решение в смешанных стратегиях.
Найдем выигрыши игроков по формулам:
( ∗, ∗) =
∗ ∗,
( ∗, ∗) =
∗ ∗.
Выигрыш первого игрока: ( ∗, ∗) = 2236.
Выигрыш второго игрока: ( ∗, ∗) = 735.
Ответ
1)Вектор оптимальных стратегий игрока А:
̅∗ = (0, 1).
Выигрыш игрока А при оптимальных стратегиях:
( ∗, ∗) = 98.
Вектор оптимальных стратегий игрока B:
∗ = (1, 0).
Выигрыш игрока В при оптимальных стратегиях:
( ∗, ∗) = 51.
2)Вектор оптимальных стратегий игрока А:
̅∗ = (1, 0).
40
Выигрыш игрока А при оптимальных стратегиях:
( ∗, ∗) = 62.
Вектор оптимальных стратегий игрока B:
∗ = (0, 1).
Выигрыш игрока В при оптимальных стратегиях:
( ∗, ∗) = 47.
3)Вектор оптимальных стратегий игрока А:
̅∗ = ( , ).
Выигрыш игрока А при оптимальных стратегиях:
( ∗, ∗) = 2236.
Вектор оптимальных стратегий игрока B:
∗ = ( , ).
Выигрыш игрока В при оптимальных стратегиях:
( ∗, ∗) = 735 .
4 Решение задачи о максимальном потоке
Постановка задачи
Задана транспортная сеть (рисунок 3.1). Найти совокупность потоков по
ребрам транспортной сети при условии максимизации мощности потока по сети.
Рисунок 3.1 – Транспортная сеть
41
Решение
Введем обозначения:
- поток по ребру (i, j),
- исток,
- сток.
Искомая совокупность потоков должна удовлетворять следующим
условиям:
1) поток по ребру в прямом направлении численно равен по модулю
потоку в обратном направлении и противоположен по знаку:
= −
;
2) равенство количества вещества, поступившего в вершину и
количество вещества, вышедшего из неё:
=
, ∉
, ∉
,
где- некоторая вершина, не являющаяся ни истоком, ни стоком;
- множество номеров вершиндля дуг, входящих в ;
- множество номеров вершин для дуг, выходящих из l.
3) количества вещества, вышедшего из истока равно количеству
вещества пришедшего в сток, и является мощностью потока по сети:
=
= ,
где - множество номеров вершин для дуг, выходящих из истока;
- множество номеров вершиндля дуг, входящих в сток;
- мощность потока по сети.
Для решения задачи воспользуемся алгоритмом Форда-Фалкерсона.
42
Таблица 7 – Матрица пропускных способностей, отображающая ход
алгоритма Форда-Фалкерсона
i
j
1
2
3
4
5
6
7
8
9
10
1
96
-18-13
75
-12
68
-38 -9
2
62
+18 +13
48
-18 -13
3
51
+18 +13
31
-18 -13
40
4
49
+18 +13
79
-13
18
-18
5
91
+12
12
-12
22
6
54
+12
56-12
-9 -13
39
+9+13
7
47 +12
+9 +13
42 -12
-9 -13
8
11
+38+9
98
87
47
-38-9
9
24
+13
93
-9-13
26
+38+9
38
-38
10
86
+18
16 +12
+13 +9
11
+38
На нулевом шаге алгоритма найдем три допустимых потока на сети:
:1 → 8→9→ 10, = = = 38;
:1 → 2→3→4→ 10, = = = = 18;
:1 → 5→6→7→ 10, = = = = 12.
Мощность потока по сети на 0-м шаге найдем по формуле:
=
=
= + + = + + = 68.
43
Проверим, существует ли путь по ненасыщенным ребрам из истока в
сток, для этого составим списки:
( : 2,5,8), (2: 3), (5: ∅), (8: 9), (3: 4), (9: 6), (4: ∅), (6: 7), (7: 10 = ).
Решение не оптимально, так как идя по ненасыщенным ребрам из
истока пришли в сток, следовательно, на сети существует полный путь :
:1→8→9→6→7→ 10, = = = = = 9.
Мощность потока по сети на первом шаге:
= + 9 = 77.
Проверим, существует ли путь по ненасыщенным ребрам из истока в
сток, для этого составим списки:
( : 2,5,8), (2: 3), (5: ∅), (8: ∅)(3: 4)(4: 9)(9: 6)(6: 7)(7: 10 = ).
Решение не оптимально, так как идя по ненасыщенным ребрам из
истока пришли в сток, следовательно, на сети существует полный путь :
: 1→2→3→4→9→6→7→ 10, = = = = =
= = 13.
Мощность потока по сети на втором шаге:
= + 11 = 90.
Проверим, существует ли путь по ненасыщенным ребрам из истока в
сток, для этого составим списки:
( : 2,5,8), (2: 3), (5: ∅), (8: ∅)(3: ∅).
Полного пути по ненасыщенным ребрам из истока в сток нет,
следовательно, решение оптимально.
Ответ
Максимальный поток = 90.
Распределение потока по ребрам сети: = 31, = 12, = 47,
= 31, = 31, = 13, = 18, = 12, = 34, =
= 34, = 47, = 22, = 38.
44
Анализ и рекомендации
Рисунок 3.2 – Распределение оптимального потока по ребрам сети.
Примечание к рисунку 3.2: через « / » написаны пропускная
способность ребра и поток, прошедший через ребро, соответственно.
Из рисунка 3.2 видно, что пропускные способности некоторых ребер
недоиспользованы, а именно:
- недоиспользование ребра 1→2 равно 65 ед;
- недоиспользование ребра 1→5 равно 63 ед;
-недоиспользование ребра 1→8 равно 21 ед;
-недоиспользование ребра 2→3 равно 17 ед;
-недоиспользование ребра 4→9 равно 66 ед;
-недоиспользование ребра 6→7 равно 22 ед;
-недоиспользование ребра 7→10 равно 8 ед;
-недоиспользование ребра 9→6 равно 71 ед.
Рекомендация: снизить пропускные способности данных ребер, чтобы
уменьшить объем недоиспользования.
Ребра 5→8 и 8→3 не были использованы, поэтому имеется
возможность убрать их из сети.
Ребра3→4, 8→9, 5→6,9→10,4→10 являются насыщенными (узкими
местами сети), сдерживающими максимальный поток.
Рекомендация: повысить пропускные способности данных ребер, что
должно привести к увеличению максимального потока и уменьшению
объемов недоиспользования.
45
Список литературы
1.Чуркин Г. Динамическое программирование в задачах исследования
операций и управления, Саратов, 1973
2. Акоф Р., Сасиени М. Основы исследования операций, «Мир», 1960
3. Кардаш В.А., Ладейщикова Е.Н. «Моделирование экономической
ситуации и оптимизация решений в условиях рынка». Методические
указания для студентов экономических специальностей по курсу
«Математическое моделирование экономических процессов».
/ Новочеркасск: ЮРГТУ, 2001, - 25с.
4. Горчаков А.А., Орлова И.В. “Компьютерные экономические
модели”,-М; “Компьютер”, “ЮНИТИ”,1995.
46
Приложение А. Контрольные примеры. Инструкция пользователю
программы, реализующей симплекс-метод
Программа, реализующая симплекс-метод не приводит задачу к
каноническому виду. Мы сами вводим задачу линейного программирования
уже в канонической форме, в виде таблицы, создаваемой в MicrosoftExcel.
Программа выводит первую и последнюю симплекс-таблицы. Она сама
выбирает разрешающий столбец и строку, которые обеспечивают
максимальное возрастание или убывание целевой функции, а также
автоматически пересчитывает все таблицы.
Для решения задачи линейного программирования необходимо
запустить программу, в открывшемся диалоговом окне нажать кнопку
«файл», затем выбрать пункт «загрузить Excel». После того, как программа
загрузит файл, нажать кнопку «Вычислить». После вычисления, на экране
появится окно с сообщением «Анализ завершен успешно. Пройдено n
итераций», закрыв это окно, мы увидим последнюю симплекс таблицу.
Рисунок А.1 - Диалоговое окно, после загрузки файла
47
Рисунок А.2 - Сообщение о завершение вычислений
Рисунок А.3 - Результат вычислений
ьшение так как при это суммарная прибыль увеличивается на 8520
д.ед.я прибыль уменьшается на суммарная прибыль уменьшается н
Информация о работе Моделирование и оптимизация деятельности предприятия. Анализ и корректировка оптимального плана