Теорема 3

Теорема 2.

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

Доказ аналогічно доказу теореми 1.

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

Доказ аналогічно доказу теореми 1.

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

– перша фаза розв’язку задачі пов'язана з оптимізацією штучної лінійної форми f. На цьому етапі розв’язку виділяється первісний опорний план. Основна лінійна форма F при цьому поводиться пасивно. Особливість першої фази складається у виключенні із задачі штучних змінних за умови виконання прямо припустимості розв’язку ЗЛП.

– друга фаза розв’язку складається з оптимізації основної лінійної форми F, що на цьому етапі поводиться активно.

Відмітимо, що в розширеній задачі в якості базисних змінних можна приймати й балансові, тобто ті змінні, які з'являються при перетворенні обмежень-нерівностей в обмеження-рівності. У цьому випадку розширена задача називається задачею з неповним штучним базисом.

Різниця між балансовими і штучними змінними полягає в тому, що балансові змінні залишаються й на другому етапі рішення задачі, беручи участь в оптимізації основної лінійної форми F. Штучні ж змінні виводяться із задачі в першій фазі її розв’язку, оскільки вони використовуються лише для виділення первісного опорного плану.

Приклад. Розв’язати задачу лінійного програмування

(42)

(43)

(44)

У кожне обмеження-рівність введемо по однієї штучній змінній. Одержимо розширену задачу

(45)

(46)

Представимо розширену задачу (44)-(46) у вигляді, дозволеному щодо базисних змінних

(48)

(47)

(49)

Далі складемо первісну жорданову таблицю, додавши у звичайну таблицю ще один рядок – рядок штучної лінійної форми f.

		-х1	-х2	-х3	-х4	-х5
ξ1			–1		–2	–6
ξ2				–1			Þ
ξ3		–1			–1
F			–1		–2	–10
f						–3

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

-х2

-х3

-х4

-х5

-х3

-х4

-х5

х1

–1

–2

–6

х1

–9

Þ

ξ2

–3

Þ

х2

–3

–9

:(3)

Þ

ξ3

–3

–6

ξ3

–9

–18

F

–1

F

–6

–3

f

f

–9

–18

			-х3	-х4	-х5				-х4	-х5
	х1				–3		х1			–3
Þ	х2		–1		–3	Þ	х2			–3	:(3) Þ
	ξ3			–3	–6		х3		–3	–6
	F			–2	–1		F		–6	–3
	f			–3	–6		f

			-х4	-х5
	х1			–1
Þ	х2			–1
	х3		–1	–2
	F		–2	–1
	f

З останньої жорданової таблиці видно, що , отже, система обмежень вихідної ЗЛП сумісна. На лівому бордюрі сформувався базис змінних: х ₁, х ₂, х ₃ – базисні, х ₄, х ₅ – вільні змінні. Рядок штучної лінійної форми, що складається з одних нулів, може бути виключений з розгляду.

Таблиця, у якій записаний первісний опорний план, має вигляд

		-х4	-х5
х1			–1
х2			–1
х3		–1	–2
F		–2	–1

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

.

5 Транспортна задача (ТЗ)

ТЗ - задача про найбільш ощадливий (оптимальний) план перевезення однорідного або взаємозамінного продукту з пунктів поставок у пункти споживання.

Постановка задачі. Є m пунктів А₁, А₂,..., А_m, у яких виготовляється або зберігається однорідний або взаємозамінний продукт у кількостях відповідно а₁, а₂,..., а_m. Цей продукт необхідно доставити в n пункти споживання В₁, В₂,..., В_n, де він потрібний відповідно в кількостях в₁, в₂,...в_n. Відомі транспортні витрати (тарифи) c_ij, пов'язані із транспортуванням одиниці продукції з i пункту зберігання в j пункт споживання.

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

Для наочності ТЗ представляють у вигляді таблиці, яка називається розподільною.

Пост.	Споживач	Зап.
В1	В2	В3	В4	Вn
А1	с11 х11	с12 х12	с13 х13		с1n х1n	a1
А2	с21 х21	с22 х22	с23 х23		с2n х2n	a2
А3	с31 х31	с32 х32	с33 х33		с3n х3n	a3
...	...	...	...	...	...	...
Аm	сm1 хm1	сm2 хm2	сm3 хm3		сmn хmn	am
Потр.	в1	в2	в3	...	вn

Матриця називається матрицею тарифів.

Для такої задачі невідомою є матриця перевезень – (тут х_ij означає кількість вантажу, перевезеного з i пункту постачальника в j пункт споживача.

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

(69)

Така задача вирішується при наступних обмеженнях: весь вантаж з пунктів постачальника повинен бути повністю вивезеним, і всі потреби пунктів споживача повинні бути повністю задоволені

(70)

(71)

(72)

Умовою сумісності транспортної системи обмежень є наявність балансу

запаси вантажу дорівнюють потребам (73)

Якщо умова (73) виконується, то математична модель ТЗ називається закритою. Якщо умова (73) не виконується, то математична модель ТЗ називається відкритою.

Відмітимо, що відкриту модель завжди можна привести до її закритого виду. Допустимо, що , тоді в розподільну таблицю ТЗ уводиться фіктивний (n+1) пункт споживання з потребами відповідно рівними . У той же час тарифи для даного пункту.

Такий підхід дозволяє записати математичну модель закритої задачі.

Дата добавления: 2014-12-07