Становление и развитие математического моделирования

q_mi+1x_m+1 + q_mi+2x_m+2+…+q_inx_n – x_n+1 = q_i;   x_n+1>=0.

При добавлении этого ограничения  к исходной задаче получаем задачу большей размерности.

Эту задачу решают обычным  симплекс-методом, т.е. переходя к этапу1.

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

 

Задача: Для приобретения нового оборудования предприятие выделяет

19 ден.ед. Оборудование должно  быть размещено на площади,  не превышающей 16 кв.м. Предприятие  может заказать оборудование  двух видов: машины типа “А”  стоимостью 2 ден.ед., требующие производственную  площадь 

4 км² и обеспечивающие производительность за смену 8 т продукции, и машины типа “В” стоимостью 5 ден.ед., занимающие площадь 1м² и обеспечивающие производительность за смену 6 т продукции.

Требуется составить оптимальный  план приобретения оборудования, обеспечивающий максимальную общую производительность.

Решение: Обозначим через x₁, x₂ количество машин соответственно типа “А” и “В”, через L - их общую производительность. Тогда математическая модель задачи:                                         max L = 8x₁ + 6x₂

при ограничениях:

2x₁+5x₂ ≤ 19 
4x₁+x₂ ≤ 16 
x₁ ≥ 0, x₂ ≥ 7 
x₁ , x₂ - целые числа

Решаем задачу симплексным  методом без учета целочисленности.

Co	Бo	Хo	8	6	-	-
			x1	x2	x3	x4
-  -	x3  x4	19  16	2  4	5  1	1  -	-  1
zj  j		0	-	-	-	-
			-8	-6	-	-

 

C1	Б1	Х1	8	6	-	-
			x1	x2	x3	x4
-  8	x3  x1	11  4	-  1	9/2  1/4	1  -	-1/2  1/4
zj  j		32	80	2	-	2
			-	-4	-	2

 

C2	Б2	Х2	8	6	-	-	-
			x1	x2	x3	x4	S1
6  8	x2  x1	22/9  61/18	-  1	1  -	2/9  -1/18	-1/9  5/18	-  -
zj  j		376/9	8	6	8/9	14/9	-
			-	-	8/9	14/9	-
		4/9	-	-	2/9	8/9	-1

 

 

Получен оптимальный нецелочисленный  план Х_опт= (61/18;22/9).  

L_max = 376/9.

Т.к. у компоненты плана х₂ максимальная дробная часть:  
max(4/9;7/18) = 4/9, то дополнительное ограничение записываем по первой строке.

22/9 - [22/9] = (2/9 - [2/9])x₃ + (-1/9 - [-1/9])x₄ - S₁, S₁ ≥ 0 
22/9 - 2 = (2/9 - 0)x₃ + (-1/9 - (-1))x₄ - S₁, S₁ ≥  0 
4/9 = 2/9x₃ + 8/9x₄ - S₁, S₁ ≥ 0  -  первое ограничение Гомори.

Составленное ограничение  дописываем к имеющимся в симплексной  таблице.

После построения дополнительного  ограничения имеем новую задачу линейного программирования, в которой 3 ограничения. Для получения опорного плана этой задачи необходимо найти  третий базисный вектор. Для этого  определяем:

=> в базис вводим вектор х₄.

 

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

C3	Б3	Х3	8	6	-	-	-	-
			x1	x2	x3	x4	S1	S2
6  8  -	x2  x1  x4	5/2  13/4  1/2	-  1  -	1  -  -	1/4  -1/8  1/4	-  -  1	-1/8  5/16  -9/8	-  -  -
zj  j		41	8	6	1/2	-	7/4	-
			-	-	1/2	-	7/4	-
		1/2	-	-	1/4	-	7/8	-1

 

 

 

 

 

 

 

 

 

Найденный план оптимален, но нецелочисленный. Строим новое ограничение  Гомори.

Т.к. максимальная дробная  часть среди компонент плана  равна 1/2, записываем дополнительное ограничение  по первой строке (можно и по третьей).

5/2 - [5/2] = (1/4 - [1/4])x₃ + (-1/8 - [-1/8])S₁ - S₂, S₂ ≥ 0 
1/2 = 1/4x₃ + 7/8S₁ - S₂, S₂ ≥ 0 -   второе ограничение Гомори

Это ограничение добавляем  в последнюю симплексную таблицу.

Получили задачу, в которой 4 ограничения, следовательно, в базисе должно быть 4 единичных вектора.

Определяем вектор, вводимый в базис: Можно ввести либо x₃, либо S₁. Введем вектор S₁.

=>соответствует  дополнительному ограничению.

 

C4	Б4	Х4	8	6	-	-	-	-	-
			x1	x2	x3	x4	S1	S2	S3
6  8  -	x2  x1  x4	18/7  43/14  8/7	-  1  -	1  -  -	2/7  -3/14  4/7	-  -  1	-  -  -	-1/7  5/14  -9/7	-  -  -
-	S1	4/7	-	-	2/7	-	1	-8/7	-
zj  j		40	8	6	-	-	-	2	-
			-	-	-	-	-	2	-
		4/7	-	-	2/7	-	-	6/7	-1

 

Получаем новый оптимальный  нецелочисленный план. Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие переменной S₁.

В полученном плане максимальную дробную часть имеет компо-нента  х₂, поэтому записываем дополнительное ограничение по первой строке.

4/7 = 2/7х₃ + 6/7S₂ - S₃,    S₃ ≥  0    - третье ограничение Гомори.

Определяем вектор, вводимый в базис: Это вектор х₃. Минимальное значение q = 2, что соответствует дополнительной строке.

C5	Б5	Х5	8	6	-	-	-	-	-
			x1	x2	x3	x4	S2	S3	S4
6  8  -  -	x2  x1  x4  x3	2  7/2  -  2	-  1  -  -	1  -  -  -	-  -  -  1	-  -  1  -	-1  1  -3  3	1  -3/4  2  -7/2	-  -  -  -
zj  j		40	8	6	-	-	-	2	-
			-	-	-	-	-	2	-
		4/7	-	-	-	-	-	1/4	-1

 

 

 

 

 

 

 

 

 

 

 

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

План Х₅ - оптимальный нецелочисленный.

Дополнительное ограничение  запишем по второй строке:

1/2 = 1/4S₃ - S₄,  S₄ ≥ 0   - четвертое ограничение Гомори.

Т.к. базисной компонентой может  быть S₃, определяем величину . Минимальное значение получилось по 3 строке, а не по строке Гомори, следовательно, переходим к М-задаче: введем дополнительную переменную х₅ в ограничение Гомори.

 

-	Б5	Х5	8	6	-	-	-	-	-	-M
			x1	x2	x3	x4	S2	S3	S4	x5
6  8  -  -  -M	x2  x1  x4  x3  x5	2  7/2  -  2  1/2	-  1  -  -  -	1  -  -  -  -	-  -  -  1  -	-  -  1  -  -	-1  1  -3  3  -	1  -3/4  2  -7/2  1/4	-  -  -  -  -1	-  -  -  -  1
zj  j		40-  -M/2	8	6	-	-	2	-M/4	M	-M
			-	-	-	-	2	-M/4	M	-

C6	Б6	Х6	8	6	-	-	-	-	-	-M
			x1	x2	x3	x4	S2	S3	S4	x5
6  8	x2  x1	2  7/2	-  1	1  -	-  -	-1/2  3/8	1/2  -1/8	-  -	-  -	-  -
-	S3	-	-	-	-	1/2	-3/2	1	-	-
-  -M	x3  x5	2  1/2	-  -	-  -	1  -	7/4  -1/8	-9/4  3/8	-  -	-  -1	-  1
zj  j		40-  -M/2	8	6	-	M/8	2-3M/8	-	M	-M
			-	-	-	M/8	2-3M/8	-	M	-

C7	Б7	Х7	8	6	-	-	-	-	-
			x1	x2	x3	x4	S2	S4	S5
6  8  -	x2  x1  x3	4/3  11/3  5	-  1  -	1  -  -	-  -  1	-1/3  1/3  1	-  -  -	4/3  -1/3  -6	-  -  -
-	S2	4/3	-	-	-	-1/3	1	-8/3	-
zj  j		112/3	8	6	-	2/3	-	16/3	-
			-	-	-	2/3	-	16/3	-
		2/3	-	-	-	1/3	-	2/3	-1