Пример решения Р-методом

Условие задачи. Предприятию необходимо выпустить по плану продукции А1 – 500 единиц, А2 – 300 единиц, А3 – 450 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P – метода.

Матрица затрат времени на производство видов продукции g – го вида A=(aig)

Машины
 

Виды продукции

Ресурс времени машин

А1

А2

А3

1

2

3

3

1500

2

5

4

1

1000

План выпуска продукции

500

300

450

 

Составим математическую модель задачи.
2x11 + 3x12 +3x13 ≤ 1500
5x21 + 4x22 +x23 ≤ 1000
x11 + x21 ≥ 500
x12 + x22 ≥ 300
x13 + x23 ≥ 450
Целевая функция:
2x11 + 3x12 +3x13 + 5x21 + 4x22 +x23 → min
Запишем в виде, решаемом Р-методом.
2x11 + 3x12 +3x13 ≤ 1500
5x21 + 4x22 +x23 ≤ 1000
-x11  -x21 ≤ -500
-x12 -x22 ≤ -300
-x13 -x23 ≤ -450

Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием калькулятора P-метод.
Определим минимальное значение целевой функции F(X) = 2x1+3x2+3x3+5x4+4x5+x6 при следующих условиях-ограничений.
2x1+3x2+3x3≤1500
5x4+4x5+x6≤1000
-x1-x4≤-500
-x2-x5≤-300
-x3-x6≤-450
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x1 + 3x2 + 3x3 + 0x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1500
0x1 + 0x2 + 0x3 + 5x4 + 4x5 + 1x6 + 0x7 + 1x8 + 0x9 + 0x10 + 0x11 = 1000
-1x1 + 0x2 + 0x3-1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 1x9 + 0x10 + 0x11 = -500
0x1-1x2 + 0x3 + 0x4-1x5 + 0x6 + 0x7 + 0x8 + 0x9 + 1x10 + 0x11 = -300
0x1 + 0x2-1x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 + 0x9 + 0x10 + 1x11 = -450
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:


2

3

3

0

0

0

1

0

0

0

0

0

0

0

5

4

1

0

1

0

0

0

-1

0

0

-1

0

0

0

0

1

0

0

0

-1

0

0

-1

0

0

0

0

1

0

0

0

-1

0

0

-1

0

0

0

0

1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x7, x8, x9, x10, x11,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,0,0,1500,1000,-500,-300,-450)

План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

0

x7

1500

2

3

3

0

0

0

1

0

0

0

0


x8

1000

0

0

0

5

4

1

0

1

0

0

0


x9

-500

-1

0

0

-1

0

0

0

0

1

0

0


x10

-300

0

-1

0

0

-1

0

0

0

0

1

0


x11

-450

0

0

-1

0

0

-1

0

0

0

0

1

Индексная строка

F(X0)

0

-2

-3

-3

-5

-4

-1

0

0

0

0

0

θ

 

 

2

 

 

5

 

 

 

 

 

 

 

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 3-ая строка, а переменную x9 следует вывести из базиса.
В строку θ заносим следующие величины:
Минимальное значение θ соответствует 1-му столбцу, т.е. переменную x1 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный -1.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

План
 

Базис
 

В
 

x1
 

x2
 

x3
 

x4
 

x5
 

x6
 

x7
 

x8
 

x9
 

x10
 

x11
 

0
 

x7
 

500
 

0
 

3
 

3
 

-2
 

0
 

0
 

1
 

0
 

2
 

0
 

0
 

 
 

x8
 

1000
 

0
 

0
 

0
 

5
 

4
 

1
 

0
 

1
 

0
 

0
 

0
 

 
 

x1
 

500
 

1
 

0
 

0
 

1
 

0
 

0
 

0
 

0
 

-1
 

0
 

0
 

 
 

x10
 

-300
 

0
 

-1
 

0
 

0
 

-1
 

0
 

0
 

0
 

0
 

1
 

0
 

 
 

x11
 

-450
 

0
 

0
 

-1
 

0
 

0
 

-1
 

0
 

0
 

0
 

0
 

1
 

Индексная строка
 

F(X)
 

1000
 

0
 

-3
 

-3
 

-3
 

-4
 

-1
 

0
 

0
 

-2
 

0
 

0
 

θ

 

 

 

 

3

 

 

1

 

 

 

 

 

План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 5-ая строка, а переменную x11 следует вывести из базиса.
В строку θ заносим следующие величины:
Минимальное значение θ соответствует 6-му столбцу, т.е. переменную x6 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный -1.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

0

x7

500

0

3

3

-2

0

0

1

0

2

0

0


x8

550

0

0

-1

5

4

0

0

1

0

0

1


x1

500

1

0

0

1

0

0

0

0

-1

0

0


x10

-300

0

-1

0

0

-1

0

0

0

0

1

0


x6

450

0

0

1

0

0

1

0

0

0

0

-1

Индексная строка

F(X)

1450

0

-3

-2

-3

-4

0

0

0

-2

0

-1

θ

 

 

 

3

 

 

4

 

 

 

 

 

 

План 2 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 4-ая строка, а переменную x10 следует вывести из базиса.
В строку θ заносим следующие величины:

Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный -1.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

0

x7

-400

0

0

3

-2

-3

0

1

0

2

3

0


x8

550

0

0

-1

5

4

0

0

1

0

0

1


x1

500

1

0

0

1

0

0

0

0

-1

0

0


x2

300

0

1

0

0

1

0

0

0

0

-1

0


x6

450

0

0

1

0

0

1

0

0

0

0

-1

Индексная строка

F(X)

2350

0

0

-2

-3

-1

0

0

0

-2

-3

-1

θ

 

 

 

 

 

1,5

0,33

 

 

 

 

 

 

План 3 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 1-ая строка, а переменную x7 следует вывести из базиса.
В строку θ заносим следующие величины:
Минимальное значение θ соответствует 5-му столбцу, т.е. переменную x5 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный -3.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

0

x5

133.33

0

0

-1

0.6667

1

0

-0.3333

0

-0.6667

-1

0


x8

16.67

0

0

3

2.33

0

0

1.33

1

2.67

4

1


x1

500

1

0

0

1

0

0

0

0

-1

0

0


x2

166.67

0

1

1

-0.6667

0

0

0.3333

0

0.6667

0

0


x6

450

0

0

1

0

0

1

0

0

0

0

-1

Индексная строка

F(X)

2483.33

0

0

-3

-2.33

0

0

-0.3333

0

-2.67

-4

-1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

В базисном столбце все элементы положительные.
Окончательный вариант симплекс-таблицы:

План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

1

x5

133.33

0

0

-1

0.6667

1

0

-0.33

0

-0.6667

-1

0


x8

16.67

0

0

3

2.33

0

0

1.33

1

2.67

4

1


x1

500

1

0

0

1

0

0

0

0

-1

0

0


x2

166.67

0

1

1

-0.6667

0

0

0.33

0

0.6667

0

0


x6

450

0

0

1

0

0

1

0

0

0

0

-1


F(X1)

2483.33

0

0

-3

-2.33

0

0

-0.33

0

-2.67

-4

-1

Оптимальный план можно записать так:
x5 = 133.33
x8 = 16.67
x1 = 500
x2 = 166.67
x6 = 450
F(X) = 2*500 + 3*166.67 + 4*133.33 + 1*450 = 2483.33
загрузка...