Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.
Оскільки в правій частині присутні негативні значення, помножимо відповідні рядки на (-1).
Визначимо максимальне значення цільової функції F (X) = x 1 + x 2 при наступних умовах-обмежень.
- 3x 1 + 2x 2 ? 6
x 1 + 2x 2 ? 3
x 1 ? 3
x 2 ? 5
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної формі).
-3x 1 + 2 x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 6
1x 1 + 2x 2 + 0x 3-1x 4 + 0x 5 + 0x 6 = 3
1x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 3
0x 1 + 1x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 5
Введемо штучні змінні x: в 2-м рівність вводимо змінну x 7;
-3x 1 + 2x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 + 0x 7 = 6
1x 1 + 2x 2 + 0x 3-1x 4 + 0x 5 + 0x 6 + 1x 7 = 3
1x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 + 0x 7 = 3
0x 1 + 1x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 + 0x 7 = 5
Для постановки задачі на максимум цільову функцію запишемо так:
F (X) = x 1 + x 2 - Mx 7 > max
З рівнянь виражаємо штучні змінні:
x 7 = 3-x 1-2x 2 + x 4
які підставимо в цільову функцію:
F (X) = (1 +1 M) x 1 + (1 +2 M) x 2 + (-1M) x 4 + (-3M) > max
Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:
-3
2
1
0
0
0
0

1
2
0
-1
0
0
1

1
0
0
0
1
0
0

0
1
0
0
0
1
0

 
Вирішимо систему рівнянь щодо базисних змінних:
x 3, x 7, x 5, x 6,
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,6,0,3,5,3)
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7

x 3
6
-3
2
1
0
0
0
0

x 7
3
1
2
0
-1
0
0
1

x 5
3
1
0
0
0
1
0
0

x 6
5
0
1
0
0
0
1
0

F (X0)
-3M
-1-1M
-1-2M
0
1M
0
0
0

 
Переходимо до основного алгоритму симплекс-метода.
Ітерація № 0.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 2, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: b i / a i2
і з них виберемо найменше:
Отже, 2-ий рядок є провідною.
Дозволяє елемент дорівнює (2) і стоїть на перетині провідного стовпця і ведучою рядка.
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
min

x 3
6
-3
2
1
0
0
0
0
3

x 7
3
1
2
0
-1
0
0
1
1 1/2

x 5
3
1
0
0
0
1
0
0
-

x 6
5
0
1
0
0
0
1
0
5

F (X1)
-3M
-1-1M
-1-2M
0
1M
0
0
0
0

 
 
Отримуємо нову симплекс-таблицю:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7

x 3
3
-4
0
1
1
0
0
-1

x 2
1 1/2
1/2
1
0
-1 / 2
0
0
1/2

x 5
3
1
0
0
0
1
0
0

x 6
3 1/2
-1 / 2
0
0
1/2
0
1
-1 / 2

F (X1)
1 1/2
-1 / 2
0
0
-1 / 2
0
0
1/2 +1 M

 
Ітерація № 1.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 4, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: b i / a i4
і з них виберемо найменше:
Отже, 1-а рядок є провідною.
Дозволяє елемент дорівнює (1) і стоїть на перетині провідного стовпця і ведучою рядка.
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
min

x 3
3
-4
0
1
1
0
0
-1
3

x 2
1 1/2
1/2
1
0
-1 / 2
0
0
1/2
-

x 5
3
1
0
0
0
1
0
0
-

x 6
3 1/2
-1 / 2
0
0
1/2
0
1
-1 / 2
7

F (X2)
1 1/2
-1 / 2
0
0
-1 / 2
0
0
1/2 +1 M
0

 
 
Отримуємо нову симплекс-таблицю:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7

x 4
3
-4
0
1
1
0
0
-1

x 2
3
-1 1/2
1
1/2
0
0
0
0

x 5
3
1
0
0
0
1
0
0

x 6
2
1 1/2
0
-1 / 2
0
0
1
0

F (X2)
3
-2 1/2
0
1/2
0
0
0
1M

 
Ітерація № 2.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 1, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: b i / a i1
і з них виберемо найменше:
Отже, 4-й рядок є провідною.
Дозволяє елемент дорівнює (1 1/2) і стоїть на перетині провідного стовпця і ведучою рядка.
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
min

x 4
3
-4
0
1
1
0
0
-1
-

x 2
3
-1 1/2
1
1/2
0
0
0
0
-

x 5
3
1
0
0
0
1
0
0
3

x 6
2
1 1/2
0
-1 / 2
0
0
1
0
1 1/3

F (X3)
3
-2 1/2
0
1/2
0
0
0
1M
0

 
 
Отримуємо нову симплекс-таблицю:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7

x 4
8 1/3
0
0
-1 / 3
1
0
2 2/3
-1

x 2
5
0
1
0
0
0
1
0

x 5
1 2/3
0
0
1/3
0
1
-2 / 3
0

x 1
1 1/3
1
0
-1 / 3
0
0
2/3
0

F (X3)
6 1/3
0
0
-1 / 3
0
0
1 2/3
1M

 
Ітерація № 3.
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідний змінної x 3, так як це найбільший коефіцієнт за модулем.
Обчислимо значення D i по рядках як частка від ділення: b i / a i3
і з них виберемо найменше:
Отже, 3-а рядок є провідною.
Дозволяє елемент дорівнює (1/3) і стоїть на перетині провідного стовпця і ведучою рядка.
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7
min

x 4
8 1/3
0
0
-1 / 3
1
0
2 2/3
-1
-

x 2
5
0
1
0
0
0
1
0
-

x 5
1 2/3
0
0
1/3
0
1
-2 / 3
0
5

x 1
1 1/3
1
0
-1 / 3
0
0
2/3
0
-

F (X4)
6 1/3
0
0
-1 / 3
0
0
1 2/3
1M
0

 
 
Отримуємо нову симплекс-таблицю:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7

x 4
10
0
0
0
1
1
2
-1

x 2
5
0
1
0
0
0
1
0

x 3
5
0
0
1
0
3
-2
0

x 1
3
1
0
0
0
1
0
0

F (X4)
8
0
0
0
0
1
1
1M

 
Кінець ітерацій: індексна рядок не містить негативних елементів - знайдений оптимальний план
Остаточний варіант симплекс-таблиці:
Базис
B
x 1
x 2
x 3
x 4
x 5
x 6
x 7

x 4
10
0
0
0
1
1
2
-1

x 2
5
0
1
0
0
0
1
0

x 3
5
0
0
1
0
3
-2
0

x 1
3
1
0
0
0
1
0
0

F (X5)
8
0
0
0
0
1
1
1M

 
Оптимальний план можна записати так:
x 4 = 10
x 2 = 5
x 3 = 5
x 1 = 3
F (X) = 1 5 + 1 3 = 8