Розв’язання задач лінійного програмування

9.2.1. Графічним методом знайти розв’язок таких задач:

а) x₁ + x₂ → max б) 2x₁ + x₂ → max

3x₁ – 2x₂ ≤ 6, -x₁ + x₂ ≤ 2,

-x₁ + 2x₂ ≤ 4, x₁ + 2x₂ ≤ 7,

3x₁ + 2x₂ ≤ 12; 4x₁ – 3x₂ ≤ 6;

x₁ ≥ 0; x₁, x₂ ≥ 0;

Відповіді: а) x* = (2,3); б) х* = (3,2); в) x* = (1,2); г) x* = (1,-2).

9.2.2. Звести нижченаведені задачі до канонічної форми з діагональною матрицею обмежень.

а) 8x₁ – 2x₂ – x₃ → max, б) x₁ + x₃ – 7x₄ + x₅ → max

x₁ + 3x₂ + x₃ ≤ 4, x₁ – x₂ + 6x₄ – 2x₅ = -7,

7x₁ - x₃ ≤ 16, x₂ – x₃ – 4x₄ + 6x₅ = 24,

2x₁ – x₂ – x₃ = 2, x₁ + x₂ – x₃ – 4x₄ + 7x₅ =32,

x_j ≥ 0, j = 1,2,3 x_j ≥ 0, j = 1,…,5

9.2.3. Розв’язати симплекс-методом наведені нижче задачі. В усіх задачах змінні є невід’ємними.

1)	x1+ x2+ x3 min,	2)	2 x1+ x2 – x3– x4 min,
	x1 – x4 – 2 x6= 5,		x1+ x2+ 2 x3– x4= 2,
	x2 + 2 x4– 3 x5+ x6= 3,		2 x1+ x2– 3 x3+ x4= 6,
	x3+ 2 x4– 5 x5+ 6 x6= 5;		x1+ x2+ x3+ x4= 7;

3)	x1– 2x2+ 3x3 min,	4)	2x1– 3x2 max,	5)	6 x1+ 4 x2 min,
	2x1+ 3x2+ 4x3= 1,		5x1+ 2x2 10,		2 x1+ x2 3,
	–2x1+ x2+ 3x3= 2;		x1+ 3x2 12;		x1– x2 1;
6)	2 x1– 4 x2 min,	7)	7 x1+ 5 x2 max,	8)	3 x1+ 2 x2 max,
	8 x1– 5 x2 16,		7 x1+ 5 x2 7,		4 x1+ 2 x2 12,
	x1+ 3 x2 2,		7 x1– 5 x2 35,		x1+ 2 x2 10,
	2 x1+ 7 x2 9;		x1– x2 0;		2 x1+ 2 x2= 6;

9)	4 x1+ 5 x2+ 9 x3+ 11 x4 max,	10)	2 x1+ x2– x3– x4 min,
	x1+ x2+ x3+ x4 15,		x1+ x2+ 2 x3– x4= 2,
	7 x1+ 5 x2+ 3 x3+ 2 x4 80,		2 x1+ x2– 3 x3+ x4= 6,
	3 x1+ 5 x2+ 10 x3+ 15 x4 60;		x1+ x2+ x3+ x4= 7;

11)	4x1+ x2– 2x3– x4– x5 min,	12)	x1+ 2 x2+ 3 x3– x4 max,
	x3– x4+ x5= 1,		x1+ 2 x2+ 3 x3 = 15,
	x2 + 2x4– x5= 1,		2 x1+ x2– 3 x3 = 20,
	x1+ 2x2 + 2x5= 4;		x1+ 2 x2 + x4= 10.

Відповіді:

1) x * = (7,1; 0; 0; 1,3; 0; 0,4), L (x*) = 7,1.

2) x * = (0; 4,13; 0,25; 2,63), L (x*) = 1,25.

3) Розв’язку немає (D = Æ).

4) x * = (12; 0), L (x*) = 24.

5) x * = (1,33; 0,33), L (x*) = 9,33.

6) x * = (0; 1,29), L (x*) = -5,14.

7) Розв’язку немає (цільова функція не обмежена зверху).

8) x * = (3; 0), L (x*) = 9.

9) x * = (4,56; 0; 2,95; 0), L (x*) = 67,21.

10) x * = (0; 4,13; 0,25; 2,63), L (x*) = 1,25.

11) x * = (0; 0; 0,5; 1,5; 2), L (x*) = -4,5.

12) Розв’язку немає (D = Æ).

9.2.4. Розв’язати двоїстим симплекс-методом задачі лінійного програмування, умови яких задаються нижче. В усіх задачах змінні невід’ємні.