Анализ акционерного капитала
Задача №1 (Симплекс метод
решения задачи линейного программирования.)
Найти F max = 9x1+ 10x2 + 16x3, при ограничениях:
Запишем задачу в
каноническом виде:
F=9x1+ 10x2 + 16x3 → max
Заполним начальную
таблицу:
Таблица 0.
|
0
|
9
|
10
|
16
|
0
|
0
|
0
|
Отношение,
θ
|
|
i
|
|
Базис
|
|
|
|
|
|
|
|
|
1
|
0
|
|
360
|
18
|
15
|
12
|
1
|
0
|
0
|
30
|
|
2
|
0
|
|
192
|
6
|
4
|
8
|
0
|
1
|
0
|
24
|
|
3
|
0
|
|
180
|
5
|
3
|
3
|
0
|
0
|
1
|
60
|
|
∆j
|
0
|
-9
|
-10
|
-16
|
0
|
0
|
0
|
|
|
Zj
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
Zj вычисляется по формуле
Оценки (∆j)
вычисляются по формуле 
, где 
-
коэффициент из первой строки таблицы.
Выбираем минимальную
(отрицательную) оценку. Она определяет направляющий столбец.
Заполняем столбец «θ», по минимальному значению
определяем направляющую строку.
На пересечение строки и
столбца находится направляющий элемент.
Заполняем новую таблицу
Таблица 1.
|
0
|
9
|
10
|
16
|
0
|
0
|
0
|
Отношение,
θ
|
|
i
|
|
Базис
|
|
|
|
|
|
|
|
|
1
|
0
|
|
72
|
9
|
9
|
0
|
1
|
|
0
|
8
|
|
2
|
16
|
|
24
|
|
|
1
|
0
|
|
0
|
48
|
|
3
|
0
|
|
108
|
|
|
0
|
0
|
-
|
1
|
72
|
|
∆j
|
384
|
3
|
-2
|
0
|
0
|
2
|
0
|
|
|
Zj
|
384
|
12
|
8
|
0
|
0
|
2
|
0
|
Изменяется базис в
позиции направляющей строки. Базисным становится вектор, соответствующий
направляющему столбцу, т. е.
Столбец становится базисным, то есть
единичным.
Новые значения в
направляющей строке получаем делением элементов этой строки на направляющий
элемент.
Остальные элементы в
небазисных столбцах и в столбце вычисляем по правилу треугольника.
Выбираем минимальную отрицательную
оценку. Она определяет направляющий столбец.
Заполняем столбец «θ»
По минимальному значению
определяем направляющую строку.
На пересечении
направляющей строки и столбца находится направляющий элемент.
Заполнение второй таблицы
осуществляется по аналогии с предыдущей.
Таблица 2.
|
0
|
9
|
10
|
16
|
0
|
0
|
0
|
Отношение,
θ
|
|
i
|
|
Базис
|
|
|
|
|
|
|
|
|
1
|
10
|
|
8
|
1
|
1
|
0
|
|
-
|
0
|
______
|
|
2
|
16
|
|
20
|
|
0
|
1
|
-
|
|
0
|
______
|
|
3
|
0
|
|
96
|
|
0
|
0
|
|
-
|
1
|
______
|
|
∆j
|
400
|
5
|
0
|
0
|
|
|
0
|
|
|
Zj
|
400
|
14
|
10
|
16
|
|
|
0
|
Так как нет отрицательных
оценок ∆j, значит выполняется признак оптимальности и не вводились искусственные
переменные, то получено оптимальное решение.
Ответ:
Максимальное значение
функции F max =400 достигается в точке с
координатами:
=0
=8
=20
=0
=0
=96
Задача №2 (Метод Литтла)
Найти кратчайший путь в
графе, заданном графически в виде чертежа, методом Литтла.
Из чертежа запишем
матрицу расстояний. (Расстояние от т.1 до т.2 равно:
,
и т.д.)
|
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
∞
|
18,87
|
49,48
|
51,86
|
80,51
|
97,42
|
|
2
|
18,87
|
∞
|
32,06
|
34,48
|
65,15
|
84,01
|
|
3
|
49,48
|
32,06
|
∞
|
31,76
|
61,19
|
83,20
|
|
4
|
51,86
|
34,48
|
31,76
|
∞
|
32,14
|
53,15
|
|
5
|
80,51
|
65,15
|
61,19
|
32,14
|
∞
|
22,14
|
|
6
|
97,42
|
84,01
|
83,20
|
53,15
|
22,14
|
∞
|
Предположим что
кратчайший путь будет следующим:
т.1→ т.2→
т.3→ т.4→ т.5→ т.6→т.1 и составит 
Решение: Первый этап.
Шаг 1. Приведем матрицу
расстояний по строкам и столбцам
(в строке вычитаем из
каждого элемента минимальный, затем в столбцах)
|
1
|
2
|
3
|
4
|
5
|
6
|
|
|
1
|
∞
|
18,87
|
49,48
|
51,86
|
80,51
|
97,42
|
18,87
|
|
2
|
18,87
|
∞
|
32,06
|
34,48
|
65,15
|
84,01
|
18,87
|
|
3
|
49,48
|
32,06
|
∞
|
31,76
|
61,19
|
83,20
|
31,76
|
|
4
|
51,86
|
34,48
|
31,76
|
∞
|
32,14
|
53,15
|
31,76
|
|
5
|
80,51
|
65,15
|
61,19
|
32,14
|
∞
|
22,14
|
22,14
|
|
6
|
97,42
|
84,01
|
83,20
|
53,15
|
22,14
|
22,14
|
↓
|
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
∞
|
0
|
30,61
|
32,99
|
61,64
|
78,55
|
|
2
|
0
|
∞
|
13,19
|
15,61
|
46,28
|
65,14
|
|
3
|
17,72
|
0,30
|
∞
|
0
|
29,43
|
51,44
|
|
4
|
20,10
|
2,72
|
0
|
∞
|
0,38
|
21,39
|
|
5
|
58,37
|
43,01
|
39,05
|
10,00
|
∞
|
0
|
|
6
|
75,28
|
61,87
|
61,06
|
31,01
|
0
|
∞
|
|
0
|
0
|
0
|
0
|
0
|
0
|
↓
|
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
∞
|
0
|
30,61
|
32,99
|
61,64
|
78,55
|
|
2
|
0
|
∞
|
13,19
|
15,61
|
46,28
|
65,14
|
|
3
|
17,72
|
0,30
|
∞
|
0
|
29,43
|
51,44
|
|
4
|
20,10
|
2,72
|
0
|
∞
|
0,38
|
21,39
|
|
5
|
58,37
|
43,01
|
39,05
|
10,00
|
∞
|
0
|
|
6
|
75,28
|
61,87
|
61,06
|
31,01
|
0
|
∞
|
Шаг 2. Определим оценки
нулевых клеток:
Шаг 3. Вычеркиваем клетку
с максимальной оценкой. Включаем данную клетку в путь обхода. (5 – 6)
Шаг 4. Переписываем
матрицу расстояний, накладывая запрет на одну из клеток для исключения
преждевременного замыкания контура (в клетку 6-5 ставим ∞).
|
1
|
2
|
3
|
4
|
5
|
|
1
|
∞
|
0
|
30,61
|
32,99
|
61,64
|
|
2
|
0
|
∞
|
13,19
|
15,61
|
46,28
|
|
3
|
17,72
|
0,30
|
∞
|
0
|
29,43
|
|
4
|
20,10
|
2,72
|
0
|
∞
|
0,38
|
|
6
|
75,28
|
61,87
|
61,06
|
31,01
|
∞
|
Далее повторяем шаги 1 –
4, пока не дойдем до одной клетки.
Второй этап.
Шаг 1. Приведем матрицу
расстояний по строкам и столбцам.
|
1
|
2
|
3
|
4
|
5
|
|
1
|
∞
|
0
|
30,61
|
32,99
|
61,64
|
|
2
|
0
|
∞
|
13,19
|
15,61
|
46,28
|
|
3
|
17,72
|
0,30
|
∞
|
0
|
29,43
|
|
4
|
20,10
|
2,72
|
0
|
∞
|
0,38
|
|
6
|
75,28
|
61,87
|
61,06
|
31,01
|
∞
|
|
0
|
0
|
0
|
0
|
0,38
|
↓
|
1
|
2
|
3
|
4
|
5
|
|
1
|
∞
|
0
|
30,61
|
32,99
|
61,26
|
|
2
|
0
|
∞
|
13,19
|
15,61
|
45,90
|
|
3
|
17,72
|
0,30
|
∞
|
0
|
29,05
|
|
4
|
20,10
|
2,72
|
0
|
∞
|
0
|
|
6
|
75,28
|
61,87
|
61,06
|
31,01
|
∞
|
Шаг 2. Определим оценки
нулевых клеток:
Шаг 3. Вычеркиваем клетку
с максимальной оценкой. Включаем данную клетку в путь обхода. (1 – 2)
Шаг 4. Переписываем
матрицу расстояний, накладывая запрет на одну из клеток для исключения
преждевременного замыкания контура (в клетку 2 – 1 ставим ∞).
|
1
|
3
|
4
|
5
|
|
2
|
∞
|
13,19
|
15,61
|
45,90
|
|
3
|
17,72
|
∞
|
0
|
29,05
|
|
4
|
20,10
|
0
|
∞
|
0
|
|
6
|
75,28
|
61,06
|
31,01
|
∞
|
Третий этап.
Шаг 1. Приведем матрицу
расстояний по строкам и столбцам.
|
1
|
3
|
4
|
5
|
|
2
|
∞
|
13,19
|
15,61
|
45,90
|
|
3
|
17,72
|
∞
|
0
|
29,05
|
|
4
|
20,10
|
0
|
∞
|
0
|
|
6
|
75,28
|
61,06
|
31,01
|
∞
|
|
17,72
|
0
|
0
|
0
|
↓
|
1
|
3
|
4
|
5
|
|
|
2
|
∞
|
13,19
|
15,61
|
45,90
|
13,19
|
|
3
|
0
|
∞
|
0
|
29,05
|
0
|
|
4
|
2,38
|
0
|
∞
|
0
|
0
|
|
6
|
57,56
|
61,06
|
31,01
|
∞
|
31,01
|
↓
|
1
|
3
|
4
|
5
|
|
2
|
∞
|
0
|
2,42
|
32,71
|
|
3
|
0
|
∞
|
0
|
29,05
|
|
4
|
2,38
|
0
|
∞
|
0
|
|
6
|
26,55
|
30,05
|
0
|
∞
|
Шаг 2. Определим оценки
нулевых клеток:
Шаг 3. Вычеркиваем клетку
с максимальной оценкой. Включаем данную клетку в путь обхода. (4 – 5)
Шаг 4. Переписываем
матрицу расстояний, накладывая запрет на одну из клеток для исключения
преждевременного замыкания контура (в клетку 6 – 4 ставим ∞).
|
1
|
3
|
|
2
|
∞
|
0
|
2,42
|
|
3
|
0
|
∞
|
0
|
|
6
|
26,55
|
30,05
|
∞
|
Четвертый этап.
Шаг 1. Приведем матрицу
расстояний по строкам и столбцам.
|
1
|
3
|
4
|
|
|
2
|
∞
|
0
|
2,42
|
0
|
|
3
|
0
|
∞
|
0
|
0
|
|
6
|
26,55
|
30,05
|
∞
|
26,55
|
↓
|
1
|
3
|
4
|
|
2
|
∞
|
0
|
2,42
|
|
3
|
0
|
∞
|
0
|
|
6
|
0
|
3,50
|
∞
|
Шаг 2. Определим оценки
нулевых клеток:
Шаг 3. Вычеркиваем клетку
с максимальной оценкой. Включаем данную клетку в путь обхода. (3 – 4)
Шаг 4. Переписываем
матрицу расстояний, накладывая запрет на одну из клеток для исключения
преждевременного замыкания контура (в клетку 6 – 3 ставим ∞).
Пятый этап.
Остались не
задействованными связи 2 – 3 и 6 – 1.
В результате получаем
следующую цепочку:
1→ 2→ 3 →
4→ 5→ 6 →1
Длина пути составляет:
L=18,87+32,06+31,76+32,14+22,14+97,42=234,39
это и есть кратчайший
путь.
