6. Алгоритм симплекс-метода

Если номера базисных переменных, соответствующих оптимальному решению, известны, то для нахождения оптимального решения достаточно выразить указанные базисные переменные через свободные переменные. Если набор таких номеров не известен, то оптимальное решение находится последовательными переходами от одного допустимого базисного решения к другому допустимому базисному решению, в результате чего целевая функция каждый раз становится больше (в крайнем случае - не меньше),

Для решения задачи симплекс-методом необходима начальная симплексная таблица. Какие-то базисные переменные должны быть выражены через остальные свободные переменные, причем базисное решение должно быть допустимым, т. е. значения базисных переменных при нулевых значениях свободных переменных должны быть неотрицательны. Коэффициенты целевой функции в начальной таблице должны быть выраженные через свободные переменные,

Алгоритм симплекс-метода достаточно прост.

Шаг 1. Выбор новой базисной переменной. По положительным коэффициентам целевой функции в последней строке симплексной таблицы выбирается j-й столбец свободной переменной, подлежащей переводу в категорию базисных переменных.

Шаг 2. Выбор новой свободной переменной. Выполняются следующие вспомогательные вычисления: элементы правого крайнего столбца, содержащего значения базисных переменных, делятся на соответствующие (на расположенные в тех же строках) элементы j-го столбца, выбранного на шаге 1, Естественно, деление не выполняется, если элемент j-го столбца окажется равным нулю. Строки с нулевыми и отрицательными элементами j-того столбца не рассматриваются, Среди вычисленных положительных чисел выбирается наименьшее положительное число и указывается соответствующая этому числу -я строка. Найденная строка с номером - это строка базисной переменной, которой предстоит превратиться в свободную переменную.

Шаг 3. Переход к новой симплексной таблице. Очередная симплексная таблица получается изменением статуса двух переменных: свободная переменная, соответствующая j-му столбцу переводится в категорию базисных переменных, а базисная переменная, соответствующая -ой строке, становится свободной переменной. В новой таблице на пересечении j-того столбца и -той строки находится единица, остальные элементы нового j-того столбца содержат ноль. Если в последней строке полученной таблицы среди коэффициентов целевой функции не окажется положительных чисел, то оптимальное решение достигнуто, иначе следует перейти к шагу 1.

Переход к новой симплексной таблице по симплекс-методу будем называть итерацией. Одна итерация симплекс-метода в многомерном случае означает переход из соответствующей допустимому базисному решению вершины n-мерного многогранника ограничений на соседнюю вершину, причем, из множества возможных переходов выбирается такой, который приближает нас к цели, т. е. значение целевой функции при таком переходе возрастает, либо, в крайнем случае, остается неизменным.

7. Решение задачи об использовании сырья симплекс-методом.

1234

111100 - такой выбор переменных соответствует точке О(0,0)

X₁ X₂

1.000 .000 .000 .000 2.000 3.000 35.000

.000 1.000 .000 .000 2.000 1.000 21.000

.000 .000 1.000 .000 1.000 4.000 40.000

.000 .000 .000 1.000 5.000 1.000 45.000

.000 .000 .000 .000 7.000 5.000 .000

1246

110101 - такой выбор переменных соответствует точке A(0,10)

1.000 .000 -.750 .000 1.250 .000 5.000

.000 1.000 -.250 .000 1.750 .000 11.000

.000 .000 .250 .000 .250 1.000 10.000

.000 .000 -.250 1.000 4.750 .000 35.000

.000 .000 -1.250 .000 5.750 .000 -50.000

2456

010111 - такой выбор переменных соответствует точке B(4, 9)

.800 .000 -.600 .000 1.000 .000 4.000

-1.400 1.000 .800 .000 .000 .000 4.000

-.200 .000 .400 .000 .000 1.000 9.000

-3.800 .000 2.600 1.000 .000 .000 16.000

-4.600 .000 2.200 .000 .000 .000 -73.000

3456

001111 - такой выбор переменных соответствует точке C(7, 7)

-.250 .750 .000 .000 1.000 .000 7.000

-1.750 1.250 1.000 .000 .000 .000 5.000

.500 -.500 .000 .000 .000 1.000 7.000

.750 -3.250 .000 1.000 .000 .000 3.000

-.750 -2.750 .000 .000 .000 .000 -84.000

Предыдущие 4 таблицы представим в другом формате

1234

111100 - такой выбор переменных соответствует точке О(0,0)

X₁ X₂

1 0 0 0 2 3 35

0 1 0 0 2 1 21

0 0 1 0 1 4 40

0 0 0 1 5 1 45

0 0 0 0 7 5 0

1246

110101 - такой выбор переменных соответствует точке A(0,10)

1 0 -0,75 0 1,25 0 5

0 1 -0,25 0 1,75 0 11

0 0 0,25 0 0,25 1 10

0 0 -0,25 1 4,75 0 35

0 0 -1,25 0 5,75 0 -50

2456

010111 - такой выбор переменных соответствует точке B(4, 9)

0,8 0 -0,59 0 1 0 4

-1,4 1 0,8 0 0 0 4

-0,2 0 0,4 0 0 1 9

-3,8 0 2,6 1 0 0 16

-4,6 0 2,2 0 0 0 -73

3456

001111 - такой выбор переменных соответствует точке C(7, 7)

-0,25 0,75 0 0 1 0 7

-1,75 1,25 1 0 0 0 5

0,5 -0,5 0 0 0 1 7

0,75 -3,25 0 1 0 0 3

-0,75 -2,74 0 0 0 0 -84

Для достижения максимума потребовалось три итерации. Как видно из приведенных результатов, каждая итерация симплекс-метода соответствует переходу на соседнюю вершину многоугольника ограничений:

О(0, 0) A(0,10) B(4, 9) C(7, 7).

Каждая итерация увеличивает значение целевой функции :

0 50 73 84.

Отметим, что при решении задачи симплекс-методом и методом полного перебора базисных решений таблицы, соответствующие одной и той же вершине многоугольника ограничений, могут отличаться порядком следования строк.

Оптимальной вершины можно достигнуть другим путем

1234

111100 - такой выбор переменных соответствует точке О(0,0)

X₁ X₂

1.000 .000 .000 .000 2.000 3.000 35.000

.000 1.000 .000 .000 2.000 1.000 21.000

.000 .000 1.000 .000 1.000 4.000 40.000

.000 .000 .000 1.000 5.000 1.000 45.000

.000 .000 .000 .000 7.000 5.000 .000

1235

111010 - такой выбор переменных соответствует точке F(9,0)

1.000 .000 .000 -.400 .000 2.600 17.000

.000 1.000 .000 -.400 .000 .600 3.000

.000 .000 1.000 -.200 .000 3.800 31.000

.000 .000 .000 .200 1.000 .200 9.000

.000 .000 .000 -1.400 .000 3.600 -63.000

1356

101011 - такой выбор переменных соответствует точке E(8,5)

1.000 -4.333 .000 1.333 .000 .000 4.000

.000 1.667 .000 -.667 .000 1.000 5.000

.000 -6.333 1.000 2.333 .000 .000 12.000

.000 -.333 .000 .333 1.000 .000 8.000

.000 -6.000 .000 1.000 .000 .000 -81.000

3456

001111 - такой выбор переменных соответствует точке C(7, 7)

.750 -3.250 .000 1.000 .000 .000 3.000

.500 -.500 .000 .000 .000 1.000 7.000

-1.750 1.250 1.000 .000 .000 .000 5.000

-.250 .750 .000 .000 1.000 .000 7.000

-.750 -2.750 .000 .000 .000 .000 -84.000

Нетрудно заметить, что это достижение максимума следующим путем:

О(0, 0) F(9, 0) E(8, 5) C(7, 7).

Каждая итерация увеличивает значение целевой функции :

0 63 81 84.

Предыдущие 4 таблицы представим в другом формате

1234

111100 - такой выбор переменных соответствует точке О(0,0)

X₁ X₂

1 0 0 0 2 3 35

0 1 0 0 2 1 21

0 0 1 0 1 4 40

0 0 0 1 5 1 45

0 0 0 0 7 5 0

1235

111010 - такой выбор переменных соответствует точке F(9,0)

1 0 0 -0,4 0 2,6 17

0 1 0 -0,4 0 0,6 3

0 0 1 -0,2 0 3,8 31

0 0 0 0,2 1 0,2 9

0 0 0 -1,4 0 3,6 -63

1356

101011 - такой выбор переменных соответствует точке E(8,5)

1 -4,33 0 1,33 0 0 4

0 1,67 0 -0,66 0 1 5

0 -6,33 1 2,33 0 0 12

0 -0,33 0 0,33 1 0 8

0 -6 0 1 0 0 -81

3456

001111 - такой выбор переменных соответствует точке C(7, 7)

0,75 -3,25 0 1 0 0 3

0,5 -0,5 0 0 0 1 7

-1,74 1,25 1 0 0 0 5

-0,25 0,75 0 0 1 0 7

-0,75 -2,74 0 0 0 0 -84

ЗАДАНИЕ ДЛЯ САМОСТОЯТЕЛЬНОЙ работы.

1. Прочитать внимательно текст. С неясными вопросами обратиться к преподавателю.

2. Разобраться с графиком для первого способа перебора.

3. Найти максимальное значение целевой функции, перебрав все вершины многоугольника ограничений.

4. Указать для каждой точки на графике соответствующую ей симплексную таблицу.

5. Выписать для каждой таблицы значения свободных и базисных переменных. Дать экономическую интерпретацию этим значениям(хотя бы для 7-ми таблиц).

6. Указать, какие две переменные изменяют свой статус при переходе от одной таблицы к другой.

7. Найти максимальное значение целевой функции, перебирая симплексные таблицы с допустимыми базисными решениями (максимальное из чисел, взятых из правого нижнего угла с обратным знаком.).

Ниже выбрать свой вариант и решить задачу линейного программирования с помощью прилагаемой программы, разработанной студентом ЮЗГУ группы КС-81

Богомазовым Р. Ю.

Кроме задач линейного программирования (симплекс-метод и его модификации), эта программа позволяет решать все задачи линейной алгебры. Причем, задачу все-таки решает студент, а не компьютер, который всего лишь выполняет арифметические операции по командам студента.

Разработана программа, которая генерирует задачи. Оптимальное решение сгенерированных задач соответствует целочисленным значениям базисных переменных.

Ниже значок “<=” означает “ ”

BAPIANT 1

31.X1 + 29.X2 + 101.X3 <= 3700.

109.X1 + 191.X2 + 49.X3 <= 9092.

41.X1 + 44.X2 + 101.X3 <= 3658.

199.X1 + 101.X2 + 79.X3 <= 9032.

26.X1 + 32.X2 + 51.X3 --> MAX

BAPIANT 2

32.X1 + 28.X2 + 102.X3 <= 3800.

108.X1 + 192.X2 + 48.X3 <= 9132.

42.X1 + 43.X2 + 102.X3 <= 3768.

198.X1 + 102.X2 + 78.X3 <= 9102.

27.X1 + 31.X2 + 52.X3 --> MAX

BAPIANT 3

33.X1 + 27.X2 + 103.X3 <= 3900.

107.X1 + 193.X2 + 47.X3 <= 9363.

43.X1 + 42.X2 + 103.X3 <= 3922.

197.X1 + 103.X2 + 77.X3 <= 9273.

28.X1 + 30.X2 + 53.X3 --> MAX

BAPIANT 4

34.X1 + 26.X2 + 104.X3 <= 4000.

106.X1 + 194.X2 + 46.X3 <= 9460.

44.X1 + 41.X2 + 104.X3 <= 3975.

196.X1 + 104.X2 + 76.X3 <= 9460.

29.X1 + 29.X2 + 54.X3 --> MAX

BAPIANT 5

35.X1 + 25.X2 + 105.X3 <= 4100.

105.X1 + 195.X2 + 45.X3 <= 9495.

45.X1 + 40.X2 + 105.X3 <= 4090.

195.X1 + 105.X2 + 75.X3 <= 9525.

30.X1 + 28.X2 + 55.X3 --> MAX

BAPIANT 6

36.X1 + 24.X2 + 106.X3 <= 4200.

104.X1 + 196.X2 + 44.X3 <= 9724.

46.X1 + 39.X2 + 106.X3 <= 4246.

194.X1 + 106.X2 + 74.X3 <= 9694.

31.X1 + 27.X2 + 56.X3 --> MAX

BAPIANT 7

37.X1 + 23.X2 + 107.X3 <= 4300.

103.X1 + 197.X2 + 43.X3 <= 9713.

47.X1 + 38.X2 + 107.X3 <= 4257.

193.X1 + 107.X2 + 73.X3 <= 9683.

32.X1 + 26.X2 + 57.X3 --> MAX

BAPIANT 8

38.X1 + 22.X2 + 108.X3 <= 4400.

102.X1 + 198.X2 + 42.X3 <= 9744.

48.X1 + 37.X2 + 108.X3 <= 4376.

192.X1 + 108.X2 + 72.X3 <= 9744.

33.X1 + 25.X2 + 58.X3 --> MAX

BAPIANT 9

39.X1 + 21.X2 + 109.X3 <= 4500.

101.X1 + 199.X2 + 41.X3 <= 9972.

49.X1 + 36.X2 + 109.X3 <= 4533.

191.X1 + 109.X2 + 71.X3 <= 9912.

34.X1 + 24.X2 + 59.X3 --> MAX

BAPIANT 10

40.X1 + 20.X2 + 110.X3 <= 4600.

100.X1 + 200.X2 + 40.X3 <=10200.

50.X1 + 35.X2 + 110.X3 <= 4670.

190.X1 + 110.X2 + 70.X3 <=10090.

35.X1 + 23.X2 + 60.X3 --> MAX

BAPIANT 11

41.X1 + 19.X2 + 111.X3 <= 4700.

99.X1 + 201.X2 + 39.X3 <=10300.

51.X1 + 34.X2 + 111.X3 <= 4677.

189.X1 + 111.X2 + 69.X3 <=10143.

36.X1 + 22.X2 + 61.X3 --> MAX

BAPIANT 12

42.X1 + 18.X2 + 112.X3 <= 4800.

98.X1 + 202.X2 + 38.X3 <=10400.

52.X1 + 33.X2 + 112.X3 <= 4796.

188.X1 + 112.X2 + 68.X3 <=10264.

37.X1 + 21.X2 + 62.X3 --> MAX

BAPIANT 13

43.X1 + 17.X2 + 113.X3 <= 4900.

97.X1 + 203.X2 + 37.X3 <=10500.

53.X1 + 32.X2 + 113.X3 <= 4917.

187.X1 + 113.X2 + 67.X3 <=10383.

38.X1 + 20.X2 + 63.X3 --> MAX

BAPIANT 14

44.X1 + 16.X2 + 114.X3 <= 5000.

96.X1 + 204.X2 + 36.X3 <=10600.

54.X1 + 31.X2 + 114.X3 <= 5040.

186.X1 + 114.X2 + 66.X3 <=10500.

39.X1 + 19.X2 + 64.X3 --> MAX

BAPIANT 15

45.X1 + 15.X2 + 115.X3 <= 5100.

95.X1 + 205.X2 + 35.X3 <=10700.

55.X1 + 30.X2 + 115.X3 <= 5165.

185.X1 + 115.X2 + 65.X3 <=10615.

40.X1 + 18.X2 + 65.X3 --> MAX

BAPIANT 16

46.X1 + 14.X2 + 116.X3 <= 5200.

94.X1 + 206.X2 + 34.X3 <=10800.

56.X1 + 29.X2 + 116.X3 <= 5176.

184.X1 + 116.X2 + 64.X3 <=10664.

41.X1 + 17.X2 + 66.X3 --> MAX

BAPIANT 17

47.X1 + 13.X2 + 117.X3 <= 5300.

93.X1 + 207.X2 + 33.X3 <=10900.

57.X1 + 28.X2 + 117.X3 <= 5304.

183.X1 + 117.X2 + 63.X3 <=10776.

42.X1 + 16.X2 + 67.X3 --> MAX

BAPIANT 18

48.X1 + 12.X2 + 118.X3 <= 5400.

92.X1 + 208.X2 + 32.X3 <=11000.

58.X1 + 27.X2 + 118.X3 <= 5434.

182.X1 + 118.X2 + 62.X3 <=10886.

43.X1 + 15.X2 + 68.X3 --> MAX

BAPIANT 19

49.X1 + 11.X2 + 119.X3 <= 5500.

91.X1 + 209.X2 + 31.X3 <=11100.

59.X1 + 26.X2 + 119.X3 <= 5447.

181.X1 + 119.X2 + 61.X3 <=10933.

44.X1 + 14.X2 + 69.X3 --> MAX

BAPIANT 20

50.X1 + 10.X2 + 120.X3 <= 5600.

90.X1 + 210.X2 + 30.X3 <=11200.

60.X1 + 25.X2 + 120.X3 <= 5580.

180.X1 + 120.X2 + 60.X3 <=11040.

45.X1 + 13.X2 + 70.X3 --> MAX

BAPIANT 21

51.X1 + 9.X2 + 121.X3 <= 5700.

89.X1 + 211.X2 + 29.X3 <=11300.

61.X1 + 24.X2 + 121.X3 <= 5715.

179.X1 + 121.X2 + 59.X3 <=11145.

46.X1 + 12.X2 + 71.X3 --> MAX

BAPIANT 22

52.X1 + 8.X2 + 122.X3 <= 5800.

88.X1 + 212.X2 + 28.X3 <=11400.

62.X1 + 23.X2 + 122.X3 <= 5730.

178.X1 + 122.X2 + 58.X3 <=11190.

47.X1 + 11.X2 + 72.X3 --> MAX

BAPIANT 23

53.X1 + 7.X2 + 123.X3 <= 5900.

87.X1 + 213.X2 + 27.X3 <=11500.

63.X1 + 22.X2 + 123.X3 <= 5868.

177.X1 + 123.X2 + 57.X3 <=11292.

48.X1 + 10.X2 + 73.X3 --> MAX

BAPIANT 24

54.X1 + 6.X2 + 124.X3 <= 6000.

86.X1 + 214.X2 + 26.X3 <=11600.

64.X1 + 21.X2 + 124.X3 <= 6072.

176.X1 + 124.X2 + 56.X3 <=11568.

49.X1 + 9.X2 + 74.X3 --> MAX

BAPIANT 25

55.X1 + 5.X2 + 125.X3 <= 6100.

85.X1 + 215.X2 + 25.X3 <=11700.

65.X1 + 20.X2 + 125.X3 <= 6090.

175.X1 + 125.X2 + 55.X3 <=11610.

50.X1 + 8.X2 + 75.X3 --> MAX

BAPIANT 26

56.X1 + 4.X2 + 126.X3 <= 6200.

84.X1 + 216.X2 + 24.X3 <=11800.

66.X1 + 19.X2 + 126.X3 <= 6234.

174.X1 + 126.X2 + 54.X3 <=11706.

51.X1 + 7.X2 + 76.X3 --> MAX

BAPIANT 27

57.X1 + 3.X2 + 127.X3 <= 6300.

83.X1 + 217.X2 + 23.X3 <=11900.

67.X1 + 18.X2 + 127.X3 <= 6253.

173.X1 + 127.X2 + 53.X3 <=11747.

52.X1 + 6.X2 + 77.X3 --> MAX

BAPIANT 28

58.X1 + 2.X2 + 128.X3 <= 6400.

82.X1 + 218.X2 + 22.X3 <=12000.

68.X1 + 17.X2 + 128.X3 <= 6400.

172.X1 + 128.X2 + 52.X3 <=11840.

53.X1 + 5.X2 + 78.X3 --> MAX

BAPIANT 29

59.X1 + 1.X2 + 129.X3 <= 6500.

81.X1 + 219.X2 + 21.X3 <=12100.

69.X1 + 16.X2 + 129.X3 <= 6489.

171.X1 + 129.X2 + 51.X3 <=12051.

54.X1 + 4.X2 + 79.X3 --> MAX

BAPIANT 30

60.X1 + 0.X2 + 130.X3 <= 6600.

80.X1 + 220.X2 + 20.X3 <=12200.

70.X1 + 15.X2 + 130.X3 <= 6640.

170.X1 + 130.X2 + 50.X3 <=12140.

55.X1 + 3.X2 + 80.X3 --> MAX

BAPIANT 31

61.X1 + -1.X2 + 131.X3 <= 6700.

79.X1 + 221.X2 + 19.X3 <=12300.

71.X1 + 14.X2 + 131.X3 <= 6662.

169.X1 + 131.X2 + 49.X3 <=12178.

56.X1 + 2.X2 + 81.X3 --> MAX

BAPIANT 32

62.X1 + -2.X2 + 132.X3 <= 6800.

78.X1 + 222.X2 + 18.X3 <=12400.

72.X1 + 13.X2 + 132.X3 <= 6816.

168.X1 + 132.X2 + 48.X3 <=12264.

57.X1 + 1.X2 + 82.X3 --> MAX

BAPIANT 33

63.X1 + -3.X2 + 133.X3 <= 6900.

77.X1 + 223.X2 + 17.X3 <=12500.

73.X1 + 12.X2 + 133.X3 <= 6912.

167.X1 + 133.X2 + 47.X3 <=12468.

58.X1 + 0.X2 + 83.X3 --> MAX

BAPIANT 34

64.X1 + -4.X2 + 134.X3 <= 7000.

76.X1 + 224.X2 + 16.X3 <=12600.

74.X1 + 11.X2 + 134.X3 <= 7070.

166.X1 + 134.X2 + 46.X3 <=12550.

59.X1 + -1.X2 + 84.X3 --> MAX

BAPIANT 35

65.X1 + -5.X2 + 135.X3 <= 7100.

75.X1 + 225.X2 + 15.X3 <=12700.

75.X1 + 10.X2 + 135.X3 <= 7095.

165.X1 + 135.X2 + 45.X3 <=12585.

60.X1 + -2.X2 + 85.X3 --> MAX

BAPIANT 36

66.X1 + -6.X2 + 136.X3 <= 7200.

74.X1 + 226.X2 + 14.X3 <=12800.

76.X1 + 9.X2 + 136.X3 <= 7120.

164.X1 + 136.X2 + 44.X3 <=12620.

61.X1 + -3.X2 + 86.X3 --> MAX

BAPIANT 37

67.X1 + -7.X2 + 137.X3 <= 7300.

73.X1 + 227.X2 + 13.X3 <=12900.

77.X1 + 8.X2 + 137.X3 <= 7359.

163.X1 + 137.X2 + 43.X3 <=12861.

62.X1 + -4.X2 + 87.X3 --> MAX

BAPIANT 38

68.X1 + -8.X2 + 138.X3 <= 7400.

72.X1 + 228.X2 + 12.X3 <=13000.

78.X1 + 7.X2 + 138.X3 <= 7386.

162.X1 + 138.X2 + 42.X3 <=12894.

63.X1 + -5.X2 + 88.X3 --> MAX

BAPIANT 39

69.X1 + -9.X2 + 139.X3 <= 7500.

71.X1 + 229.X2 + 11.X3 <=13100.

79.X1 + 6.X2 + 139.X3 <= 7413.

161.X1 + 139.X2 + 41.X3 <=12927.

64.X1 + -6.X2 + 89.X3 --> MAX

BAPIANT 40

70.X1 + -10.X2 + 140.X3 <= 7600.

70.X1 + 230.X2 + 10.X3 <=13200.

80.X1 + 5.X2 + 140.X3 <= 7660.

160.X1 + 140.X2 + 40.X3 <=13160.

65.X1 + -7.X2 + 90.X3 --> MAX

BAPIANT 41

71.X1 + -11.X2 + 141.X3 <= 7700.

69.X1 + 231.X2 + 9.X3 <=13300.

81.X1 + 4.X2 + 141.X3 <= 7689.

159.X1 + 141.X2 + 39.X3 <=13191.

66.X1 + -8.X2 + 91.X3 --> MAX

BAPIANT 42

72.X1 + -12.X2 + 142.X3 <= 7800.

68.X1 + 232.X2 + 8.X3 <=13400.

82.X1 + 3.X2 + 142.X3 <= 7718.

158.X1 + 142.X2 + 38.X3 <=13222.

67.X1 + -9.X2 + 92.X3 --> MAX

BAPIANT 43

73.X1 + -13.X2 + 143.X3 <= 7900.

67.X1 + 233.X2 + 7.X3 <=13500.

83.X1 + 2.X2 + 143.X3 <= 7830.

157.X1 + 143.X2 + 37.X3 <=13410.

68.X1 + -10.X2 + 93.X3 --> MAX

BAPIANT 44

74.X1 + -14.X2 + 144.X3 <= 8000.

66.X1 + 234.X2 + 6.X3 <=13600.

84.X1 + 1.X2 + 144.X3 <= 8004.

156.X1 + 144.X2 + 36.X3 <=13476.

69.X1 + -11.X2 + 94.X3 --> MAX

BAPIANT 45

75.X1 + -15.X2 + 145.X3 <= 8100.

65.X1 + 235.X2 + 5.X3 <=13700.

85.X1 + 0.X2 + 145.X3 <= 8120.

155.X1 + 145.X2 + 35.X3 <=13660.

70.X1 + -12.X2 + 95.X3 --> MAX

BAPIANT 46

76.X1 + -16.X2 + 146.X3 <= 8200.

64.X1 + 236.X2 + 4.X3 <=13800.

86.X1 + -1.X2 + 146.X3 <= 8152.

154.X1 + 146.X2 + 34.X3 <=13688.

71.X1 + -13.X2 + 96.X3 --> MAX

BAPIANT 47

77.X1 + -17.X2 + 147.X3 <= 8300.

63.X1 + 237.X2 + 3.X3 <=13900.

87.X1 + -2.X2 + 147.X3 <= 8271.

153.X1 + 147.X2 + 33.X3 <=13869.

72.X1 + -14.X2 + 97.X3 --> MAX

BAPIANT 48

78.X1 + -18.X2 + 148.X3 <= 8400.

62.X1 + 238.X2 + 2.X3 <=14000.

88.X1 + -3.X2 + 148.X3 <= 8452.

152.X1 + 148.X2 + 32.X3 <=13928.

73.X1 + -15.X2 + 98.X3 --> MAX

BAPIANT 49

79.X1 + -19.X2 + 149.X3 <= 8500.

61.X1 + 239.X2 + 1.X3 <=14100.

89.X1 + -4.X2 + 149.X3 <= 8486.

151.X1 + 149.X2 + 31.X3 <=13954.

74.X1 + -16.X2 + 99.X3 --> MAX

BAPIANT 50

80.X1 + -20.X2 + 150.X3 <= 8600.

60.X1 + 240.X2 + 0.X3 <=14200.

90.X1 + -5.X2 + 150.X3 <= 8610.

150.X1 + 150.X2 + 30.X3 <=14130.

75.X1 + -17.X2 + 100.X3 --> MAX

Пример решения одного из вариантов.

BAPIANT 33

63.X1 + -3.X2 + 133.X3 <= 6900.

77.X1 + 223.X2 + 17.X3 <=12500.

73.X1 + 12.X2 + 133.X3 <= 6912.

167.X1 + 133.X2 + 47.X3 <=12468.

58.X1 + 0.X2 + 83.X3 --> MAX

X₁ X₂ X₃

1 0 0 0 63 -3 133 6900

0 1 0 0 77 223 17 12500

0 0 1 0 73 12 133 6912

0 0 0 1 167 133 47 12468

0 0 0 0 58 0 83 0

1 0 0 -0,37 0 -53,17 115,27 2196,5

0 1 0 -0,46 0 161,68 -4,67 6751,28

0 0 1 -0,43 0 -46,13 112,46 1461,92

0 0 0 0,01 1 0,8 0,28 74,66

0 0 0 -0,34 0 -46,19 66,68 -4330,2

1 0 -1,02 0,07 0 -5,88 0 698

0 1 0,04 -0,47 0 159,76 0 6812

0 0 0,01 -3,8e-3 0 -0,41 1 13

0 0 -2,5e-3 0,01 1 0,91 0 71

0 0 -0,59 -0,08 0 -18,83 0 -5197

Для получения оптимального решения оказалось достаточно двух итераций симплекс-метода. Как и следовало ожидать, оптимальное решение задачи соответствует целочисленным значениям базисных переменных.

F_max =5197 при = 698, = 6812, = 0, = 0,

X₁ = 71, X₂ = 0, X₃ = 13.