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

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

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

x11	x12	x13	x14	x21	x22	x23	x24	х31	х32	x33	x34	Знак	Правые части ограничений
x 1	x 2	x 3	x4	x5	x6	x7	x8	x9	x10	x11	x12
12	12	12		6	6	6		11	11	11		≤	600
		12				6				10		≤	750
			11				6				10	≤	600
11				5				11				≤	750
50	28	46	34									=	1095
				43	24	35	24					=	1825
								42	23	35	23	=	1825
273,3	126	277,2	123,2	129,5	63	126	67,2	261,8	115,5	241,5	112	→	max

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

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

Z=273.3*x₁+126*x₂+277.2*x₃+123.2*x₄+129.5*x₅+63*x₆+126*x₇+67.2*x₈+261.8 *x₉+ 115.5* x₁₀+ 241.5* x₁₁ +112*x₁₂ – max

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

12 x₁+12 x₂+12 x₃+6 x₅+6 x₆+6 x₇+11 x₉+11 x₁₀+11 x₁₁600;

12 x₃ +5 x₇+10 x₁₁ 750;

11 x₄+6 x₈+10x₁₂ 600;

11 x₁+ 5 x₅ +11 x₉ 750;

50 x₁ +28 x₂+ 46 x₃+34x₄= 1095

43 x₅ +24 x₆+ 35 x₇+24x₈= 1825

42 x₉ +23 x₁₀+ 35 x₁₁+23x₁₂= 1825

x_1-12 0

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

Z=273.3*x₁+126*x₂+277.2*x₃+123.2*x₄+129.5*x₅+63*x₆+126*x₇+67.2*x₈+261.8 *x₉+ 115.5* x₁₀+ 241.5* x₁₁ +112*x₁₂ +0*x₁₃+0*x₁₄+0*x₁₅+0*x₁₆– max

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

12 x₁+12 x₂+12 x₃+6 x₅+6 x₆+6 x₇+11 x₉+11 x₁₀+11 x₁₁+x₁₃=600;

12 x₃ +5 x₇+10 x₁₁+x₁₄ =750;

11 x₄+6 x₈+10x₁₂+x₁₅ =600;

11 x₁+ 5 x₅ +11 x₉ +x₁₆=750;

50 x₁ +28 x₂+ 46 x₃+34x₄= 1095

43 x₅ +24 x₆+ 35 x₇+24x₈= 1825

42 x₉ +23 x₁₀+ 35 x₁₁+23x₁₂= 1825

x_1-16 0

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

А₁=А₂=А₃=А₄=А₅=А₆=А₇=

А₈=А₉=А₁₀=А₁₁₌=А₁₂=А₁₃=А₁₄=

А₁₅=А₁₆=

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

Z=273.3*x₁+126*x₂+277.2*x₃+123.2*x₄+129.5*x₅+63*x₆+126*x₇+67.2*x₈+261.8 *x₉+ 115.5* x₁₀+ 241.5* x₁₁ +112*x₁₂ +0*x₁₃+0*x₁₄+0*x₁₅+0*x₁₆–М*x₁₇ –М*x₁₈–М*x₁₉– max

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

12 x₁+12 x₂+12 x₃+6 x₅+6 x₆+6 x₇+11 x₉+11 x₁₀+11 x₁₁+x₁₃=600;

12 x₃ +5 x₇+10 x₁₁+x₁₄ =750;

11 x₄+6 x₈+10x₁₂+x₁₅ =600;

11 x₁+ 5 x₅ +11 x₉ +x₁₆=750;

50 x₁ +28 x₂+ 46 x₃+34x₄+x₁₇ = 1095

43 x₅ +24 x₆+ 35 x₇+24x₈+x₁₈ = 1825

42 x₉ +23 x₁₀+ 35 x₁₁+23x₁₂+x₁₉ = 1825

x_1-19 0

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

А₁₃=А₁₄=А₁₅=А₁₆=А₁₇=А₁₇=А₁₈=А₁₉=

В=

Вычислим значение базисных переменных.

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

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₁₃=600; x₁₄=750; x₁₅=600; x₁₆=750; x₁₇=1095; x₁₈=1825; x₁₉=1825).

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

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

Строка	Базис	Сб	В		273,3		126		277,2		123,2		129,5		63		126		67,2		261,8		115,5		241,5		112		0		0		0		0		-М		-М		-М
					x1		x2		x3		x4		x5		x6		x7		x8		x9		x10		x11		x12		x13		x14		x15		x16		x17		x18		x19
1	Х13	0	600		12		12		12		0		6		6		6		12		11		11		22		0		1		0		0		0		0		0		0
2	Х14	0	750		0		0		12		0		0		0		5		0		0		10		20		0		0		1		0		0		0		0		0
3	Х15	0	600		0		0		0		11		0		0		0		0		0		0		0		10		0		0		1		0		0		0		0
4	Х16	0	750		11		0		0		0		5		0		0		11		11		0		0		0		0		0		0		1		0		0		0
5	Х17	-M	1095		50		28		46		34		0		0		0		50		0		0		0		0		0		0		0		0		1		0		0
6	Х18	-M	1825		0		0		0		0		43		24		35		0		0		0		0		0		0		0		0		0		0		1		0
7	Х19	-М	1825		0		0		0		0		0		0		0		0		42		35		35		23		0		0		0		0		0		0		1
m+1	Zj -Cj			0		-273,3		-126		-277,2		-123,2		-129,5		-63		-126		-67,2		-261,8		-115,5		-241,5		-112		0		0		0		0		0		0		0
m+2				-4745		-50		-28		-46		-34		-43		-24		-35		-50		-42		-35		-35		-23		0		0		0		0		0		0		0

План в табл. 3.2 неоптимальный, так как есть отрицательные оценки, а задача на максимум. Оптимальный план находим с помощью MS Excel

Excel – это широко распространенная компьютерная программа. Нужна она для проведения расчетов, составления таблиц и диаграмм, вычисления простых и сложных функций. Она входит в состав пакета Microsoft Office.

Это такой набор программ для работы в офисе. Самые популярные приложения в нем - Word и Excel.

Excel (эксель) – это что-то вроде калькулятора с множеством функций и возможностей. В этой программе можно составлять отчеты, производить вычисления любой сложности, составлять диаграммы. Нужна она, в первую очередь, бухгалтерам и экономистом.

Ценной возможностью Excel является возможность писать код на основе Visual Basic для приложений. Этот код пишется с использованием отдельного от таблиц редактора. Управление электронной таблицей осуществляется посредством объектно-ориентированной модели кода и данных. С помощью этого кода данные входных таблиц будут мгновенно обрабатываться и отображаться в таблицах и диаграммах (графиках). Таблица становится интерфейсом кода, позволяя легко работать изменять его и управлять расчётами.

Для того чтобы решить задачу ЛП в табличном процессоре Microsoft Excel необходимо выполнить следующие действия:

1. Ввести условие задачи:

a) создать экранную форму для ввода условия задачи:

· переменных,

· целевой функции (ЦФ),

· ограничений,

· граничных условий;

b) ввести исходные данные в экранную форму:

· коэффициенты ЦФ,

· коэффициенты при переменных в ограничениях,

· правые части ограничений;

c) ввести зависимости из математической модели в экранную форму:

· формулу для расчета ЦФ,

· формулы для расчета значений левых частей ограничений;

d) задать ЦФ (в окне "Поиск решения"):

· целевую ячейку,

· направление оптимизации ЦФ;

e) ввести ограничения и граничные условия (в окне "Поиск решения"):

· ячейки со значениями переменных,

· граничные условия для допустимых значений переменных,

· соотношения между правыми и левыми частями ограничений.

2. Решить задачу:

a) установить параметры решения задачи (в окне "Поиск решения");

b) запустить задачу на решение (в окне "Поиск решения");

c) выбрать формат вывода решения (в окне "Результаты поиска решения").

Введя все ограничения, получаем оптимальный план задачи:

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

х₁= х₁₁=0

х₂= х₁₂=0

х₃= х₁₃=0

х₄= х₁₄=32,21

х₅= х₂₁=19,58

х₆= х₂₂=0

х₇= х₂₃=0

х₈= х₂₄=40,96

х₉= х₃₁=0

х₁₀= х₃₂=0

х₁₁= х₃₃=43,86

х₁₂= х₃₄=0

Z_max=19849,11

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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