3. Нахождение оптимального плана работы флота и оптимальных схем движения судов.

Перенумеруем переменные, чтобы они были одноиндексными (табл. 3.1)

x11	x12	x13	x14	x15	x21	x22	x23	x24	x25	x31	x32	x33	x34	x35	Знак	Правые части ограничений
x 1	x 2	x 3	x4	x5	x6	x7	x8	x9	x10	x11	x12	x13	x14	x15
11		11			8		8			7		7			≤	600
12			12		7			7		6			6		≤	800
	11		11	11		7		7	7		7		7	7	≤	550
			12	12				8	8				6	6	≤	400
103	33	68	117	82											=	1460
					89	31	66	89	79						=	1825
										90	36	66	111	87	=	1825
521,5	254,1	269,5	816,9	564,9	343	161,7	196	515,9	368,9	297,5	161,7	171,5	443,1	317,1	→	max

Таблица 3.1 Переход от двухиндексной к одноиндексной нумерации переменных

Запишем математическую модель в координатной форме с использованием конкретных числовых данных:

Целевая функция:

Z = 521,5*x₁+ 254,1*x₂+ 269,5*x₃+ 816,9*x₄ + 564,9*x₅ + 343*x₆+ 161,7*x₇ + 196*x₈ +515,9*x₉ + 368,9*x₁₀ + 297,5* x₁₁ + 161,7* x₁₂+ 171,5* x₁₃ +443,1*x₁₄ + 317,1*x₁₅ – max

Ограничения:

11* x₁+8* x₆ + 7*x₁₁ + 11*x₃ + 8* x₈+ 7* x₁₃ 600;

12* x₁+7* x₆ + 6*x₁₁ + 12*x₄ +7* x₉ +6* x₁₄ 800;

11* x₂ +7* x₇ + 7*x₁₂ + 11*x₄ +7* x₉+7* x₁₄ + 11* x₅+ 7* x₁₀ + 7*x₁₅550;

12* x₄+ 8* x₉ +6* x₁₄ + 12* x₅+ 8* x₁₀ +6* x₁₅ 400;

103* x₁ +33* x₂+ 68* x₃+ 117*x₄ + 82*x₅= 1460;

89* x₆ +31* x₇+ 66* x₈+89*x₉ + 79*x₁₀= 1825;

90* х₁₁ +36* x₁₂+ 66 * x₁₃+111*x₁₄ + 87*x₁₅= 1825;

x_1-12  0

Перейдем от задачи в стандартной форме к задаче в канонической форме (преобразуем неравенства в уравнения с помощью дополнительных переменных):

Z = 521,5*x₁+ 254,1*x₂+ 269,5*x₃+ 816,9*x₄ + 564,9*x₅ + 343*x₆+ 161,7*x₇ + 196*x₈ +515,9*x₉ + 368,9*x₁₀ + 297,5* x₁₁ + 161,7* x₁₂+ 171,5* x₁₃ +443,1*x₁₄ + 317,1*x₁₅ +0*x₁₆+0*x₁₇+0*x₁₈+0*x₁₉ – max

Ограничения:

11* x₁+8* x₆ + 7*x₁₁ + 11*x₃ + 8* x₈+ 7* x₁₃ +x₁₆ = 600;

12* x₁+7* x₆ + 6*x₁₁ + 12*x₄ +7* x₉ +6* x₁₄ + x₁₇ = 800;

11* x₂ +7* x₇ + 7*x₁₂ + 11*x₄ +7* x₉+7* x₁₄ + 11* x₅+ 7* x₁₀ + 7*x₁₅ +x₁₈ =550;

12* x₄+ 8* x₉ +6* x₁₄ + 12* x₅+ 8* x₁₀ +6* x₁₅ +x₁₉ = 400;

103* x₁ +33* x₂+ 68* x₃+ 117*x₄ + 82*x₅= 1460;

89* x₆ +31* x₇+ 66* x₈+89*x₉ + 79*x₁₀= 1825;

90* х₁₁ +36* x₁₂+ 66 * x₁₃+111*x₁₄ + 87*x₁₅= 1825;

x_1-19 0

Обозначаем вектора условий:

; ;;;;;;;;;;;;;;;;

Для ограничений 2-ого типа применим метод искусственного базиса и введём искусственные переменные x₂₀, x₂₁ и x₂₂.

Z = 521,5*x₁+ 254,1*x₂+ 269,5*x₃+ 816,9*x₄ + 564,9*x₅ + 343*x₆+ 161,7*x₇ + 196*x₈ +515,9*x₉ + 368,9*x₁₀ + 297,5* x₁₁ + 161,7* x₁₂+ 171,5* x₁₃ +443,1*x₁₄ + 317,1*x₁₅ +0*x₁₆+0*x₁₇+0*x₁₈+0*x₁₉ – M*x₂₀ – M*x₂₁ – M*x₂₂ – max

Ограничения:

11* x₁+8* x₆ + 7*x₁₁ + 11*x₃ + 8* x₈+ 7* x₁₃ +x₁₆ = 600;

12* x₁+7* x₆ + 6*x₁₁ + 12*x₄ +7* x₉ +6* x₁₄ + x₁₇ = 800;

11* x₂ +7* x₇ + 7*x₁₂ + 11*x₄ +7* x₉+7* x₁₄ + 11* x₅+ 7* x₁₀ + 7*x₁₅ +x₁₈ =550;

12* x₄+ 8* x₉ +6* x₁₄ + 12* x₅+ 8* x₁₀ +6* x₁₅ +x₁₉ = 400;

103* x₁ +33* x₂+ 68* x₃+ 117*x₄ + 82*x₅ +x₂₀= 1460;

89* x₆ +31* x₇+ 66* x₈+89*x₉ + 79*x₁₀ +x₂₁= 1825;

90* х₁₁ +36* x₁₂+ 66 * x₁₃+111*x₁₄ + 87*x₁₅ +x₂₂= 1825;

x_1-22  0

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

A₁₆=A₁₇=A₁₈=A₁₉=A₂₀=A₂₁=

A₂₂=B=

Вычислим значение базисных переменных. Тогда исходный опорный план расширенной задачи таков:

X= (x₁=0; x₂=0; x₃=0; x₄=0; x₅=0; x₆=0; x₇=0; x₈=0; x₉=0; x₁₀=0; x₁₁=0; x₁₂=0; x₁₃=0; x₁₄=0; x₁₅=0; x₁₆=600; x₁₇=800; x₁₈=550; x₁₉=400; x₂₀=1460; x₂₁=1825; x₂₂=1825).