MATMEDECONOM (1)
.docx-
Решим прямую задачу линейного программирования М - симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 3x1 - 2x2 при следующих условиях-ограничений.
2x1 + x2 = 15
3х1 + 2х2 =6
4x1 - 2x2 = 18
5x1 - 5x2 = 16
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. Во 2-м неравенстве смысла (≥) вводим базисные переменную -x4 и х7. В 3-м неравенстве смысла (≤) вводим базисную переменную x5. В 4-м неравенстве смысла (≤) вводим базисную переменную x6.
f(x) = 3*x1-2*x2+x3*0+x4*0 + x5*0 + x6*0 - M*x7 → max
2x1 + x2 + x3*1+x4*0 + x5*0 + x6*0 = 15
3*х1 + 2*х2 + х3*0 - х4*1 + х5*0 + х6*0+ 1х7 =6
4* x1 - 2*x2 + X3*0 + X4*0 + X5*1 + X6*0 = 18
5*x1 - 5*x2 + X3*0 + X4*0 + X5*0 + X6*1 = 16
№ интерации |
базис |
Сi |
Решение bi |
3 |
-2 |
0 |
0 |
0 |
0 |
- M |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
||||
0
|
x3 |
0 |
15 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
x7 |
-M |
6 |
3 |
2 |
0 |
-1 |
0 |
0 |
1 |
|
x5 |
0 |
18 |
4 |
-2 |
0 |
0 |
1 |
0 |
0 |
|
x6 |
0 |
16 |
5 |
-5 |
0 |
0 |
0 |
1 |
0 |
|
- f |
Δj |
6М |
3+3M |
-2+2M |
0 |
-M |
0 |
0 |
0 |
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (15 : 2 , 6 : 3, 18 : 4, 16 : 5 ) = 2
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки. Получаем новую симплекс-таблицу:
№ интерации |
базис |
Сi |
Решение bi |
3 |
-2 |
0 |
0 |
0 |
0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
||||
|
x3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
x1 |
3 |
7 1/2 |
1 |
1/2 |
1/2 |
0 |
0 |
0 |
|
x5 |
0 |
-30 |
14 |
2 |
-4 |
0 |
0 |
1 |
|
x6 |
0 |
-21 1/2 |
0 |
-7 1/2 |
-2 1/2 |
0 |
0 |
1 |
|
- f |
Δj |
-22 1/2 |
0 |
-3 1/2 |
-1 1/2 |
0 |
0 |
0 |
В последней симплекс-таблице в строке симплекс - разности все значения < 0.
f = 22 1/2
X=(7 1/2; 0; 0; 0; 30; 21 1/2)
-
Решим прямую задачу линейного программирования М - симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 50x1+27x2+34x3+54x4 при следующих условиях-ограничений.
5*x1+4*x2+6*x3+7*x4 = 275
2*x1+0*x2+4*x3+2*х4=100
3*х1+2*x2+0*x3+1*x4=85
№ интерации |
базис |
Сi |
Решение bi |
50 |
27 |
34 |
54 |
0 |
0 |
0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
х7 |
||||
0
|
x5 |
0 |
275 |
5 |
4 |
6 |
7 |
1 |
0 |
0 |
x6 |
0 |
100 |
2 |
0 |
4 |
2 |
0 |
1 |
0 |
|
x7 |
0 |
85 |
3 |
2 |
0 |
1 |
0 |
0 |
1 |
|
- f |
j |
0 |
50 |
27 |
34 |
54 |
0 |
0 |
0 |
Выбираем наибольшую положительную симплекс - разность (которая определит ведущий столбец). Чтобы определить ведущую строку, вычисляем неотрицательное отношение типа: min {bi/aij}. Новая симплекс-таблица:
№ интерации |
базис |
Сi |
Решение bi |
50 |
27 |
34 |
54 |
0 |
0 |
0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
||||
1 |
x4 |
54 |
39 2/7 |
5/7 |
4/7 |
6/7 |
1 |
1/7 |
0 |
0 |
x6 |
0 |
21 3/7 |
4/7 |
-1 1/7 |
2 2/7 |
0 |
- 2/7 |
1 |
0 |
|
x7 |
0 |
45 5/7 |
2 2/7 |
1 3/7 |
- 6/7 |
0 |
- 1/7 |
0 |
1 |
|
- f |
j |
-2121 3/7 |
11 3/7 |
-3 6/7 |
-12 2/7 |
0 |
-7 5/7 |
0 |
0 |
Аналогично выбираем наибольшую положительную симплекс - разность (которая определит ведущий столбец). Чтобы определить ведущую строку, вычисляем неотрицательное отношение типа: min {bi/aij}. Новая симплекс-таблица:
№ интерации |
базис |
Сi |
Решение bi |
50 |
27 |
34 |
54 |
0 |
0 |
0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
||||
2 |
x4 |
54 |
25 |
0 |
1/8 |
1 1/8 |
1 |
1/5 |
0 |
- 1/3 |
x6 |
0 |
10 |
0 |
-1 1/2 |
2 1/2 |
0 |
- 1/4 |
1 |
- 1/4 |
|
x1 |
50 |
20 |
1 |
5/8 |
- 3/8 |
0 |
-0 |
0 |
4/9 |
|
- f |
j |
-2350 |
0 |
-11 |
-8 |
0 |
-7 |
0 |
-5 |
В последней симплекс-таблице в строке симплекс - разности все значения < 0
f = 2350
X=(20; 0; 0; 25; 0; 10).
Решим двойственную задачу:
b = (50, 27, 34, 54)
275
с = 100
85
5 4 6 7
А = 2 0 4 2
3 2 0 1
Транспортируем матрицу:
5 2 3
Ат = 4 0 2
6 4 0
7 2 1
F(x) = 275х1 + 100х2 + 85х3 → min
5х1 + 2х2 + 3х3 = 50
4х1 + 0х2 + 2х3 = 27
6х1 + 4х2 + 0х3 = 34
7х1 + 2х2 + 1х3 = 54
Решение двойственной задачи:
Z = 2350
y1 = 7 y5 = 11
y2 = 0 y6 = 8
y3 = 5 y7 = 0
y4 = 0
-
3.1. Поиск опорного плана методом северо - западного угла:
Вариант задачи |
||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие |
А1 |
1) 65 7 |
2)55 4 |
15 |
9 |
14 |
120 (55) (0) |
А2 |
11 |
3)35 2 |
4)60 7 |
5)55 3 |
10 |
150 (90) (0) |
А3 |
4 |
5 |
12 |
6)15 8 |
7) 85 17 |
100 (0) |
Потребность |
65 (0) |
90 (35) (0) |
60 (0) |
70 (15) (0) |
300 (215) |
|
Добавим фиктивную строку:
Вариант задачи |
||||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
Наличие |
А1 |
1) 65 7 |
2)55 4 |
15 |
9 |
14 |
120 (55) (0) |
А2 |
11 |
3)35 2 |
4)60 7 |
5)55 3 |
10 |
150 (90) (0) |
А3 |
4 |
5 |
12 |
6)15 8 |
7) 85 17 |
100 (0) |
А4 |
17 |
17 |
17 |
17 |
8)215 17 |
215 (0) |
Потребность |
65 |
90 |
60 |
70 |
300 |
|
-
Метод наименьшей стоимости:
Для всех свободных клеток находим значения γij = cij – (αi+βj)
α1 + β5 = С15 |
14 |
α1 |
7 |
β5 |
7 |
|
γ11 |
1 |
α2 + β2 = С22 |
2 |
α2 |
0 |
β2 |
2 |
|
γ12 |
-5 |
α2 + β4 = С23 |
3 |
α2 |
0 |
β4 |
3 |
|
γ13 |
1 |
α3 + β1 = С31 |
4 |
α3 |
5 |
β1 |
-1 |
|
γ14 |
-1 |
α3 + β3 = С33 |
12 |
α3 |
5 |
β3 |
7 |
|
γ21 |
12 |
α3 + β4 = С34 |
8 |
α3 |
5 |
β4 |
3 |
|
γ23 |
0 |
α4 + β3 = С43 |
17 |
α4 |
10 |
β3 |
7 |
|
γ25 |
3 |
α4 + β5 = С45 |
17 |
α4 |
10 |
β5 |
7 |
|
γ32 |
-2 |
|
|
|
|
|
|
|
γ35 |
5 |
|
|
|
|
|
|
|
γ41 |
8 |
|
|
|
|
|
|
|
γ42 |
5 |
|
|
|
|
|
|
|
γ44 |
4 |
Среди посчитанных гамм, выбираем « - » наибольшее по модулю. Для клеткиЮ которой соответствует эта гамма строится цикл:
α1 + β2 = С12 |
4 |
α1 |
0 |
β2 |
4 |
|
γ11 |
1 |
α1 + β5 = С15 |
14 |
α1 |
0 |
β5 |
14 |
|
γ13 |
1 |
α2 + β2 = С22 |
2 |
α2 |
-2 |
β2 |
4 |
|
γ14 |
4 |
α2 + β4 = С24 |
3 |
α2 |
-2 |
β4 |
5 |
|
γ21 |
7 |
α3 + β1 = С31 |
4 |
α3 |
-2 |
β1 |
6 |
|
γ23 |
-5 |
α3+ β3 = С33 |
12 |
α3 |
-2 |
β3 |
14 |
|
γ25 |
-2 |
α4 + β3 = С43 |
17 |
α4 |
3 |
β3 |
14 |
|
γ32 |
3 |
α4 + β5 = С45 |
17 |
α4 |
3 |
β5 |
14 |
|
γ34 |
5 |
|
|
|
|
|
|
|
γ35 |
5 |
|
|
|
|
|
|
|
γ41 |
8 |
|
|
|
|
|
|
|
γ42 |
10 |
|
|
|
|
|
|
|
γ44 |
9 |