logo
Методы решения задач математического моделирования

2.3 Решение задачи планирования производства симплекс-методом

Введем базисные переменные и преобразуем исходную задачу к виду:

Z= 40x1 + 30x2 + 0x3 + 0x4 + 0x5 > max

Решим систему уравнений относительно базисных переменных: x3, x4, x5.

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,240,180,251)

"right">Таблица 2.3.1

Итерация № 0

Базис

Сб

X1

X2

X3

X4

X5

Свободные члены

Отношение

X3

0

4

1

1

0

0

240

240/4

X4

0

2

3

0

1

0

180

180/2

X5

0

1

5

0

0

1

251

251/1

Z

-40

-30

0

0

0

0

-

При составлении исходной симплекс таблицы (Табл. 2.3.1), коэффициенты при переменных функции ?? записываются с противоположными знаками, а свободный член со своим знаком.

Сб - вектор, составленный из координат соответствующих базисных переменных.

Текущий план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

Ведущий столбец X1, так как -40 - наименьшее отрицательное число.

За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим.

"right">Таблица 2.3.2

Разрешающий элемент 4

Базис

Сб

X1

X2

X3

X4

X5

Отношение

X3

0

4

1/4

1/4

0

0

60

60

X4

0

2

3

0

1

0

180

90

X5

0

1

5

0

0

1

251

251

Z

-40

-30

0

0

0

0

-

От элементов строки 2 отнимаем соответствующие элементы строки 1, умноженные на 2.

От элементов строки 3 отнимаем соответствующие элементы строки 1, умноженные на 1.

От элементов строки ?? отнимаем соответствующие элементы строки 1, умноженные на -40 (Табл. 2.3.2)

Заменяем базисную переменную X3 на X1

"right">Таблица 2.3.3

Итерация № 1

Базис

Сб

X1

X2

X3

X4

X5

Свободные члены

Отношение

X1

0

1

0,25

0,25

0

0

60

240

X4

0

0

2,5

-0,5

1

0

60

24

X5

40

0

4,75

-0,25

0

1

191

40,21

Z

0

-20

10

0

0

2400

0

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты (Табл. 2.3.3).

За ведущий выберем столбец 2, так как -20 наименьший элемент в ?? строке.

За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим.

Разрешающий элемент 2,5

Разделим элементы строки 2 на 2,5(Табл. 2.3.3).

"right">Таблица 2.3.4

Базис

Сб

X1

X2

X3

X4

X5

Свободные члены

Отношение

X1

0

1

0,25

0,25

0

0

60

240

X4

20

0

1

-0,2

0,4

0

24

24

X5

40

0

4,75

-0,25

0

1

191

40,21

Z

0

-20

10

0

0

2400

0

От элементов строки 1 отнимаем соответствующие элементы строки 2, умноженные на 0,25.

От элементов строки 3 отнимаем соответствующие элементы строки 2, умноженные на 4,75.

От элементов строки ?? отнимаем соответствующие элементы строки 2, умноженные на -20

"right">Таблица 2.3.5

Базис

Сб

X1

X2

X3

X4

X5

Свободные члены

X1

0

1

0

0,3

-0,1

0

54

X2

20

0

1

-0,2

0,4

0

24

X5

40

0

0

0,7

-1,9

1

77

Z

0

0

6

8

0

2880

X2 = (54, 24, 77, 0, 0)

??(X2) = 40*54 + 30*24 = 2880 (Табл. 2.3.5).

Ответ: Для достижения максимальной прибыли 2880 ден.ед. следует производить 54 ед. продукции вида А1 и 24 ед. продукции вида А2. (ответ совпадает с ответом полученным графическим способом).