Решение задач линейного программирования. Решение целочисленной задачи методом Гомори

Типовой расчет

Задание 1. Решить задачу линейного программирования:  a) графически, b) симплекс-методом.

1. f(x) = 2x1 + 4x2 ® max	2. f(x) = x1 + x2 ® max	3. f(x) = 3x1 + 2x2 ® max
4. f(x) = 2x1 + 5x2 ® max	5. f(x) = 4x1 + 5x2 ® max	6. f(x) = 2x1 - 3x2 ® max
7. f(x) = x1 - x2 ® max	8. f(x) = 6x1 + 5x2 ® max	9. f(x) = 2x1 + 4x2 ® max
10. f(x) = 5x1 + 4x2 ® max	11. f(x) = 2x1 + x2 ® max	12. f(x) = x1 + 3x2 ® max
13. f(x) = 7x1 + 4x2 ® max	14. f(x) = 2x1 - x2 ® max	15. f(x) = 2x1 - x2 ® max
16. f(x) = 3x1 + 4x2 ® max	17. f(x) = x1 - x2 ® max	18. f(x) = 5x1 + 6x2 ® max
19. f(x) = 3x1 - x2 ® max	20. f(x) = x1 + x2 ® max	21. f(x) = 4x1 + x2 ® max
22. f(x) = 2x1 - x2 ® max	23. f(x) = 2x1 +3x2 ® max	24. f(x) = x1 - x2 ® max
25. f(x) = 3x1 - 2x2 ® max	26. f(x) = 5x1 + 3x2 ® max	27. f(x) = 2x1 + 7x2 ® max
28. f(x) = 3x1 + 5x2 ® max	29. f(x) = 4x1 + 3x2 ® max	30. f(x) = 2x1 + 6x2 ® max

Задание 2. Решить задачу линейного программирования  симплекс-методом.

1. f(x) = x1 + x2 + x3 - x4 - 2x5  - 7 ® min	2. f(x) =21 x1 + 2x2 + 30x3  + x5   ® min
3. f(x) = 2x1 + x2 + x3 - x4 - 2x5  + 12 ® min	4. f(x) =2 x1 + 2x2 + 3x3  + x5   ® min
5. f(x) = 2x1 + 4x2 + x3 - x4 - 5x5  + 15® min	6. f(x) = x1 + 2x2 + 2x3  + x5   ® min
7. f(x) = x1 + 4x2 + 2x3 + 4x4 - 5x5  ® min	8. f(x) = 5x1 + 2x2 + 5x3  + x5   ® min
9. f(x) = 10x1 + 4x2 + 2x3 + 4x4 - 5x5   ® min	10. f(x) = 4x1 + 2x2 + 3x3  + 2x5   ® min
11. f(x) = x1 + 4x2 + 2x3 - 2x4 - x5  - 10 ® min	12. f(x) = 3x1 + 2x2 + 8x3  + x5   ® min
13. f(x) = x1 + 4x2 + 2x3 + 2x4 + x5  + 2 ® min	14. f(x) = 4x1 + 2x2 + 3x3  + 5x5   ® min
15. f(x) = x1 + 7x2 + 2x3 + x4 + 4x5  - 5 ® min	16. f(x) = 7x1 + 2x2 - 3x3  + 5x5   ® min
17. f(x) = x1 + 2x2 + 2x3 + 9x4 + 4x5   ® min	18. f(x) = x1 + 2x2 - 3x3  + x5   ® min
19. f(x) = 5x1 + 7x2 + 9x3 + x4 + x5  + 1 ® min	20. f(x) = 2x1 + 2x2 - 2x3  + x5   ® min
21. f(x) = 3x1 + 2x2 + x3 + x4 + x5  + 4 ® min	22. f(x) = 8x1 + 2x2 - 2x3  + 5x5   ® min
23. f(x) = 4x1 + 2x2 + 3x3 + x4 + x5  + 1 ® min	24. f(x) = 4x1 + 2x2 - 2x3  + 3x5   ® min
25. f(x) = 9x1 + 2x2 + 3x3 + 2x4 + x5  ® min	26. f(x) = - x1 + 2x2 - 2x3  + 3x5   ® min
27. f(x) = 2x1 + 2x2 + 3x3 + 5x4 + x5  ® min	28. f(x) = - 4x1 + 2x2 - 2x3  + 7x5   ® min
29. f(x) = 21x1 + 2x2 + 30x3 + 5x4 + x5  ® min	30. f(x) = - 5x1 + 7x2 - 5x3  + 8x5   ® min

Задание 3. Решить задачу линейного программирования симплекс-методом, составить двойственную задачу и найти ее решение.

1. f(x) = 5x1 + 3x2 + 2x3  ® mах	2. f(x) = 4x1 + 5x2 + 4x3  ® mах
3. f(x) = 6x1 + 4x2 + x3 ® mах	4. f(x) = 6x1 - 5x2 + 4x3  ® mах
5 f(x) = 2x1 + 4x2 - x3 ® mах	6. f(x) = 3x1 - 5x2 + 4x3  ® mах
7. f(x) = 5x1 + 4x2 - 2x3 ® mах	8. f(x) = 5x1 - 5x2 + 6x3  ® mах
9. f(x) = x1 - 2x2 + 2x3 ® mах	10. f(x) = 9x1 - 5x2 + 8x3  ® mах
11. f(x) = 5x1 - 5x2 + 6x3 ® mах	12. f(x) = x1 - 5x2 + x3  ® mах
13. f(x) = -5x1 + 7x2 + 6x3 ® mах	14. f(x) = x2 + x3  ® mах
15. f(x) = -3x1 + 5x2 + 6x3 ® mах	16. f(x) = 10x1 - 3x2 + 2x3  ® mах
17. f(x) = - x1 + x2 + 2x3 ® mах	18. f(x) = x1 - 3x2 + 2x3  ® mах
19. f(x) = - x1 + 3x2 + 2x3 ® mах	20. f(x) = 7x1 - 3x2 + 8x3  ® mах
21. f(x) = - 7x1 + 8x2 + 7x3 ® mах	22. f(x) = 4x1 - x2 + 4x3  ® mах
23. f(x) = - 9x1 + 5x2 + 4x3 ® mах	24. f(x) = 2x1 - x2 + 5x3  ® mах
25. f(x) = - 4x1 + 8x2 + 7x3 ® mах	26. f(x) = 2x1 - 5x2 + 3x3  ® mах
27.  f(x) = 4x1 + 5x2 + 7x3 ® mах	28. f(x) = 2x1 + 8x2 + 3x3  ® mах
29. f(x) = 5x1 + 5x2 + 6x3 ® mах	30. f(x) = 5x1 + 4x2 + 3x3  ® mах

Задание 4. Решить целочисленную задачу методом Гомори.

1. f(x) = 3x1 + 4x2 ® max	2. f(x) = 7x1 + x2 ® max	3. f(x) = 3x1 + 2x2 ® max
4. f(x) = 2x1 + 15x2 ® max	5. f(x) = 4x1 + 5x2 ® max	6. f(x) = 2x1 - 3x2 ® max
7. f(x) = 9x1 + 7x2 ® max	8. f(x) = 7x1 + 10x2 ® max	9. f(x) = x1 + 3x2 ® max
10. f(x) = 5x1 + 4x2 ® max	11. f(x) = x1 + 2x2 ® max	12. f(x) = 2x1 - x2 ® max
13. f(x) = 3x1 + 2x2 ® max	14. f(x) = x1 - x2 ® max	15. f(x) = 7x1 + 6x2 ® max
16. f(x) = 3x1 - x2 ® max	17. f(x) = 2x1 + x2 ® max	18. f(x) = 4x1 + x2 ® max
19. f(x) = 4x1 - x2 ® max	20. f(x) = 2x1 +9x2 ® max	21. f(x) = x1 - x2 ® max
22. f(x) = 3x1 - 2x2 ® max	23. f(x) = 5x1 + 3x2 ® max	24. f(x) = 11x1 + 7x2 ® max
25. f(x) = 3x1 + 5x2 ® max	26. f(x) = 4x1 + 3x2 ® max	27. f(x) = 2x1 + 6x2 ® max
28. f(x) = 9x1 + 5x2 ® max	29. f(x) = 9x1 + 5x2 ® max	30. f(x) = 5x1 + 4x2 ® max

Задание 5. Решить транспортную задачу.

		В 1							В 2
	B1	B2	B3	B4				B1	B2	B3	B4
A1	1	8	2	10	190		A1	2	2	5	1	140
A2	20	21	7	8	120		A2	1	8	11	1	190
A3	7	11	5	9	240		A3	9	8	7	2	230
	210	120	170	50				120	210	190	40
		В 3							В 4
	B1	B2	B3	B4				B1	B2	B3	B4
A1	3	3	3	2	200		A1	4	3	2	5	250
A2	1	7	5	11	180		A2	22	2	5	8	130
A3	4	3	9	3	190		A3	10	16	22	3	230
	130	230	80	130				70	230	240	70
		В 5							В 6
	B1	B2	B3	B4				B1	B2	B3	B4
A1	5	1	1	2	25		A1	6	3	14	10	25
A2	7	2	4	3	13		A2	3	15	4	5	13
A3	4	7	2	4	23		A3	8	11	5	2	25
	7	23	24	7				16	20	20	7
		В 7							В 8
	B1	B2	B3	B4				B1	B2	B3	B4
A1	7	12	5	9	50		A1	8	10	5	11	10
A2	4	2	9	21	30		A2	7	6	4	5	30
A3	12	3	4	7	35		A3	7	2	8	2	35
	15	25	25	50				5	30	20	20
		В 9							В 10
	B1	B2	B3	B4				B1	B2	B3	B4
A1	9	15	10	1	10		A1	10	8	12	18	20
A2	3	8	3	2	30		A2	23	1	4	25	20
A3	6	2	5	8	25		A3	25	18	4	6	25
	15	10	15	25				15	20	10	20
		В 11							В 12
	B1	B2	B3	B4				B1	B2	B3	B4
A1	11	9	4	4	30		A1	12	18	23	14	15
A2	5	7	10	5	10		A2	4	5	3	16	25
A3	3	5	4	6	65		A3	11	8	17	4	35
	30	10	5	60				25	20	15	15
		В 13							В 14
	B1	B2	B3	B4				B1	B2	B3	B4
A1	13	8	20	10	10		A1	14	10	25	10	45
A2	22	2	7	8	12		A2	12	8	11	15	95
A3	7	11	5	9	24		A3	9	8	7	12	23
	21	5	15	5				33	50	35	45
		В 15							В 16
	B1	B2	B3	B4				B1	B2	B3	B4
A1	15	11	3	22	20		A1	10	3	2	5	45
A2	10	10	5	11	80		A2	2	2	5	8	100
A3	14	22	11	22	90		A3	10	6	2	3	55
	35	20	85	50				45	60	50	45
		В 17							В 18
	B1	B2	B3	B4				B1	B2	B3	B4
A1	17	15	10	11	10		A1	18	8	12	18	20
A2	9	8	14	12	30		A2	9	16	4	5	20
A3	6	12	15	8	25		A3	25	18	14	6	25
	15	10	15	25				15	20	10	20
		В 19							В 20
	B1	B2	B3	B4				B1	B2	B3	B4
A1	19	9	6	7	30		A1	20	18	23	14	25
A2	5	7	10	9	20		A2	14	5	12	16	25
A3	8	5	8	6	65		A3	11	8	17	14	35
	30	10	15	60				25	20	25	15
		В 21							В 22
	B1	B2	B3	B4				B1	B2	B3	B4
A1	21	8	9	10	30		A1	22	10	15	10	45
A2	11	2	7	8	12		A2	12	8	11	15	95
A3	7	12	5	9	24		A3	9	8	17	12	50
	21	15	15	15				40	60	35	55
		В 23							В 24
	B1	B2	B3	B4				B1	B2	B3	B4
A1	23	11	14	22	50		A1	24	3	12	5	40
A2	10	10	15	11	80		A2	2	12	5	8	100
A3	14	22	11	12	90		A3	10	6	2	3	60
	35	50	85	50				40	60	50	50
		В 25							В 26
	B1	B2	B3	B4				B1	B2	B3	B4
A1	25	15	10	1	30		A1	26	8	12	18	40
A2	3	8	3	2	30		A2	23	12	4	25	20
A3	6	2	5	8	25		A3	25	18	4	6	25
	15	20	25	25				25	20	20	20
		В 27							В 28
	B1	B2	B3	B4				B1	B2	B3	B4
A1	27	9	4	4	30		A1	28	8	23	4	45
A2	5	7	10	5	30		A2	4	5	3	6	25
A3	3	5	4	6	65		A3	11	8	7	4	35
	30	10	25	60				25	20	25	35
		В 29							В 30
	B1	B2	B3	B4				B1	B2	B3	B4
A1	29	8	10	10	30		A1	30	10	5	10	45
A2	12	2	7	8	42		A2	12	8	11	5	85
A3	7	11	5	9	24		A3	9	8	7	12	23
	21	25	15	35				33	40	35	45

Задание 6. Дана платежная матрица игры. Найти седловые точки и оптимальные стратегии игроков.

1.	9	8	10	10	2.	2	8	10	10
	12	2	7	8		1	2	7	8
	7	7	5	9		0	1	5	9
3.	12	8	8	10	4.	9	8	10	5
	12	2	7	8		12	2	7	4
	7	11	5	9		7	11	5	0
5.	4	6	0	3	6.	9	8	1	6
	1	7	7	8		2	2	7	5
	7	7	8	9		7	11	8	6
7.	6	8	5	10	8.	19	18	10	10
	12	7	7	8		12	2	7	8
	7	11	5	9		7	11	5	9
9.	5	7	1	1	10.	20	8	6	8
	12	7	7	8		12	2	3	8
	7	1	5	9		7	11	5	9
11.	6	8	4	9	12.	21	8	9	5
	12	2	3	8		12	2	7	5
	7	11	3	9		7	7	5	4
13.	7	8	9	10	14.	22	18	17	10
	7	9	7	8		12	2	27	8
	7	11	5	9		17	11	5	9
15.	8	8	10	10	16.	23	18	10	10
	12	8	7	8		12	12	1	18
	7	6	5	9		7	11	5	9
17.	9	8	6	5	18.	24	8	3	2
	2	2	7	4		12	2	3	8
	7	1	5	0		12	14	3	3
19.	10	10	10	10	20.	25	28	100	10
	12	10	17	18		12	2	10	8
	17	11	15	19		70	10	5	9
21.	11	8	11	11	22.	26	18	16	9
	12	2	7	8		12	2	7	8
	17	11	15	11		10	11	12	9
23.	12	18	18	12	24.	27	12	14	10
	12	2	7	8		12	12	17	18
	7	11	12	9		7	11	5	12
25.	13	8	5	4	26.	28	7	4	5
	4	2	3	2		12	2	4	8
	7	4	5	3		7	11	5	9
27.	14	10	10	12	28.	29	28	20	20
	12	2	1	8		12	20	7	8
	7	11	5	10		20	11	5	9
29.	15	7	1	1	30.	30	15	5	40
	12	6	6	8		12	9	7	8
	17	1	5	6		10	11	9	9

Задание 7. Дана платежная матрица игры. Решить графически игру.

1.	2.	3.
4.	5.	6.
7.	8.	9.
10.	11.	12.
13.	14.	15.
16.	17.	18.
19.	20.	21.
22.	23.	24.
25.	26.	27.
28.	29.	30.

Задание 8. Дана платежная матрица игры. Найти решение  игры путем сведения ее к задаче линейного программирования.

1.	2.	3.
4.	5.	6.
7.	8.	9.
10.	11.	12.
13.	14.	15.
16.	17.	18.
19.	20.	21.
22.	23.	24.
25.	26.	27.
27.	29.	30.

Примеры решения  заданий

Задачи линейного программирования

Пример 1. Решить ЗЛП                  f(x) = 3x₁ + 2x₂ ® max

x₁ + x₂ £ 4,

 2x₁ + x₂ £ 6,

   x₁ ³ 0, x₂ ³ 0,

a) графически,  b) симплекс-методом.

a) Шаг 1. Строится множество D допустимых решений  задачи, оно представляет собой  четырехугольник ОABC на плоскости x₁О x₂ с вершинами в точках О, А, В, С,  с координатами (0; 0), (0; 4), (2; 2), (3; 0), соответственно.

Шаг 2. Из начала координат откладывается вектор-градиент функции f(x), указывающий направления ее возрастания.

Шаг 3. Строится прямая 3x1 + 2x2  = const  – линия уровня функции f(x), перпендикулярная вектору градиента . Шаг 4. Линия уровня 3x1 + 2x2  = const  передвигается в направлении вектора до тех пор, пока она не покинет область D. Крайняя точка области, в которой линия уровня покидает допустимую область, и является решением задачи. В данном случае – это точка В(2; 2).

Шаг 5.Находится оптимальное значение функции.

f ^*(2; 2) =3x₁ + 2x₂ = 3 × 2 + 2 × 2 = 10.

b) Шаг 1. Задача приводится к специальному виду, для этого к левым частям неравенств прибавляются дополнительные переменные x₃ и x₄, превращающие неравенства в равенства.

         f(x) =3x₁ + 2x₂ ® max

x₁ + x₂ + x₃ = 4,

2x₁+ x₂ + x₄ = 6,

    x_j ³ 0,

Переменные x₃ и x₄ входят в первое и второе уравнения соответственно с коэффициентами единица, тогда х₃ , х₄  – начальный базис,  x₁ , x₂  – свободные переменные, b  – вектор ограничений.

   Шаг 2. Составляется соответствующая симплекс - таблица:

Так как свободные переменные всегда равны нулю, то для данного начального базиса f(x) будет равна нулю:

f(x) = с₀ - åc_i х_i = 0 × 2 + 0 × 6 = 0.

Так как имеются с_j < 0, приступаем к улучшению плана.

   Шаг 3. Выбирается разрешающий j-й столбец, соответствующий наименьшему отрицательному с_j.

         Шаг 4. Разрешающую строку определяют следующим образом: рассчитываются так называемые симплексные отношения, т. е. отношения текущих значений базисных переменных к положительным  коэффициентам разрешающего столбца, соответствующим данным базисным переменным. Затем берется минимальное из этих отношений и по тому, какой строке оно соответствует, определяется ведущая строка.

         Шаг 5.  Находится разрешающий элемент, он расположен на пересечении разрешающей строки и разрешающего столбца (в нашем случае он равен 2).

         Шаг 6.  Определяются переменные, которые будут исключены из базиса и включены в него. Переменную, которой соответствует разрешающий столбец, включаются в базис вместо переменной, которой соответствует разрешающая строка.  В базис вводим переменную x₁, которому соответствует минимальное значение c_j. Из базиса выводится x₄, так как минимальное q достигается в этой строке формулой  .

 Таким образом, элемент a₄₁ будет разрешающим (в таблице выделен серым цветом).

Шаг 7. Заполняем таблицу, соответствующую новому базисному решению.

 Шаг 8.  Так как в строке f(x) оценок полученного нового плана имеется отрицательное значение с_j , приступаем к следующей итерации, продолжая улучшать план.

  Поскольку все с_j ³ 0, то план, представленный в данной таблице, будет оптимальным.

Ответ:  f ^*(x) =10; x₁^* = 0; x₂^*= 6

Пример 2.  Решить каноническую задачу линейного программирования:

         f(Х) = х₁ - 2х₂ - 2x₃ ® max

                                                      x₁ + 4x₂ + x₃ = 5,

                                                      x₁ - 2x₂ - x₃ = -1,          

                                                       x_j ³ 0,

Данная каноническая задача линейного программирования (КЗЛП) не является специальной (СЗЛП), поэтому применяем метод искусственного базиса.  Строим вспомогательную задачу линейного программирования и приводим ее к специальному виду,  выражая целевую функцию через небазисные переменныеx_j ,  j=1,…,3. Эта задача имеет вид:

h(Х) = – ( t₁+ t₂) =  – 6 + 6 x₂ + 2 x₃ ® max

                                x₁ + 4x₂ + x₃ + t₁ = 5,

 x₁ - 2x₂ - x₃ + t₂ = -1,

                                                       все  x_j  ≥ 0, t_i  ≥ 0.

Решаем специальную задачу линейного программирования симплекс-методом:

б\с	x1	x2	x3	b		б\с	x1	x2	t2	b		б\с	t1	x2	t2	b
t1	1	4	1	5		t1	2	2	-1	4	¬	x1	0.5	1	-0,5	2
t2	-1	2	1	1	¬	x3	-1	2	1	1		x3	0,5	3	0,5	3
h	0	-6	-2	-6		h	-2	-2	2	-4		h	1	0	1	0
			­				­
f	-1	2	2	0		f	1	-2	2	-2		f	-0,5	-3	5/2	-4

Так как max h = 0, то множество Х допустимых решений КЗЛП не пусто, т. е.

Х ¹ Æ, поэтому существует СЗЛП, эквивалентная данной КЗЛП. Эта задача имеет вид:f(Х) = - 4 + 3х₂ ® max            

 x₁ + x₂  = 2,

 3x₂ + x₃ = 3,

                                                         все  x_j  ≥ 0.

Линейные уравнения этой системы и f(Х)  получены из завершающей симплекс-таблицы вспомогательной задачи.

Решаем специальную задачу линейного программирования симплекс-методом:

Отсюда оптимальный план Х^*(1; 1; 0), f_max = -1.

Пример 3. Решить задачу линейного программирования симплекс-методом, составить двойственную задачу и найти ее решение.

            Z = 6x₁ + 5 x₂ + 4x₃ + 3x₄ ® max

2x₁+ 3x₂ + 2x₃ + x₄ £ 25,

4x₁ + x₂ + 3x₃ + 2x₄ £ 30,

  3x₁ +5 x₂ + 2x₃ + 2x₄ £ 42,

                                                    все  x_j  ≥ 0.

Математическая модель прямой задачи Z = 6x1 + 5x2 + 4x3 + 3x4 ® max 2x1 + 3x2 + 2x3 + x4 £ 25, 4x1 + x2 + 3x3 +2x4 £ 30, 3x1 + 5x2 + 2x3 + 2x4 £ 42, x1≥ 0, x2≥ 0, x3≥ 0, x4≥ 0.

Математическая модель двойственной задачи f = 25y1+ 30y2 + 42y3 ® min y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, 2y1 + 4y2 + 3y3  ≥ 6, 3y1 + y2 + 5y3  ≥ 5, 2y1 + 3y2 + 2y3  ≥ 4, y1 + 2y2 + 2y3 ≥ 3.

Специальный вид Z= 6x1+5x2+4x3+3x4 ® max          2x1+3x2+2x3+x4+S1=25, 4x1+x2+3x3+2x4+S2=30,  3x1+5x2+2x3+2x4+S3=42,    x1, x2, x3, x4, S1, S2, S3 ≥ 0							S2		x2		x3		x4		b
					S1		-0,5		2,5		0,5		0		10		4
					x1		0,25		0,25		0,75		0,5		7,5		30
					S3		-0,75		4,25		-0,25		0,5		19,5		4,58
					Z		1,5		-3,5		0,5		0		45
									­
		x1	x2	x3		x4		b								S2		x2		x3	x4	b
	S1	2	3	2		1		25		12,5				x2								4
	S2	4	1	3		2		30		7,5				x1								6,5
	S3	3	5	2		2		42		14				S3								2,5
	Z	-6	-5	-4		-3		0						Z		0,8		1,4		1,2	0	59
		­

Х*(6.5, 4, 0, 0),    Z*=59.

Решение двойственной  задачи можно найти с помощью второй теоремы двойственности:

 (2x₁+ 3x₂ + 2x₃ + x₄ - 25) у₁ = 0 Þ(2 • 6,5 + 3 • 4 - 25) у₁ = 0 Þ 0 = 0,

(4x₁+ x₂ + 3x₃ + 2x₄ - 30) у₂ = 0 Þ (4 • 6,5 + 4 - 30) у₂ = 0 Þ 0 = 0,

(3x₁ + 5x₂ + 2x₃ + 2x₄ – 42) у₃ = 0 Þ (3 • 6,5 + 5 • 4 - 42) у₃ = 0Þ

Þ -2,5у₃ = 0 Þ у₃ = 0,

(2y₁ + 4y₂ + 3y₃ – 6) х₁ = 0 Þ (2y₁ + 4y₂ + 3y₃ –6) 6,5 = 0 Þ (2y₁ + 4y₂ +3y₃ – 6 = 0),

(3y₁ + y₂ + 5y₃ – 5) х₂ = 0 Þ (3y₁ + y₂ + 5y₃ – 5) 4 = 0 Þ (3y₁ + y₂ + 5y₃ – 5 = 0),

(2y₁ + 3y₂ + 2y₃ – 4) х₃ = 0 Þ (2y₁ + 3y₂ + 2y₃ – 4) 0 = 0 Þ 0 = 0,

(y₁ + 2y₂ + 2y₃ – 3) х₄ = 0 Þ 0 = 0.

Решая систему  у₃ = 0;  2y₁ + 4y₂ + 3y₃ – 6 = 0; 3y₁ + y₂ + 5y₃ – 5 = 0,

находим у₁ = 1,4;  у₂ = 0,8;  у₃ = 0;    f * = 25 • 1,4 + 30 • 0,8 + 42 • 0 = 59.

Пример 4. Решить целочисленную задачу линейного программирования методом Гомори.                                      f(Х) =2х₁+х₂® max            

                                 2x₁ + x₃  =3,

                                                     2х₁+ 3x₂ +x₄ =6,          

                                                      все  x_j  ≥ 0.

Сначала находится решение задачи симплекс-методом.

Х^*_нц (3/2; 1; 0; 0).

Переменная х₁ – дробная. Строим по строке х₁ отсечение:

{1/2} x₃ + {0} x₄ ≥ {3/2}, т. е. x₃  ≥ 1.

Здесь дробная часть числа а находится по формуле {а} = а – [a], где [a] – целая часть числа а.       

{1/2} = 1/2 - 0, {0} = 0, {3/2} = 3/2 – 1 = 1/2.

Из последней таблицы

                     f(Х) =4 - 2/3 х₃ - 1/3 х₄  ® max

                                  1/2 x₃ + x₁  = 3/2,

                                                      -1/3 х₃ + 1/3 x₄ + x₂ =1,         

                                                       все  x_j  ≥ 0.

Составляем задачу с дополнительным ограничением:

      f(Х) =4 - 2/3 х₃ - 1/3 х₄ ® max

                          1/2 x₃ + x₁  = 3/2,

                                              -1/3 х₃ + 1/3 x₄ + x₂ = 1,         

                                               х₃ - х₅ = 1,

                                               все  x_j  ≥ 0.

Полученную задачу решаем М-методом:

F(X) = 4 - 2/3 х₃ - 1/3 х₄ – M t₁ = 4 - 2/3 х₃ - 1/3 х₄ + M (-1 + x₃ - x₅) ® max

                          1/2 x₃ + x₁  = 3/2,

                                              -1/3 х₃ + 1/3 x₄ + x₂ = 1,         

                                               х₃ - х₅ + t₁ = 1,

                                               t₁ ≥ 0, все  x_j  ≥ 0.

б\с	x3	x4	x5	b		б\с	t1	x4	x5	b
x1	1/2	0	0	3/2		x1	-1/2	0	1/2	1
x2	-1/3	1/3	0	1		x2	1/3	1/3	-1/3	4/3
t1	1	0	-1	1	¬	x3	1	0	-1	1
f	2/3	1/3	0	4		f	-2/3	1/3	2/3	10/3
M	-1	0	1	-1		M	1	0	0	0
	­

х₂ = 4/3, требуется еще итерация. Из последней симплекс-таблицы

        f(Х) =10/3 - 1/3 х₄ - 2/3 x₅ ® max

                                                 х₁ + 1/2 х₅ = 1,

 х₂ + 1/3 х₄  - 1/3 х₅ = 4/3,

                                                 - х₅ + х₃ = 1,

                                                {1/3} х₄ + {-1/3} х₅  ≥ {4/3},

                                                 все  x_j  ≥ 0.

{-1/3} = - 1/3 – (-1) = 2/3, {4/3} = 4/3 – 1 = 1/3.

Получаем каноническую задачу линейного программирования :

        f(Х) =10/3 - 1/3 х₄ - 2/3 x₅ ® max

                                                 х₁ + 1/2 х₅ = 1,

 х₂ + 1/3 х₄  - 1/3 х₅ = 4/3,

                                                 - х₅ + х₃ = 1,

                                                 х₄ + 2х₅ - х₆ = 1,

                                                 все  x_j  ≥ 0.

Применяем М-метод.

                                F(Х) =10/3 -1/3 х₄ - 2/3 x₅ – M (1 - (х₄ + 2х₅  - х₆)) ® max

х₁ + 1/2 х₅ = 1;    х₂ + 1/3 х₄  - 1/3 х₅ = 4/3;  - х₅ + х₃ = 1;    х₄ + 2х₅ - х₆ + t = 1;

                                                 t ≥ 0, все  x_j  ≥ 0.

б\с	x4	x5	x6	b		б\с	t	x5	x6	b
x1	0	½	0	1		x1				1
x2	1/3	-1/3	0	4/3		x2				1
х3	0	-1	0	1		х3				1
t	1	2	-1	1	¬	x4				1
f	1/3	2/3	0	10/3		f		0	1/3	3
M	-1	-2	1	-1		M		0	0	0
	­

Оптимальное целочисленное решение Х^*_ц (1,1,1,1).

Пример 5. Решить транспортную задачу.

Поставщики	Потребители				Запасы
	В1	В2	В3	В4
А1	2	3	2	4	30
А2	3	2	5	1	40
А3	4	3	2	6	20
Потребности	20	30	30	10	90

Шаг 1. (Нахождение опорного плана перевозок методом минимального элемента.)  В  матрице стоимостей  перевозок находится наименьший элемент, это    Находится  количество единиц перевозимого груза