Математическое моделирование производственных систем

Курсовая работа

Математическое моделирование производственных систем

Индивидуальное задание на курсовую работу

Дано: Комплекс, состоящий из восьми работ, порядок выполнения которых определяется сетевым графиком.

По работам сетевого графика установлены следующие значения характеристик

Порядковый № работы Характеристики	1	2	3	4	5	6	7	8
ak	40	25	40	15	20	40	15	20
bk	-4	-5	-2	-3	-4	-1	-2	-3
dk	2	1	2	4	2	1	4	3
Dk	3	5	9	7	6	4	8	10

Введение

Главной целью данной курсовой работы является закрепление, понимание и обобщение знаний, полученных в результате изучения курса “Математические методы в управлении”.

Ряд задач производства связан с проектированием производственных систем, с определением оптимальных значений характеристик производственных процессов. Включая в себя значительный перечень взаимосвязанных элементов, производственные системы представляют собой объекты, требующие использования различных математических аппаратов при их исследовании.

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

. сетевые модели в управлении;

. параметрическое программирование;

. принцип двойственности;

. симплексный метод;

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

Курсовая работа состоит из трех частей: теоретическая часть, расчетная часть и графическая часть.

Расчетная часть включает в себя:

. “Минимизация затрат на выполнение комплекса работ при заданном времени”;

. “Минимизация времени выполнения комплекса работ при заданных затратах”;

. “Минимизация суммарных затрат по комплексу работ и объекту”;

Графическая часть курсовой работы включает:

. графики линейных зависимостей затрат по работам от продолжительности работ;

. график линейной зависимости затрат по комплексу работ от продолжительности выполнения комплекса для каждого частного интервала времени T.

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

 

1.Теоретическая часть

1.1 Математические методы линейного программирования в сетевой системе

математический программирование производственный

При решении задач определения оптимального соотношения затрат на выполнение производственного процесса и их продолжительности сталкиваются с тем, что процесс представляет собой комплекс взаимоувязанных работ. В этом случае задача может быть сведена к оптимизации графа (сетевого графика), описывающего данный комплекс работ, с использованием минимума времени или минимума затрат. При этом в качестве основного оптимизирующего аппарата можно использовать аппараты линейного программирования. Для применения аппарата линейного программирования при оптимизации сетевых графиков необходимо выполнение следующих условий:

1.      По каждой работе сетевого графика устанавливается сетевая зависимость затрат на выполнение работы от ее продолжительности:

C_k = a_{k +} b_k t_k (1)

где C_k - затраты на выполнение к-й работы;

t_k - время выполнения к-й работы;

a_k, b_k - константы линейной функции.

2.      Продолжительность выполнения каждой работы ограничена

d_k  t_k  D_k (2)

где d_k, D_k - экстремальные значения t_k.

При решении практических задач значения d_k, D_k должны отвечать следующим условиям:

d_k >0; D_k <  (3)

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

Второе условие определяется необходимостью выполнения комплекса работ в реальные сроки.

На основании условия (2) продолжительность выполнения комплекса работ ограничена заданными интервалами

T_min T T_max (4)

где T_max - продолжительность выполнения комплекса работ при условии t_k=D_k;

T_min - продолжительность выполнения комплекса работ при условии t_k=d_k (равна величине критического пути сетевого графика).

Затраты на выполнение комплекса работ также ограничены

S_min  S S_max (5)

где S_max- затраты на выполнение комплекса работ при условии t_k=d_k, т. е.

S_max =           (6)

S_min - затраты на выполнение комплекса работ при условии t_k=D_k, т. е.

S_min =  (7)

В зависимости от используемых критериев оптимальности данную задачу можно представить как:

а) минимизацию затрат на выполнение комплекса работ при заданном времени;

б) минимизацию времени выполнения комплекса работ при заданных затратах;

в) минимизацию суммарных затрат по комплексу работ и объекту.

Рассмотрим три части курсового проекта:

1.2.1 Минимизация затрат на выполнение комплекса работ при заданном времени

Условные задачи следующие: директивно задано предельное время выполнения комплекса работ. Необходимо определить продолжительность работ, при которых затраты на выполнение комплекса будут минимально возможными, а время выполнения комплекса не превысит директивного времени.

Формализованная структура задачи следующая:

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

        (8)

Преобразуем целевую функцию

(9)

В связи с тем, что первая часть целевой функции фиксирована,

    (10)

Целевую функцию можно свести к следующему виду:

(11)

Система ограничений состоит из следующих подсистем:

а) t_k  d_k (12)

б) t_k  D_k (13)

Число выражений в каждой из этих подсистем совпадает с числом действительных работ N_раб.

в)  (14)

где - булева переменная;

, если k-я работа входит в 1-й полный путь

, если k-я работа не входит в 1-й полный путь

Каждое выражение данной подсистемы ограничений определяет максимальную продолжительность каждого полного пути сетевого графика. Число выражений совпадает с числом полных путей.

В связи с тем, что одним из общих ограничений задач линейного программирования является X 0, в рассмотренной задаче необходимо ввести новые переменные, отвечающие этому требованию, т. е.

 (15)

С учетом введения новых переменных система ограничений примет вид:

а)  (16)

б)  (17)

в)  1=1,  (18)

В связи с введением новых переменных целевая функция примет вид:

 (19)

Преобразуем полученную целевую функцию:

 (20)

Но вторая часть функции константа, т. е.

                              (21)

Тогда целевая функция примет вид:

  (22)

Для дальнейших расчетов в качестве целевой функции будет использоваться выражение:

 (23)

где

Если рассмотреть структуру полученной задачи линейного программирования, то выяснится, что это вторая частная параметрическая задача. В системе ограничения в составе свободного члена используется параметр T, предел изменения которого определен выражением (4).

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

 (24)

Система ограничений:

 (25)

где- булева переменная:

, если входит в к-е ограничение (26)

, если не входит в к-е ограничение

Справедливо соотношение (для оптимальных планов прямой и двойственной задачи):

Двойственно-сопряженная задача на максимум. Перейдем от задачи на минимум к задаче на максимум. Для этого умножим целевую функцию (24) на -1.

Получим:

 (27)

для которой

Решение двойственной задачи позволяет установить:

a) деление исходного интервала изменения T (4) на частные интервалы, в пределах которых оптимальное значение будет постоянным;

b) значение для каждого частного интервала;

c) линейный вид целевой функции от T для каждого частного интервала, устанавливающий зависимость минимальных затрат на выполнение комплексных работ от T

 (28)

где A_i, B_i - коэффициент линейной функции для i-го частного интервала.

Используя выражение (28), можно определить значение минимальных затрат, соответствующих T_д.

Для этого достаточно:

а) определить частный интервал изменения T, в который попадает T_д,

где ,  - границы i-го частного интервала.

Это, в свою очередь, позволяет определить значения A_i и B_i.

б) подставить значения T_д в выражение (28), т. е.

 

.2.2 Минимизация времени выполнения комплекса работ при заданных затратах

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

Для решения данной задачи можно использовать алгоритм решения параметрической задачи «Минимизация затрат на выполнение комплекса работ при заданном времени выполнения». Схема выполнения данной задачи следующая:

а) решается задача минимизации затрат на выполнение комплекса работ, в результате чего устанавливают:

-        частный интервал времени T;

-        значение неизвестных для каждого частного интервала;

         вид целевой функции от T.

б) определяются граничные значения затрат для каждого частного интервала, т. е. :

где A_i, B_i - показатели целевой функции основной задачи,

в) определяется частный интервал, в который попадет заданное значение;

г) определяется минимальное время выполнения комплекса работ:

 (29)

1.2.3 Минимизация суммарных затрат по комплексу работ и объекту

Условие задачи следующее: необходимо определить продолжительность работ, при которых сумма затрат на выполнение комплекса и затраты по объекту будут минимальны.

Пример: комплекс работ - подразделение системы комплексного обслуживания, объект - судно.

Для решения данной задачи можно использовать алгоритм решения параметрической задачи «Минимизация затрат на выполнение комплекса работ при заданном времени».

Схема решения задачи минимизации суммарных затрат по комплексу работ и объекту следующая:

а) решается параметрическая задача минимизации затрат по комплексу работ при заданном времени, в результате чего устанавливаются:

-        частные интервалы изменения T;

-        значения неизвестных для каждого частного интервала;

         вид целевой функции минимизации затрат на выполнение комплекса работ от T;

б) формируется вид целевой функции минимизации затрат на выполнение комплекса работ и по объекту.

Z_сум=Z_ком + Z_об,

где Z_сум - значение целевой функции минимизации суммарных затрат;

Z_ком - значение целевой функции минимизации затрат по комплексу работ;

Z_об - значение затрат по объекту за время выполнения комплекса

Поиск минимального значения суммарных затрат сводится к определенеию:

а) частного интервала, в пределах которого Z_сум принимает минимальное значение.

б) значения T, при котором Z_сум принимает минимальное значение.

1.3 Условные обозначения в формулах экономико-математической модели

C_k - затраты на выполнение к-й работы сетевого графика;

t_k- время выполнения к-й работы;

a_k, b_k - коэффициент линейной зависимости затрат от времени;

d_k, D_k - соответственно минимальное и максимальное время выполнения к-й работы;

T - планируемое время выполнения всего комплекса работ;

T_min, T_max - соответственно минимальное и максимальное возможные значения времени выполнения комплекса работ;

S_min, S_max - соответственно минимально и максимально возможные значения затрат на выполнение комплекса работ;

N_раб - число работ, включаемых в комплекс;

 - булева переменная, имеющая значения 0 или 1;

N_пут - число полных путей;

 - дополнительная переменная;

y_k - двойственная переменная.

2.Рассчетная часть

.1 Минимизация затрат на выполнение комплекса работ при заданном времени

Выпишем все пути, ведущие из источника в сток сетевого графика, и вычислим минимальную и максимальную продолжительность выполнение комплекса работ.

Путь	Ранний срок	Поздний срок
L1{1;5}	2+2=4	3+6=9
L2{2;6}	1+1=2	5+4=9
L3{3;8}	2+3=5	9+10=19
L4{2;4;5;}	1+4+2=7	5+7+6=18
L5{2;7;8}	1+4+3=8	5+8+10=23
L6{1;4;7;8;}	2+4+4+3=13	3+7+8+10=28
L7{3;7;4;5;}	2+4+4+2=12	9+8+7+6=30
L8{3;7;6}	2+4+1=7	9+8+4=21
L9{1;4;6}	2+4+1=7	3+7+4=14
	Tmin=13	Tmax=30

Таким образом, время выполнения комплекса работ может изменяться в пределах

≤T≤30

Директивное время находим по формуле T_д=(Т_min+Т_max)/2

T_д=(13+30)/2≈22

Построим математическую модель данной задачи.

Строим систему ограничений.

t1≥2	t2≥1	t3≥2	t4≥4	t5≥2	t6≥1	t7≥4	t8≥3
t1≤3	t2≤5	t3≤9	t4≤7	t5≤6	t6≤4	t7≤8	t8≤10

t₁+ t₅≤T

t₂+ t₆≤T

t₃+ t₈≤T

t₂+ t₄+ t₅≤T

t₂+ t₇+ t₈≤T

t₁+ t₄+ t₇+ t₈≤T

t₃+ t₇+ t₄+ t₅≤T

t₃+ t₇+ t₆≤T

t₁+ t₄+ t₆≤T

t1-2≥0

t2-1≥0

t3-2≥0

t4-4≥0

t5-2≥0

t6-1≥0

t7-4≥0

t8-3≥0

Введем новые переменные, связанные с базовыми следующим образом:

ф₁ = t₁- 2 ф₂ = t₂ - 1 ф₃ =t₃ - 2 ф₄ =t₄ - 4 ф₅ =t₅ - 2 ф₆ =t₆ - 1 ф₇ = t₇ - 4 ф₈ = t₈ - 3

Это приведет к тому, что ф_k≥0

Система ограничений имеет следующий вид:

t₁ =ф₁+2 t₂ =ф₂+1 t₃ =ф₃+2 t₄ =ф₄+4 t₅=ф₅+2 t₆ =ф₆+1 t₇= ф₇+4 t₈ = ф₈+3

ф1+2 ≤3

ф2+1≤5

ф3+2≤9

ф4 +4≤7

ф5+2≤6

ф6+1≤4

ф7+4 ≤8

ф8+3≤10

ф₁+2+ ф₅+2≤T

ф₂+1+ ф₆+1≤T

ф₃+2+ ф₈+3≤T

ф₂+1+ ф₄+4+ ф₅+2≤T

ф₂+1 + ф₇+4+ ф₈+3≤T

ф₁+2+ ф₄+4+ ф₇+4+ ф₈+3≤T

ф₃+2+ ф₇+4+ ф₄+4+ ф₅+2≤T

ф₃+2+ ф₇+4+ ф₆+1≤T

ф₁+2+ ф₄+4+ ф₆+1≤T

ф1 ≤1

ф2≤4

ф3≤7

ф4 ≤3

ф5≤4

ф6≤3

ф7 ≤4

ф8≤7

преобразований система ограничений примет вид:

ф₁+ ф₅≤T-4

ф₂+ ф₆≤T-2

ф₃+ ф₈≤T-5

ф₂+ ф₄+ ф₅≤T-7

ф₂+ф₇+ ф₈≤T-8

ф₁+ф₄+ ф₇+ ф₈≤T-13

ф₃+ ф₇+ ф₄+ ф₅≤T-12

ф₃+ ф₇+ ф₆≤T-7

ф₁+ ф₄+ ф₆≤T-7

Строим целевую функцию.

Целевая функция при основных переменных имеет вид

Z=215- 4t₁-5 t₂ - 2t₃- 3t₄- 4t₅- 1t₆- 2t₇- 3t₈→ min

При замене t_k на ф_k получим

Z=215- 4(ф₁+2)-5 (ф₂+1) - 2(ф₃+2)- 3(ф₄+4)- 4(ф₅+2)- 1(ф₆+1)- 2(ф₇+4)- 3(ф₈+3)→ min

или

Z=160- 4ф₁-5 ф₂-2ф₃- 3ф₄- 4ф₅- ф₆- 2ф₇- 3ф₈→ min

Z’= 4ф₁+5 ф₂+2ф₃+3ф₄+4ф₅+ ф₆+ 2ф₇+ 3ф₈ → max

Представим исходную задачу в матричной форме

	-ф1	-ф2	-ф3	-ф4	-ф5	-ф6	-ф7	-ф8	b
y1	1								1
y2		1							4
y3			1						7
y4				1
y5					1				4
y6						1			3
y7							1		4
y8								1	7
y9	1				1				T-4
y10		1				1			T-2
y11			1					1	T-5
y12		1		1	1				T-7
y13		1					1	1	T-8
y14	1			1			1	1	T-13
y15			1	1	1		1		T-12
y16			1			1	1		T-7
y17	1			1		1			T-7
Z’	-4	-5	-2	-3	-4	-1	-2	-3	0

max

Составим двойственную сопряженную задачу

	-y1	-y2	-y3	-y4	-y5	-y6	-y7	-y8	-y9	-y10	-y11	-y12	-y13	-y14	-y15	-y16	-y17	b
ф1	-1								-1					-1			-1	-4
ф2		-1								-1		-1	-1					-5
ф3			-1								-1				-1	-1		-2
ф4				-1								-1		-1	-1		-1	-3
ф5					-1				-1			-1			-1			-4
ф6						-1				-1						-1	-1	-1
ф7							-1						-1	-1	-1	-1		-2
ф8								-1			-1		-1	-1				-3
Z’дв	-1	-4	-7	-3	-4	-3	-4	-7	4-T	2-T	5-T	7-T	8-T	13-T	12-T	7-T	7-T	0

min

Перейдем от задачи на минимум к задаче на максимум. Для этого целевую функцию умножим на -1.

	-y1	-y2	-y3	-y4	-y5	-y6	-y7	-y8	-y9	-y10	-y11	-y12	-y13	-y14	-y15	-y16	-y17	b
ф1	-1								-1					-1			-1	-4
ф2		-1								-1		-1	-1					-5
ф3			-1								-1				-1	-1		-2
ф4				-1								-1		-1	-1		-1	-3
ф5					-1				-1			-1			-1			-4
ф6						-1				-1						-1	-1	-1
ф7							-1						-1	-1	-1	-1		-2
ф8								-1			-1		-1	-1				-3
Zдв	1	4	7	3	4	3	4	7	T-4	T-2	T-5	T-7	T-8	T-13	T-12	T-7	T-7	0

max

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

I шаг. Выбираем ведущими 1-ю строку и 1-й столбец (табл.4) и произведем пересчёт элементов, использую правило пересчёта симплексного метода. Получим:

II шаг. Выберем ведущими 2-ю строку и 2-й столбец и произведем пересчет элементов. Получим:

	- ф 1	- ф 2	-y3	-y4	-y5	-y6	-y7	-y8	-y9	-y10	-y11	-y12	-y13	-y14	-y15	-y16	-y17	b
y1	-1								1					1			1	4
y2		-1								1		1	1					5
ф3			-1								-1				-1	-1		-2
ф4				-1								-1		-1	-1		-1	-3
ф5					-1				-1			-1			-1			-4
ф6						-1				-1						-1	-1	-1
ф7							-1						-1	-1	-1	-1		-2
ф8								-1			-1		-1	-1				-3
Zдв	1	4	7	3	4	3	4	7	T-5	T-6	T-5	T-11	T-12	T-14	T-12	T-7	T-8	-24

max

III шаг. Выберем ведущими 3-ю строку и 3-й столбец и произведем пересчет элементов.

	- ф 1	- ф 2	- ф3	-y4	-y5	-y6	-y7	-y8	-y9	-y10	-y11	-y12	-y14	-y15	-y16	-y17	b
y1	-1								1					1			1	4
y2		-1								1		1	1					5
y3			-1								1				1	1		2
ф4				-1								-1		-1	-1		-1	-3
ф5					-1				-1			-1			-1			-4
ф6						-1				-1						-1	-1	-1
ф7							-1						-1	-1	-1	-1		-2
ф8								-1			-1		-1	-1				-3
Zдв	1	4	7	3	4	3	4	7	T-5	T-6	T-12	T-11	T-12	T-14	T-19	T-14	T-8	-38

max

IV шаг. Выберем ведущими 4-ю строку и 4-й столбец и произведем пересчет элементов.

Получим:

	- ф 1	- ф 2	- ф3	- ф4	-y5	-y6	-y7	-y8	-y9	-y10	-y11	-y12	-y13	-y14	-y15	-y16	-y17	b
y1	-1								1					1			1	4
y2		-1								1		1	1					5
y3			-1								1				1	1		2
y4				-1								1		1	1		1	3
ф5					-1				-1			-1			-1			-4
ф6						-1				-1						-1	-1	-1
ф7							-1						-1	-1	-1	-1		-2
ф8								-1			-1		-1	-1				-3
Zдв	1	4	7	3	4	3	4	7	T-5	T-6	T-12	T-14	T-12	T-17	T-22	T-14	T-11	-47

Max

V шаг. Выберем ведущими 5-ю строку и 5-й столбец и произведем пересчет элементов.

Получим:

	- ф 1	- ф 2	- ф3	- ф4	- ф 5	-y6	-y7	-y8	-y9	-y10	-y11	-y12	-y13	-y14	-y15	-y16	-y17	b
y1	-1								1					1			1	4
y2		-1								1		1	1					5
y3			-1								1				1	1		2
y4				-1								1		1	1		1	3
y5					-1				1			1			1			4
ф6						-1				-1						-1	-1	-1
ф7							-1						-1	-1	-1	-1		-2
ф8								-1			-1		-1	-1				-3
Zдв	1	4	7	3	4	3	4	7	T-9	T-6	T-12	T-18	T-12	T-17	T-26	T-14	T-11	-63

max

VI шаг. Выберем ведущими 6-ю строку и 6-й столбец и произведем пересчет элементов.

Получим:

	- ф 1	- ф 2	- ф3	- ф4	- ф 5	- ф 6	-y7	-y8	-y9	-y10	-y11	-y12	-y13	-y14	-y15	-y16	-y17	b
y1	-1								1					1			1	4
y2		-1								1		1	1					5
y3			-1								1				1	1		2
y4				-1								1		1	1		1	3
y5					-1				1			1			1			4
y 6						-1				1						1	1	1
ф 7							-1						-1	-1	-1	-1		-2
ф8								-1			-1		-1	-1				-3
Zдв	1	4	7	3	4	3	4	7	T-9	T-9	T-12	T-18	T-12	T-17	T-26	T-17	T-14	-66

Max

VII шаг. Выберем ведущими 7-ю строку и 7-й столбец и произведем пересчет элементов.

Получим:

	- ф 1	- ф 2	- ф3	- ф 5	- ф 6	- ф 7	-y8	-y9	-y10	-y11	-y12	-y13	-y14	-y15	-y16	-y17	b
y1	-1								1					1			1	4
y2		-1								1		1	1					5
y3			-1								1				1	1		2
y4				-1								1		1	1		1	3
y5					-1				1			1			1			4
y 6						-1				1						1	1	1
y7							-1						1	1	1	1		2
ф8								-1			-1		-1	-1				-3
Zдв	1	4	7	3	4	3	4	7	T-9	T-9	T-12	T-18	T-16	T-21	T-30	T-21	T-14	-74

max

VIII шаг. Выберем ведущими 8-ю строку и 8-й столбец и произведем пересчет элементов.

Получим:

	- ф 1	- ф 2	- ф3	- ф4	- ф 5	- ф 6	- ф 7	- ф 8	-y9	-y10	-y11	-y12	-y13	-y14	-y15	-y16	-y17	b
y1	-1								1					1			1	4
y2		-1								1		1	1					5
y3			-1								1				1	1		2
y4				-1								1		1	1		1	3
y5					-1				1			1			1			4
y 6						-1				1						1	1	1
y7							-1						1	1	1	1		2
y8								-1			1		1	1				3
Zдв	1	4	7	3	4	3	4	7	T-9	T-9	T-19	T-18	T-23	T-28	T-30	T-21	T-14	-95

Max

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

Проверим правильность заполнения. В опорном плане, соответствующем таблице

y₁ = 4, y₂ = 5, y₃ = 2, y₄ = 3, y₅ = 4, y₆ = 1, y₇ = 2, y₈ = 3. Остальные переменные равны 0.

Подставляя значения переменных в выражение для Z_дв, получим:

Z_дв = -14 - 45 - 72 - 33 - 44 - 31 - 42 - 73= -95

Таким образом, изменение целевой функции найдено правильно.

Полученный план оптимален (элементы заключительной строки и элементы заключительного столбца больше 0), при T ≥ 30. В противном случае 15-й элемент заключительной строки будет отрицателен. Но так как предел изменения задан

≤ T ≤ 30

то план оптимален при Т = 30.

При этом значение целевой функции равно -95. Основные переменные имеют следующие значения:

ф₁ = 1 ф₂ =4 ф₃ =7 ф₄ =3 ф₅ =4 ф₆ =3 ф₇ =4 ф₈ =7

То есть получаем значения ф_k, которые приравниваются к k-м элементам заключительной строки. правомерность этого обуславливается принципом двойственности. Так как полученный план при T = 29 оптимален, значение целевой функции основной задачи совпадает со значение целевой функции двойственной задачи, т.е.

Z’ = Z’_дв = -Z_дв = -95

Значение исходной целевой функции будет равно

Z = A + B + Z_дв =65 , где A + B = 160

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

30 ≤ T ≤ ∞

обязательно совпадет с максимальной границей времени выполнения комплекса работ

T_max = 30

Однако если значение T сократить (присвоить значение менее 30), то 15-й элемент заключительной строчки станет меньше 0. Выберем заданный столбец ведущим, а ведущая строка определится по минимуму из отношений b_i / a_ij , т.е. ведущей получим 3-ю строчку.

Произведем пересечение элементов матрицы. Получим:

	- ф 1	- ф 2	- ф3	- ф4	- ф 5	- ф 6	- ф 7	- ф 8	-y9	-y10	-y11	-y12	-y13	-y14	-y3	-y16	-y17	b
y1	-1								1					1			1	4
y2		-1								1		1	1					5
y15			-1								1				1	1		2
y4			1	-1							-1	1		1	-1	-1	1	1
y5			1		-1				1		-1	1			-1	-1		2
y 6						-1				1						1	1	1
y7			1				-1				-1		1	1	-1
y8								-1			1		1	1				3
Zдв	1	4	T-23	3	4	3	4	7	T-9	T-9	11	T-18	T-23	T-28	30-T	7	T-14	-35-2T

max

Полученный план будет оптимален при 28≤Т≤30. Значение целевой функции двойственной задачи в зависимости от значения T будет определяться по формуле:

Z_дв=-35-2T

Z= 160-35-2T = 125-2T

При этом основные и исходные переменные примут следующие значения:

=1, =4, =Т-23, =3, =4, =3, =4, =7;

t₁= 3; t₂=5; t₃= Т-21; t₄= 7; t₅=6; t₆= 4; t₇=8; t₈=10;

Если значение Т будет меньше 28, то 14-й элемент заключительной строчки будет отрицательным. Поэтому выберем 14-й столбец ведущим столбцом и 7-ю строку ведущей строкой и произведем пересчет элементов.

Получим:

	- ф 1	- ф 2	- ф3	- ф4	- ф 5	- ф 6	- ф 7	- ф 8	-y9	-y10	-y11	-y12	-y13	-y7	-y3	-y16	-y17	b
y1	-1		-1				1		1		1		-1	-1	1		1	4
y2		-1								1		1	1					5
y15			-1								1				1	1		2
y4				-1			1					1	-1	-1		-1	1	1
y5			1		-1		-1	1			-1	-1		2
y 6						-1				1						1	1	1
y14			1				-1				-1		1	1	-1
y8			-1				1	-1			2			-1	1			3
Zдв	1	4	5	3	4	3	T-24	7	T-9	T-9	T-17	T-18	5	28 -T	2	7	T-14	-35-2T

max

Полученный план будет оптимален при 24≤Т≤28. Значение целевой функции двойственной задачи в зависимости от значения T будет определяться по формуле:

Z_дв=-35-2T

Z= 160-35-2T = 125-2T

При этом основные и исходные переменные примут следующие значения:

=1, =4, =5, =3, =4, =3, =Т-24, =7;

t₁= 3; t₂=5; t₃= 7; t₄= 7; t₅=6; t₆= 4; t₇= Т-20; t₈=10;

Если значение Т будет меньше 24, то 7-й элемент заключительной строчки будет отрицательным. Поэтому выберем 7-й столбец ведущим столбцом и 4-ю строку ведущей строкой и произведем пересчет элементов.

	- ф 1	- ф 2	- ф3	- ф4	- ф 5	- ф 6	- y4	- ф 8	-y9	-y10	-y11	-y12	-y13	-y7	-y3	-y16	-y17	b
y1	-1		-1	1			-1		1		1	-1			1	1		3
y2		-1								1		1	1					5
y15			-1								1				1	1		2
ф 7				-1			1					1	-1	-1		-1	1	1
y5			1		-1				1		-1	1			-1	-1		2
y 6						-1				1						1	1	1
y14			1	-1			1				-1	1			-1	-1	1	1
y8			-1	1			-1	-1			2	-1	1		1	1	-1	2
Zдв	1	4	5	T-21	4	3	24-T	7	T-9	T-9	T-17	6	T-19	4	2	T-17	10	-11-3T

max

Полученный план будет оптимален при 21≤Т≤24. Значение целевой функции двойственной задачи в зависимости от значения T будет определяться по формуле:

Z_дв=-11-3T

Z= 160-11-3T = 149-3T

При этом основные и исходные переменные примут следующие значения:

=1, =4, =5, =Т-21, =4, =3, =0, =7;

t₁= 3; t₂=5; t₃= 7; t₄= Т-17; t₅=6; t₆= 4; t₇= 4; t₈=10;

Если значение Т будет меньше 21, то 4-й элемент заключительной строчки будет отрицательным. Поэтому выберем 4-й столбец ведущим столбцом и 8-ю строку ведущей строкой и произведем пересчет элементов.

	- ф 1	- ф 2	- ф3	-y8	- ф 5	- ф 6	- y4	- ф 8	-y9	-y10	-y11	-y12	-y13	-y7	-y3	-y16	-y17	b
y1	-1			-1				1	1				-1				1	1
y2		-1								1		1	1					5
y15			-1								1				1	1		2
ф 7			-1	1				-1			2			-1	1			3
y5			1		-1				1		-1	1			-1	-1		2
y 6						-1				1						1	1	1
y14				1				-1			1		1					3
ф4			-1	1			1	-1			2	-1	1		1	1	-1	2
Zдв	1	4	T-16	21-T	4	3	3	T-14	T-9	T-9	25-T	T-15	2	4	23-T	4	T-11	31-5T

max

Полученный план будет оптимален при 16≤Т≤21. Значение целевой функции двойственной задачи в зависимости от значения T будет определяться по формуле:

Z_дв=31-5T

Z= 160+31-5T = 191-5T

При этом основные и исходные переменные примут следующие значения:

=1, =4, =Т-16, =0, =4, =3, =0, =Т-14;

t₁= 3; t₂=5; t₃= Т-14; t₄= 4; t₅=6; t₆= 4; t₇=4; t₈=Т-11;

Если значение Т будет меньше 16, то 3-й элемент заключительной строчки будет отрицательным. Поэтому выберем 3-й столбец ведущим столбцом и 5-ю строку ведущей строкой и произведем пересчет элементов.

Получим:

	- ф 1	- ф 2	- y5	-y8	- ф 5	- ф 6	- y4	- ф 8	-y9	-y10	-y11	-y12	-y13	-y7	-y3	-y16	-y17	b
y1	-1			-1				1	1				-1					1
y2		-1								1		1	1					5
y15			1		-1				1			1						4
ф 7			1	1	-1			-1	1		-1	1		-1		-1	1	5
ф 3			1		-1				1		-1	1			-1	-1		2
y 6						-1				1						1	1	1
y14				1				-1					1				1	3
ф4			1	1	-1		1	-1		1		1				1	4
Zдв	1	4	16-T	21-T	T-12	3	3	T-14	7	T-9	11	1	2	4	7	T-12	T-11	63-7T

max

max

Полученный план будет оптимален при 14≤Т≤16. Значение целевой функции двойственной задачи в зависимости от значения T будет определяться по формуле:

Z_дв=63-7T

Z= 160+63-7T = 223-7T

При этом основные и исходные переменные примут следующие значения:

=1, =4, =0, =0, =Т-12, =3, =0, =Т-14;

t₁= 3; t₂=5; t₃= 2; t₄= 4; t₅=Т-10; t₆= 4; t₇=4; t₈=Т-11;

Если значение Т будет меньше 14, то 8-й элемент заключительной строчки будет отрицательным. Поэтому выберем 8-й столбец ведущим столбцом и 1-ю строку ведущей строкой и произведем пересчет элементов.

Получим:

	- ф 1	- ф 2	- y5	-y8	- ф 5	- ф 6	- y4	- y1	-y9	-y10	-y11	-y12	-y13	-y7	-y3	-y16	-y17	b
ф 8	-1			-1				1	1				-1					1
y2		-1								1		1	1					5
y15			1		-1				1			1						4
ф 7	-1		1		-1			-1	1		-1	1		-1		-1	1	5
ф 3			1		-1				1		-1	1			-1	-1		2
y 6						-1				1						1	1	1
y14	-1							-1					1				1	3
ф4	-1		1		-1		1	-1	1		1		1				1	4
Zдв	T-13	4	16-T	7	T-12	3	3	14-T	21-T	T-9	11	1	T-12	4	7	T-12	3	77-8T

max

Полученный план будет оптимален при 13≤Т≤14. Значение целевой функции двойственной задачи в зависимости от значения T будет определяться по формуле:

Z_дв=77-8T

Z= 160+77-8T = 237-8T

При этом основные и исходные переменные примут следующие значения:

=Т-13, =4, =0, =0, =Т-12, =3, =0, =0;

t₁= Т-11; t₂=5; t₃= 2; t₄= 4; t₅=Т-10; t₆= 4; t₇=4; t₈=3;

Таким образом, весь интервал изменения 13≤Т≤30 разбивается на 6 составляющих частных интервала

)        28≤Т≤30;

)        24≤Т≤28;

)        21≤Т≤24;

)        16≤Т≤21;

)        14≤Т≤16;

)        13≤Т≤14;

В условии задачи дано: Т=22. Это значит, что будем рассматривать третий интервал

≤Т≤24

Оптимальное значение неизвестных равно

t₁= 3; t₂=5; t₃= 7; t₄= 22-17=5; t₅=6; t₆= 4; t₇= 4; t₈=10;

Значение минимальных затрат будет рассчитываться по формуле:

Z= 149-3T=83

2.2    Минимизация времени выполнения комплекса работ при заданных затрат

Дополнительно дано: директивные затраты равны 39 т.е.

.

Так как задача минимизации затрат на выполнение комплекса работ при заданном времени решена, то приступаем к определению граничных значений затрат для каждого частного интервала.

28≤Т≤30;

≤Т≤28;

≤Т≤24;

≤Т≤21;

≤Т≤16;

≤Т≤14;

Для первого частного интервала формула расчета затрат:

Z= 125-2T

Граница первого частного интервала: 28≤Т≤30

Таким образом, Z ¹ _min =65, Z ¹ _max =69

По аналогии, для второго частного интервала 24 ≤Т ≤28, целевая функция Z=125-2T , а граничные значения затрат Z ² _min =69, Z ² _max =77

По аналогии, для третьего частного интервала 21≤Т≤24, целевая функция

Z=149-3T,

а граничные значения затрат Z ³ _min =77

Z ³ _max =86

По аналогии, для четвертого частного интервала 16 ≤Т ≤21, целевая функция Z=191-5T, а граничные значения затрат Z ⁴ _min =86

Z ⁴ _max =111

По аналогии, для пятого частного интервала 14 T16, целевая функция Z=223-7T , а граничные значения затрат Z ⁵ _min =111

Z ⁵ _max =125

По аналогии, для шестого частного интервала 13 ≤Т ≤14, целевая функция Z=237-8T , а граничные значения затрат Z ⁶ _min =125

Z ⁶ _max =133

Получим следующие частные интервалы для затрат:

1) 65 Z  69

) 69 Z  77

) 77 Z  86

) 86 Z  111

) 111 Z  125

) 125 Z  133

Таким образом, заданные в примере директивные затраты не попадают ни в один интервал.

.3 Минимизация суммарных затрат по комплексу работ и объекту

Дополнительно введем вид затрат по объекту от времени:

Целевая функция суммарных затрат на частных интервала примет вид:

28≤Т≤30, =125-2T +2,5Т=125+0,5Т

≤Т≤28, =125-2T +2,5Т=125+0,5Т

≤Т≤24, =149-3T+2,5Т=149-0,5Т

≤Т≤21, =191-5T+2,5Т=191-2,5Т

≤Т≤16, =223-7T+2,5Т=223-4,5Т

≤Т≤14, =237-8T +2,5Т=237-5,5Т

Анализ общего вида  позволит найти точку минимума.

При изменении 13 T 24 целевая функция  убывает, т.к. коэффициент при Т отрицателен. При изменении 24 T 30 целевая функция Z ^S возрастает, т.к. коэффициент при T положителен. В связи с чем в точке Т = 24 целевая функция  примет минимальное значение, равное

Z^∑_min= 149-0,5х24=137

Значение неизвестных составит:

t₁=13; t₂=5; t₃= 2; t₄= 4; t₅=14; t₆= 4; t₇=4; t₈=3;

3.Графическая часть

Построим график для 1-го интервала: 28≤Т≤30

Построим график для 2-го интервала: 24≤Т≤28

Построим график для 3-го интервала: 21≤Т≤24

Построим график для 4-го интервала: 21≤Т≤16

Построим график для 5-го интервала: 14≤Т≤16

Построим график для 6-го интервала: 14≤Т≤13

Построим общий график:

Заключение

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

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

1)  при минимизации затрат на выполнение комплекса работ при заданном времени, оптимальное значение неизвестных равно:

t₁= 3; t₂=5; t₃= 7; t₄= 22-17=5; t₅=6; t₆= 4; t₇= 4; t₈=10

2)  при минимизации суммарных затрат по комплексу работ и объекту, оптимальное значение неизвестных равно:

t₁=13; t₂=5; t₃= 2; t₄= 4; t₅=14; t₆= 4; t₇=4; t₈=3

Список используемой литературы

1.       Математические методы и модели в управлении на морском транспорте: учебное пособие. Т.Е. Маликова

2.      Математическое моделирование производственных систем: методические указания. Т.Е. Маликова