Автор работы: Пользователь скрыл имя, 20 Ноября 2013 в 21:24, курсовая работа
Целью выполнения данной курсовой работы является овладение математическими методами решения экономических задач.
Основные задачи:
- научиться строить экономико-математические модели;
- освоить симплекс-метод табличного решения задачи линейного программирования;
- освоить двойственный симплекс-метод решения задачи линейного программирования;
Введение
Описание отрасли………………………………………………………….3
Задача оптимального распределения ресурсов………………………….5
Транспортная задача………………………………………………….…..21
Задача теории игр…………………………………………………………24
Обоснование распределения финансовых ресурсов между проектами (динамическое программирование).....……………………………..…...29
Заключение…………………………..……………………………………..……33
Заполняем индексную строку:
D1 = 0×3 + 0×1 + 0×2 – 4 = -4;
D2 = 0×1 + 0×3 + 0×2 – 6 = -6;
D3 = 0×1 + 0×2 + 0×6 – 8 = -8;
D4 = 0; D5 = 0; D6 = 0;
D7= 0×30 + 0×20 + 0×52 = 0.
|
сi |
сj |
4 |
6 |
8 |
0 |
0 |
0 |
|
|
Базисные переменные (БП) |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
bi | |
|
0 |
x4 |
3 |
1 |
2 |
1 |
0 |
0 |
30 |
0 |
x5 |
2 |
3 |
4 |
0 |
1 |
0 |
20 |
0 |
х6 |
1 |
2 |
6 |
0 |
0 |
1 |
52 |
Dj |
-4 |
-6 |
-8 |
0 |
0 |
0 |
0 | |
Первое опорное решение имеет вид: = (0, 0, 0, 30, 20, 52), = 0. (компоненты опорного решения выписывают для базисных переменных из столбца свободных членов bi; переменные, не входящие в базис, имеют значение 0). В рассматриваемом случае переменные х1, х2, х3. не входят в базис, поэтому их компоненты в опорном решении равны нулю, базисные переменные имеют значения х4 = 30, х5 = 20, х6 = 52. Значение целевой функции берут из последней строки столбца . На данном шаге симплекс-метода = 0.
Следует проверить первое опорное решение на оптимальность.
В рассматриваемом случае
первое опорное решение не оптимальное,
поскольку имеются три
D3 = - 8.
Следовательно, нужно сделать следующий шаг симплекс-метода: ввести в базис переменную, которую нужно улучшить.
Такой переменной является переменная из столбца с наибольшей по абсолютной величине оценкой |D3| = 8, т.е. переменная х3.
|
сi |
сj |
4 |
6 |
8 |
0 |
0 |
0 |
min | |
|
Базисные переменные (БП) |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
bi |
bi/ hij | |
|
0 |
x4 |
3 |
1 |
2 |
1 |
0 |
0 |
30 |
30/2 |
0 |
x5 |
2 |
3 |
“4” |
0 |
1 |
0 |
20 |
20/4 |
0 |
х6 |
1 |
2 |
6 |
0 |
0 |
1 |
52 |
52/6 |
Dj |
-4 |
-6 |
-8 |
0 |
0 |
0 |
0 |
- | |
Теперь следует определить, какую переменную нужно вывести из базиса.
В столбце оценочных отношений min{bi/ hij} отражены отношения свободных членов к элементам из разрешающего столбца, минимальным является отношение 20/4, соответствующее строке переменной х5, следовательно, эта строка – разрешающая, а переменная х6 выводится из базисных переменных. На пересечении ключевой строки и ключевого столбца находится ключевой элемент «4».
Переход ко второму шагу симплекс-метода.
Заполним симплекс-таблицу второго шага для варианта 0. Вместо переменной х5 вводим в базис переменную х3, в целевой функции ей соответствует коэффициент 8, который вносится в соответствующую клетку столбца сi.
В строке, соответствующей переменной х3 переписываем элементы из ключевой строки предыдущей таблицы, предварительно разделив их на ключевой элемент «4»:
|
сi |
сj |
4 |
6 |
8 |
0 |
0 |
0 |
min | |
|
Базисные переменные (БП) |
х1 |
x2 |
х3 |
х4 |
х5 |
х6 |
bi |
bi/ hij | |
|
0 |
x4 |
0 |
1 |
0 |
|||||
8 |
x3 |
1/2 |
3/4 |
1 |
0 |
1/4 |
0 |
5 |
|
0 |
x6 |
0 |
0 |
1 |
|||||
Dj |
0 |
0 |
0 |
||||||
Заполняем столбцы для базисных переменных х4, х3, х6:
|
сi |
сj |
4 |
6 |
8 |
0 |
0 |
0 |
min | |
|
Базисные переменные (БП) |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
bi |
bi/ hij | |
|
0 |
x4 |
||||||||
|
8 |
x3 |
||||||||
|
0 |
x6 |
||||||||
|
Dj |
|
||||||||
Остальные клетки заполняем по правилу прямоугольника, отмечая, что ключевой элемент «4» находится в первой строке и втором столбце предыдущей таблицы:
;
;
;
;
;
;
;
|
сi |
сj |
4 |
6 |
8 |
0 |
0 |
0 |
min | |
|
Базисные переменные (БП) |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
bi |
bi/ hij | |
|
0 |
x4 |
2 |
-1/2 |
0 |
1 |
-2 |
0 |
20 |
|
8 |
x3 |
1/2 |
3/4 |
1 |
0 |
1/4 |
0 |
5 |
|
0 |
x6 |
-2 |
-5/2 |
0 |
0 |
-6 |
1 |
22 |
|
Dj |
0 |
0 |
0 |
||||||
.
Находим оценки переменных:
D1 =0.2 + 8×1/2 + 0×(-2)– 4 = 0;
D2 = 0.(-1/2) + 8×3/4 + 0×(-5/2) – 6 = 0 ;
D5 = 0.(-2) + 8.1/4 + 0×1 – 0 = 2 ;
D7 = 0.(20) + 8×5 + 0×(22) = 40.
|
сi |
сj |
3 |
4 |
1 |
0 |
0 |
0 |
min | |
|
Базисные переменные (БП) |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
bi |
bi/ hij | |
|
0 |
x4 |
2 |
-1/2 |
0 |
1 |
-2 |
0 |
20 |
|
8 |
x3 |
1/2 |
3/4 |
1 |
0 |
1/4 |
0 |
5 |
|
0 |
x6 |
-2 |
-5/2 |
0 |
0 |
-6 |
1 |
22 |
|
Dj |
0 |
0 |
0 |
0 |
2 |
0 |
40 |
||
Поскольку все оценки положительные Dj, то полученное опорное решение является оптимальным: = (0, 0, 5, 20, 0, 22), а максимальное значение целевой функции равно = 40.
Учитывая соответствие переменных взаимодвойственных задач, можно выписать оптимальное решение двойственной задачи. Значения соответствующих переменных берут из последней строки последней симплекс-таблицы:
|
сi |
сj |
4 |
6 |
8 |
0 |
0 |
0 |
|
|
Базисные переменные (БП) |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
bi | |
|
0 |
x4 |
2 |
-1/2 |
0 |
1 |
-2 |
0 |
20 |
8 |
x3 |
1/2 |
3/4 |
1 |
0 |
1/4 |
0 |
5 |
0 |
x6 |
-2 |
-5/2 |
0 |
0 |
-6 |
1 |
22 |
Dj |
0 |
0 |
0 |
0 |
2 |
0 |
40 | |
yi |
y4 |
y5 |
y6 |
y1 |
y2 |
y3 |
||
Таким образом, = (0,2,0,0,0,0), поскольку y1 « x4, y2 « x5, y3 « x6, y4 « x1, y5 « x2, y6 « x3. Значение целевой функции = 40.
Экономический смысл всех переменных, участвующих в решении
Экономический смысл переменных, участвующих в решении отражен в таблице