15. Обоснуйте метод потенциалов с помощью основных теорем двойственности.
|
B1 |
В2 |
B3 |
|
|||
А1 |
С11 |
С12 |
C13 |
|
|||
|
Х11 |
|
X12 |
|
X13 |
a1 |
|
A2 |
С21 |
С22 |
C23 |
|
|||
|
Х21 |
|
X22 |
|
X23 |
a2 |
|
|
|
b1 |
|
b2 |
|
b3 |
|
F=c_11 x_11+c_12 x_12 〖+c〗_13 x_13+c_21 x_21+c_22 x_22+c_23 x_23→min x_11+x_12 〖+x〗_13=a_1 x_21+x_22+x_23=a_2 x_11+x_21=b_1 x_12+x_22=b_2 x_13+x_23=b_3 bij≥0 Матрица нетривиальных ограничений: 〖 x〗_11 x_12 〖 x〗_13 x_21 x_22 x_23 U_1 1 1 1 0 0 0 = a_1 U_2 0 0 0 1 1 1 = a_2 V_1 1 0 0 1 0 0 = b_1 V_2 0 1 0 0 1 0 = b_2 V_3 0 0 1 0 0 1 = b_3 ≥ ≥ ≥ ≥ ≥ ≥ c_11 c_12 c_13 c_21 c_22 c_23 →min 1 0 1 0 0 ≤〖 c〗_11 1 0 0 1 0 ≤〖 c〗_12 1 0 0 0 1 ≤〖 c〗_13 0 1 1 0 0 ≤〖 c〗_21 0 1 0 1 0≤c_22 0 1 0 0 1≤c_23 ~ ~ ~ ~ ~ 〖 a〗_1 a_2 b_1 b_2 b_3 → max u_(1 )+ v_1≤〖 c〗_11 u_(1 )+ v_2≤〖 c〗_12 u_(1 )+ v_3≤〖 c〗_13 u_(2 )+ v_1≤〖 c〗_21 u_(2 )+ v_2≤〖 c〗_22 u_(2 )+ v_3≤〖 c〗_23 φ=〖 a〗_1 u_(1 )+a_2 u_(2 )+ b_1 v_1+b_2 v_2+b_3 v_3→maxUi+Vj≤Cij
∆ij= Ui+Vj-Cij≤0
Ui+Vj= Cij для занятых клеток
Если X^* и (U^* V^*) оптимальное решение ВДЗ, то 〖(U〗_i^*+V_j^*- C_ij)X_ij^*=0 Для занятой клетки X_ij^*≥0 => U_i^*+V_j^* 〖=C〗_ij
16. Метод искусственного базиса. Как на основании применения этого метода можно сделать вывод о существовании допустимого базиса? Приведите примеры.
В
каждое уравнение, дающее отрицательную
компоненту в базисном решении, вводим
свою новую неотрицательную искусственную
переменную y1,
,…,
,
которая имеет тот же знак, что и свободный
член в правой части уравнения. В первой
таблице
включаем в число основных все искусственные переменные и те
обычные добавочные переменные, которые определяют неотрицательные компоненты базисного решения. Составляем новую линейную функцию Т = F-М( , ,…, ) где M -произвольно большое число, и ищем ее максимум (T-задача). Назовем М-функцией выражение М( , ,…, ). На практике находят не минимум М-функции, а максимум М-функции.
Возможны 2 случая:
1 minM-функция<0 значит исходная задача не имеет ни одного допустимого базиса.
2. minM-функция=0 исходная задача имеет допустимый базис и задача может быть решена обычным С.М,
Так как исходная задача сводиться к решению задача M-min и исходной, то метод искусственного базиса еще называется двухфазным симплекс-методом.
Пример
f= x1+x2+x3+x4 max
x1+x2+3x3+x4=4
x1-x2-x3+3x4=2
рассмотрим:
x1+x2+3x3+x4+у1=4
x1-x2-x3+3x4+у2=2
f-x1-x2-x3-x4=0
F=y1+y2=6-2x1-2x3-4x4
|
x1 |
x2 |
x3 |
x4 |
y1 |
y2 |
|
y1 |
1 |
1 |
3 |
1 |
1 |
0 |
4 |
y2 |
1 |
-1 |
-1 |
3 |
0 |
1 |
2 |
f |
-1 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
F |
2 |
0 |
2 |
4 |
0 |
0 |
6 |
y1 |
0 |
2 |
4 |
-2 |
1 |
-1 |
2 |
x1 |
1 |
-1 |
-1 |
3 |
0 |
1 |
2 |
f |
0 |
-2 |
-2 |
-2 |
0 |
1 |
2 |
F |
0 |
2 |
4 |
-2 |
0 |
-2 |
2 |
x2 |
0 |
1 |
2 |
-1 |
1 |
-1 |
1 |
x1 |
1 |
0 |
1 |
2 |
1 |
-1 |
3 |
f |
0 |
0 |
2 |
0 |
1 |
0 |
4 |
F |
0 |
0 |
0 |
0 |
-1 |
-1 |
0 |
minF=0 значит имеет доп.базис
x2 |
0 |
1 |
2 |
-1 |
1 |
x1 |
1 |
0 |
1 |
2 |
3 |
f |
0 |
0 |
2 |
0 |
4 |
x2+2x3-x4=0
x1+x3+2x4=3
f+2x3=4 f=4-2x3
f(max)=f(3,1,0,0)=4