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

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

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

x11	x12	x13	x14	x21	x22	x23	x24	Знак	Правые части ограничений
x 1	x 2	x 3	x4	x5	x6	x7	x8
11				8				≤	320
			10				7	≤	250
10	10			9	9			≤	340
	11	11	11		9	9	9	≤	150
125	119	56	109					=	2555
				115	117	55	99	=	2190
457,8	396,2	200,2	424,2	366,8	340,2	163,8	320,6	→	max

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

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

Z = 457,8* x₁+ 396,2* x₂+ 200,2* x₃+ 424,2*x₄ + 366,8* x₅+ 340,2* x₆+ 163,8* x₇ +320,6*x₈ – max

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

11* x₁+8* x₂320;

10* x₄ + 7* x₈250;

10* x₁+10* x₂+9x₅+9x₆340;

11* x₂+ 11* x₃ +11* x₄ + 9* x₆+9x₇+9x₈ 150;

125* x₁ +119* x₂+ 56* x₃+109x₄= 2555

115* x₅ +117* x₆+ 55* x₇+99x₈= 2190

x_1-8  0

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

Z = 457,8* x₁+ 396,2* x₂+ 200,2* x₃+ 424,2*x₄ + 366,8* x₅+ 340,2* x₆+ 163,8* x₇ +320,6*x₈ +0*x₉+0*x₁₀+0*x₁₁+0*x₁₂ – max

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

11* x₁+8* x₂+x₉₌320;

10* x₄ + 7* x₈+x₁₀=250;

10* x₁+10* x₂+9x₅+9x₆+x₁₁=340;

11* x₂+ 11* x₃ +11* x₄ + 9* x₆+9x₇+9x₈+x₁₂=150;

125* x₁ +119* x₂+ 56* x₃+109x₄= 2555

115* x₅ +117* x₆+ 55* x₇+99x₈= 2190

x_1-12  0

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

; ;;;;;;;;;;

Данная система ограничений не содержит нужных для построения базиса (m+n) единичных векторов – условий. Применим метод искусственного базиса и перейдем от исходной задачи к расширенной путем ввода искусственных переменных x₁₃ и x₁₄.

Z = 457,8* x₁+ 396,2* x₂+ 200,2* x₃+ 424,2*x₄ + 366,8* x₅+ 340,2* x₆+ 163,8* x₇ +320,6*x₈ +0*x₉+0*x₁₀+0*x₁₁+0*x₁₂ –М*x₁₃ –М*x₁₄– max

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

11* x₁+8* x₂+x₉320;

10* x₄ + 7* x₈+x₁₀250;

10* x₁+10* x₂+9x₅+9x₆+x₁₁340;

11* x₂+ 11* x₃ +11* x₄ + 9* x₆+9x₇+9x₈+x₁₂ 150;

125* x₁ +119* x₂+ 56* x₃+109x₄ – x₁₃= 2555

115* x₅ +117* x₆+ 55* x₇+99x₈ – x₁₄= 2190

x_1-14  0

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

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₉=320; x₁₀=250; x₁₁=340; x₁₂=150; x₁₃=2555; x₁₄=2190).

Составим симплекс-таблицу для исходного опорного плана расширенной задачи (табл.3.2).

17

Таблица 3.2 Симплекс таблица для исходного опорного плана

Строка	Базис	Сб	В	457,8	396,2	200,2	424,2	366,8	340,2	163,8	320,6	0	0	0	0	-M	-M
				x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12	x13	x14
1	Х9	0	320	11	8	0	0	0	0	0	0	1	0	0	0	0	0
2	Х10	0	250	0	0	0	10	0	0	0	7	0	1	0	0	0	0
3	Х11	0	340	10	10	0	0	9	9	0	0	0	0	1	0	0	0
4	Х12	0	150	0	11	11	11	0	9	9	9	0	0	0	1	0	0
5	Х13	M	2555	125	119	56	109	0	0	0	0	0	0	0	0	1	0
6	Х14	M	2190	0	0	0	0	115	117	55	99	0	0	0	0	0	1
m+1	Zj + Cj		0	-457,8	-396,2	-200,2	-424,2	-366,8	-340,2	-163,8	-320,6	0	0	0	0	0	0
m+2			4745	-125	-119	-56	-109	-115	-117	-55	-99	0	0	0	0	0	0

18

План в табл. 3.2 неоптимальный, так как есть отрицательные оценки, а задача на максимум. Оптимальный план находим с помощью ПЭВМ типа PENTIUM по программе симплекс – метода.

Пакет прикладных программ (ППП) ПЭР – пакет экономических расчетов является адаптацией пакета «Системы количественного анализа в управлении» версии 5.0.

ППП ПЭР предназначен для решения ряда экономико – математических задач на персональных компьютерах типа PENTIUM. В пакете реализованы наиболее часто используемые экономико – математические задачи и методы, в частности: линейное программирование.

Максимальные размеры решаемых задач: 40 основных переменных и 40 ограничений. Программа линейного программирования использует симплексный – метод решения задач.

В основном меню пакета выбираем пирамиду LP, при этом осуществляем переход к решению конкретной задачи. Решение задачи начинается с появления на экране меню, где мы выбираем опцию «Ввод новой задачи». Ввод начинается с задания имени задачи, которое должно содержать не более 6 символов.

Далее вводятся характеристики задачи:

1. признак оптимальности: при максимизации вводим 1;

2. число переменных;

3. число ограничений;

4. символ “N”, чтобы не пользоваться именами переменных.

После определения задачи и ввода имен переменных программа высвечивает экран для ввода коэффициентов модели.

Затем, выбираем опцию «Решение задачи», на экране появляется меню решение задачи, в которой выбираем «Решить и вывести начальную и конечную таблицы ».

После этого надо сохранить задачу, для этого мы вызываем опцию «Вывод (печать окончательного решения задачи)» - на экране появляется меню выводарешения, где выбираем вывод на экран и печать окончательного решения.

Я получила следующую таблицу (табл. 3.3)

Таблица 3.3. Оптимальный план задачи

Х₁ = Х₁₁ = 8,55 S₁ = 225,96

Х₂ = Х₁₂ = 0 S₂ = 113,6364

Х₃ = Х₁₃ = 0 S₃ = 83,1178

Х₄ = Х₁₄ = 13,64 S₄ =0

Х₅ = Х₂₁ = 19,04 А₅=0

Х₆ = Х₂₂ = 0 А₆=0

Х₇ = Х₂₃ = 0 Z_max=16683,47

Х₈ = Х₂₄ = 0 итерац. = 5

Экономический смысл полученных данных таков:

Х₁₁=9 - судами 1-го типа выполнено 9 рейсов по 1й схеме.

Х₁₂= 0 - Судами 1-го типа выполнено 0 рейсов по 2-й схеме.

Х₁₃= 0 - Судами 1-го типа выполнено 0 рейсов по 3-й схеме.

Х₁₄= 14 - Судами 1го типа выполнено 14 рейсов по 4-й схеме.

Х₂₁=19 - Судами 2го типа выполнено 19 рейсов по 1-й схеме.

Х₂₂=0 - Судами 2-го типа выполнено 0 рейсов по 2-й схеме.

Х₂₃=0 - Судами 2-го типа выполнено 0 рейсов по 3-й схеме.

Х₂₄=0 - Судами 2-го типа выполнено 0 рейсов по 4-й схеме.

Z_max= 16683,47 – максимальный доход в инвалюте при работе судов по схемам.

В результате решения задачи получили оптимальные схемы движения.