Основы математического программирования (стр. 11 )

БП	СЧ	x1	y1	…	xn
x2	b1’	a11’	a12’	…	a1n’
y2	b2/’	a21’	a22	…	a2n’
…	…	…	…	…	…
ym	bm’	am1’	am2’	…	amn’
Z	Q	c1’	c2’	…	cn’

Если полученное таким образом решение целочисленное, то оно принимается за оптимальное.

Если решение нецелочисленное, то система ограничений дополняется дополнительным условием.

Предположим, что х2 – дробное значение, составим дополнительное ограничение для этой переменной.

Через βij обозначим ближайшее целое число, не превосходящее свободный член и коэффициенты в строке, в которой находится переменная с дробным значением.

Для каждого коэффициента составим разность

αij = aij - βij

αсв.j = bj - βij

Для дробной переменной х2 из коэффициентов составим дополнительное условие:

α11х1 + α12y1 + … + α1nхn ≥ αсв. чл.

Далее вводим еще одну переменную S = α11х1 + α12y1 + … + α11хn - αсв. чл. и добавляем ее в базисные переменные. Далее обычный симплекс-метод. В качестве разрешающей строки выбираем строку с новой переменной.

Пример. 1.

Zmax = 4x1 + 5x2 + x3

3x1 + 2x2 ≤ 10 3x1 + 2x2 + y1 = 10

x1 + 4x2 ≤ 11 x1 + 4x2 + y2 = 11

3x1 + 3x2 + x3 ≤ 13 3x1 + 3x2 + x3 + y3 = 13

БП	СЧ	y1	y2	y3	x1	x2	x3
y1	10	1	0	0	3	2	0
y2	11	0	1	0	1	4	0
y3	13	0	0	1	3	3	1
Z	0	0	0	0	-4	-5	-1

БП	СЧ	y1	y2	y3	x1	x2	x3
y1	18/4	1	-2/4	0	10/4	0	0
x2	11/4	0	1/4	0	1/4	1	0
y3	19/4	0	-3/4	1	9/4	0	1
Z	55/4	0	5/4	0	-11/4	0	-1

БП	СЧ	y1	y2	y3	x1	x2	x3
x1	18/10	4/10	-2/10	0	1	0	0
x2	23/10	-1/10	3/10	0	0	1	0
y3	7/10	-9/10	-3/10	1	0	0	1
Z	187/10	11/10	7/10	0	0	0	-1

БП	СЧ	y1	y2	y3	x1	x2	x3
x1	18/10	4/10	-2/10	0	1	0	0
x2	23/10	-1/10	3/10	0	0	1	0
x3	7/10	-9/10	-3/10	1	0	0	1
Z	194/10	2/10	4/10	1	0	0	0

Таблица последняя, нет отрицательных чисел в последней строке. Решение нецелочисленное. Вводим дополнительное условие, например для x1, так как оно нецелочисленное.