ЛабораторнаРобота №4 Побудова моделі транспортної задачі та її аналіз і. Загальні положення

Існує доволі широке коло задач математичного програмування, в економіко-математичних моделях яких одна або кілька змінних мають набувати цілих значень. До таких задач можна віднести транспортну задачу.

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

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

Іі. Теоретичні відомості

Класична транспортна задача лінійного програмування формулюється так: деякий однорідний продукт, що знаходиться у m постачальників А_ів обсягах одиниць відповідно необхідно перевезти n споживачамв обсягах одиниць. При цьому виконується умова, що загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі вартості перевезень одиниці продукції від кожного А_і-го постачальника до кожного В_j-го споживача, що подані як елементи матриці С:

.

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

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

Запишемо її математичну модель. Позначимо через обсяг продукції, що перевозиться від постачальника до споживача . Тоді умови задачі зручно подати у вигляді табл. 4.1:

Таблиця 4.1

Умова транспортної задачі

Споживачі		В1	В2	...	Вn
Постачальники		b1	b2	...	bn
A1	а1	с11 x11	с12 x12	...	с1n x1n
A2	а2	с21 x21	с22 x22	…	с2n x2n
…	…	…	…	…	…
Am	аm	сm1 xm1	сm2 xm2	…	сmn xmn

Мають виконуватися такі умови:

1. сумарний обсяг продукції, що вивозиться з кожного і-го пункту, має дорівнювати запасу продукції в даному пункті:

;

2. сумарний обсяг продукції, що ввезений кожному j-му споживачеві, має дорівнювати його потребам:

;

3. сумарна вартість всіх перевезень повинна бути мінімальною:

Очевидно, що .

У скороченій формі запису математична модель транспортної задачі за критерієм вартості перевезень має такий вигляд:

(4.1)

за обмежень:

; (4.2)

; (4.3)

. (4.4)

У розглянутій задачі має виконуватися умова:

. (4.5)

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