Оптимізація перевезення матеріальних ресурсів

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

Задача перевезення однорідного продукту (транспортна задача-Т3) з m пунктів виробництва (постачання) в n пунктів споживання описується за допомогою лінійної моделі такого виду:

, (86)

, (87)

, (88)

, (89)

де x_ij - шукана кількість одиниць матеріалу, яка підлягає перевезенню з i -го пункта в j -ий;

c_ij - витрати на перевезення одиниці матеріалу;

A_i - виробничі можливості i -го постачальника;

B_j - розмір потреби j -го споживача в матеріальному ресурсі.

 

Якщо для задачі(86) - (89) виконується умова

, (90)

то модель називається замкненою, якщо не виконується - то відкритою.

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

Для знаходження оптимального розв’язку транспортної задачі (86) - (89) можна скористатися симплексним методом, але цей шлях є неефективним. Існують спеціальні методи знаходження оптимального розв’язку ТЗ зокрема модифікований розподільний метод (метод потенціалів).

Кожна ТЗ, як задача лінійного програмування, зв’язана з відповідною двоїстою задачею такого виду:

z= , (91)

, (92)

, (93)

де U_i - двоїсті змінні, які відповідають обмеженням (2);

V _j -двоїсті змінні, які відповідають обмеженням (3).

 

Розв’язки прямої та двоїстої задач зв’язані між собою такими співвідношеннями:

для ,

для ,

де - оптимальний розв’язок прямої задачі (86)-(89);

- оптимальний розв’язок двоїстої задачі (91)-(93).

Числа називають потенціалами виробників і споживачів відповідно.

 

Приклад 6.

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

 

Таблиця 4.

	В1=50	В2=120	В3=80	Ui
А1=100
А2=150				-2
Vj

 

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

 

2x₁₁+3x₁₂+5x₁₃+4x₂₁+2x₂₂+3x₂₃ min,

U₁ x₁₁+x₁₂+x₁₃=100,

U₂ x₂₁+x₂₂+x₂₃=150,

V₁ x₁₁+x₂₁=50,

V₂ x₁₂+x₂₂=120,

V₃ x₁₃+x₂₃=80,

Ця задача є замкненою, бо виконується умова (90):

100+150=50+120+80.

Опорний розв’язок задачі знайдемо методом подвійної переваги. Першочергово поставка ресурсу здійснюється в клітини, які позначені двома значками переваги V (W), далі - в клітини, які позначені одним значком переваги V, тобто

x₁₁=50, x₂₂=120, x₂₃=30.

Залишилося заповнити одну клітину

x₁₃=50.

Цей розв’язок

x_ij=

буде опорним, оскільки число базисних елементів (m+n-1=2+3-1), дорівнює числу заповнених клітин(4).

Побудуємо двоїсту задачу

100U₁+150U₂+50V₁+120V₂+80V₃ max,

,

,

,

,

,

,

,

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

З цією метою розрахуємо потенціали виробників і споживачів, поклавши U₁=0. Для заповнених клітин, тобто для клітин в яких повинні виконуватися умови:

U₁+V₁=2, V₁=2,

U₁+V₃=5, V₃=5,

U₂+V₃=3, U₂= -2,

U₂+V₂=2, V₂=4.

Переконаємося,чи виконується умова оптимальності для вільних клітин ():

4 + 0 = 4 > 3, умова не виконується,

2 - 2 = 0 < 4, умова виконується.

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

 

 

Максимальний розмір переміщення ресурсу визначається з умови:

Новий план перевезення матеріалу наведений в табл.5.

j i	В1=50	В2=120	В3=80	Ui
А1=100
А2=150				-1
Vj

 

Для цього розв’язку умови оптимальності виконуються, отже розв’язок

X_ij^*=

є оптимальним, а витрати

(гр.од.)

є мінімальними.

Якщо порівняти ці витрати з витратами на перевезення матеріалу для початкового опорного розв’язку

(гр.од.),

то можна пересвідчитися, що ефект від оптимізації становить:

абсолютний розмір економії

630-680=-50(гр.од.),

відносний розмір економії

= =0,0735,(7,35%).