Відкриті моделі транспортних задач

Введемо позначення: . Якщо не виконується умова А=В, то задачу називають відкритою.

Якщо запаси перевищують потреби, то вводимо фіктивного споживача з потребами . Якщо потреби перевищують запаси, то вводимо фіктивного постачальника з запасами. При цьому вартості перевезень за фіктивними маршрутами вважаємо рівними нулю.

Далі задача розв’язується так само, як і замкнута.

Приклад 3.1. Є два постачальники з запасами та три споживачі з потребами. Матриця вартостей перевезень:

С =

Побудувати план перевезень, що мінімізує їх вартість.

Розв’язання. . Потреби перевищують запаси на 10 одиниць, тому вводимо фіктивного постачальника з запасами рівними 10.

Початковий опорний план має вигляд:

	60	40	80
100	3	5	4
	60	30	10
70	4	6	2
			70
10	0	0	0
		10

Всі оцінки додатні, а значить розв’язок є оптимальним. Оскільки третій постачальник є фіктивним, то виключаємо його з розгляду.

Відповідь.

,

Другий споживач недоотримає 10 одиниць сировини.

Завдання 3. Відомий випуск продукції на трьох заводах ; потреби у цій продукції споживачів ; матриця транспортних витрат на перевезення одиниці продукції з - го заводу до -го споживача .Визначити оптимальний план перевезень за критерієм витрат . Дані задачі наведено в таблиці

Варіант 1

	10	40	20	60	20
30	2	7	3	6	2
70	9	4	5	7	3
50	5	7	6	2	4

Варіант 3

	45	15	20	10	10
25	9	5	3	10	5
55	6	3	8	2	4
20	3	2	11	4	8

Варіант 5

	180	140	190	120	170
300	12	21	9	10	16
280	13	5	11	13	21
220	19	26	12	17	20

Варіант 2

	35	25	40	20	30
20	9	8	2	5	4
90	2	7	8	3	5
40	6	6	3	3	7

Варіант 4

	90	100	70	130	110
200	12	15	21	14	17
150	14	8	15	11	21
150	19	16	26	12	20

Варіант 6

	180	120	90	105	105
250	12	8	21	10	15
200	13	4	15	13	21
150	19	16	26	17	20

Варіант 7

	200	170	230	225	175
400	13	9	5	11	17
250	14	5	12	14	22
350	20	17	13	18	21

Варіант 9.

	170	120	190	140	180
280	28	12	7	18	7
300	35	14	12	15	3
220	30	11	16	25	15

Варіант 11

	300	160	220	180	140
250	9	15	35	20	7
400	15	35	12	11	6
350	16	19	40	15	25

Варіант 13

	190	140	120	180	170
220	20	3	9	15	35
280	14	10	12	20	46
300	25	11	16	19	48

Варіант 8

	160	70	90	80	100
150	8	20	7	11	16
200	4	14	12	15	17
150	15	22	11	12	19

Варіант 10

	180	120	90	105	105
150	14	6	4	9	4
250	17	10	9	11	5
200	15	11	6	13	8

Варіант 12

	100	70	130	110	90
150	15	35	20	9	7
150	15	35	12	11	6
200	16	19	40	15	25

Варіант 14

	120	105	180	105	90
200	7	3	9	15	36
250	3	10	12	46	20
150	15	11	16	19	48

Варіант 15

	120	105	180	105	90
200	7	3	9	15	36
250	3	10	12	46	20
150	15	11	16	19	48

Варіант 17

	120	105	180	105	90
200	7	3	9	15	36
250	3	10	12	46	20
150	15	11	16	19	48

Варіант 19

	120	80	160	80	60
140	10	5	7	4	12
155	7	4	9	10	5
205	16	6	14	8	7

Варіант 21

	400	400	300	250	450
500	3	4	6	1	7
700	5	1	2	3	8
600	4	5	8	1	10

Варіант 16

	110	120	185	95	190
250	5	13	18	17	8
250	6	10	15	6	3
200	24	21	9	16	17

Варіант 18

	30	80	15	25	50
60	8	12	4	9	10
40	7	5	15	3	6
100	9	4	6	12	7

Варіант 20

	120	130	100	160	140
250	27	36	35	31	29
200	22	23	26	32	35
200	35	42	38	32	39

Варіант 22

	20	70	60	50	40
70	70	100	40	80	50
90	90	50	120	60	70
80	40	80	30	90	60

Варіант 23

	100	125	325	250	100
200	5	8	7	10	3
400	4	2	2	5	6
300	7	3	5	9	2

Варіант 25

	210	170	220	150	200
350	3	12	9	1	7
330	2	4	11	2	10
270	7	14	12	5	8

Варіант 27

	170	140	200	195	145
350	22	14	16	28	30
200	19	17	26	36	36
300	37	30	31	39	41

Варіант 29

	140	90	160	110	150
230	40	19	25	25	35
250	49	26	27	18	38
170	46	27	36	40	45

Варіант 24

	120	130	100	160	140
250	27	36	35	31	29
200	22	23	26	32	35
200	35	42	38	32	39

Варіант 26

	210	150	120	135	135
300	4	8	13	2	7
250	9	4	11	9	17
200	3	16	10	1	7

Варіант 28

	140	90	160	110	150
200	28	27	18	27	24
250	18	26	27	32	21
200	27	33	23	31	34

Варіант 30

	210	150	120	135	135
200	20	10	13	13	18
300	27	19	20	16	22
250	26	17	19	21	23

Тема 4. Марковські процеси з дискретними станами та неперервним часом

Означення 4.1. Випадковим процесом на ймовірнісному просторі називається сім’я випадкових величин, що залежить від часового параметра.

Випадковий процес можна трактувати як показник стану динамічної системи, що змінюється у часі під дією випадкових факторів. Якщо стан системи розглядати лише в дискретні моменти часу, то отримаємо випадкову послідовність (випадковий процес з дискретним часом).

Протікання випадкових процесів у часі неможливо передбачити однозначно.

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

Прикладами випадкових процесів є:

1. процес зміни у часі напруги електропостачання локомотива;

2. кількість відмов ЕОМ за час;

3. коливання курсів валют , як функції часу;

4. кількість пасажирів , що обслуговуються касиром за час і т.д.

Якщо в будь-який момент часу ймовірності станів системи в майбутньому залежать лише від її стану в момент і не залежать від того, яким чином вона потрапила в цей стан, то випадковий процес називають марковським.

Означення 4.2. Марковський процес називається процесом з дискретними станами, якщо будь-який його переріз є дискретною випадковою величиною.

Зауважимо, що в більшості прикладних задач досліджувана система може знаходитись в скінченній кількості станів.

Наприклад, телефонна лінія може перебувати в одному з трьох наступних станів: працює (S₁), зайнята (S₂), не працює (S₃). При описанні функціонування залізничної каси можливі наступні стани: каса не працює (S₁), каса вільна (S₂), каса обслуговує пасажира і немає черги (S₃), в черзі один пасажир (S₄), в черзі два пасажира (S₅) і т.д..

На практиці часто виникають ситуації, коли переходи системи із стану в стан відбуваються не у фіксовані, а у випадкові моменти часу, які передбачити неможливо. Для описання таких процесів будемо використовувати схему марковських процесів з дискретними станами і неперервним часом.

Нехай маємо систему з станами. Позначимо через - ймовірність того, що в момент часу система знаходиться в стані . Тоді маємо для будь-якого . Нехай p_ij(t; ∆t) – ймовірність переходу системи із стану s_i в стан s_j в проміжок часу [ t ; t+∆t ].

Означення 4.3. Середньою інтенсивністю переходу системи із стану S_i в стан S_j в проміжок часу [ t ; t+∆t ] будемо називати величину

,

а щільністю ймовірностей переходу (граничною інтенсивністю) в момент -величину

.

Означення 4.4. Марковський процес з дискретними станами називають однорідним, якщо щільності ймовірностей переходу не залежать від t, тобто

λ _ij(t)≡ λ _ij=const.

Надалі розглядатимемо лише однорідні марковські процеси.

Означення 4.5. Матрицею інтенсивностей (або щільностей імовірностей) переходу називається матриця виду

, (4.1)

де елементи головної діагоналі матриці визначаються рівностями

.

Матриця інтенсивностей має такі властивості:

1. Всі її діагональні елементи від’ємні, недіагональні — невід’ємні;

2. Сума елементів кожного рядка дорівнює нулю, звідки слідує, що її стовпчики є лінійно залежними, а значить її визначник дорівнює нулю.

Теорема Колмогорова. Нехай система може знаходитись в станах S_1,..., S_n і процес зміни цих станів є випадковим. Якщо відомі щільності ймовірностей переходів , то ймовірності станів системи задовольняють системі рівнянь

, (4.2)

які називають рівняннями Колмогорова

Зауваження 4.1. Сформулюємо мнемонічне правило побудови системи рівнянь Колмогорова. Похідна від ймовірності стану і дорівнює сумі потоків, що приводять систему в стан мінус сума потоків, що виводять її із цього стану.

Враховуючи (4.1), ми можемо подати систему (4.2) в матричній формі

,

де — вектор імовірностей станів системи, - його похідна:

, .

Нехай нам відомий вектор імовірностей початкових станів системи . Тоді закон розподілу ймовірностей станів системи для довільного моменту часу визначатиметься як розв’язок задачі Коші:

(4.3)

Означення 4.6. Марковський процес з дискретними станами називається ергодичним, якщо існує

,

що не залежить від стану, в якому система знаходилась в початковий момент. Вектор називають вектором граничних або фінальних імовірностей системи, а саму систему – ергодичною.

Існування вектора фінальних імовірностей означає, що через деякий час в системі наступає певний стаціонарний режим, тобто

.

Таким чином, фінальні ймовірності є розв’язком системи лінійних алгебраїчних рівнянь

(4.4)

Зауваження 4.2. Ця система містить n+1 рівнянь та n невідомих. Але враховуючи, що рядки матриці Λ^T — лінійно залежні (див. властивість 2), одне з рівнянь системи можна виключити, після чого вона матиме єдиний розв’язок.

Означення 4.7. Стан S_i є несуттєвим, якщо існує хоча б один стан S_j такий, що з S_i в S_j система може перейти, а з S_j в S_i ні. S_i є суттєвим, якщо він не є несуттєвим.

Означення 4.8. Два суттєвих стани S_i та S_j називаються сполученими, якщо система може перейти із стану S_i в стан S_j і навпаки.

Зауваження 4.3. Враховуючи, що система при виході із несуттєвого стану S_i більше не може повернутись в цей стан, робимо висновок, що фінальна ймовірність цього стану P_i=0 і P_i можна вилучити із (4.4) разом з рівнянням i.

Вектор фінальних імовірностей системи є єдиним, якщо всі її суттєві стани — сполучені.

Для описання системи в неперервному часі розглядають розмічений граф станів. Кружечками позначають стани системи. Стрілками показано напрямки переходу системи з одного стану в інший. Біля стрілок записують відповідні інтенсивності переходів із одного стану в інший.

Приклад 4.1. За заданою матрицею інтенсивностей побудувати граф станів системи, записати рівняння Колмогорова при умові, що в початковий момент часу вона знаходилась в стані S₁ та знайти фінальні ймовірності.

Розв'язання. Оскільки матриця перехідних імовірностей має розмірність 3х3, система може знаходитись в трьох станах: . Система може безпосередньо перейти із станув стан() й із станув(), ці стани сполучені двома протилежно направленими стрілками. Аналогічно, двома протилежно направленими стрілками сполучені станита. Діагональні елементи на графі не зображаються. Тоді розмічений граф станів системи можна представити у вигляді (рис.4.1).

Рис. 4.1