Постановка і математичне формулювання задачі про прикріплення споживачів до постачальників

Размещено на http://www.allbest.ru/

Постановка і математичне формулювання задачі про прикріплення споживачів до постачальників

Шатрова І.А.,

Демидова О.О.,

Матвієвський С.В.

^{1 2}' 4' 5Київський національний університет будівництва і архітектури

Постановка задачі. Є n споживачів будівельних матеріалів і m постачальників. Відомі обсяги матеріалів, які треба доставити кожному споживачу йі (і =1, 2,..., n) і можливий обсяг поставок кожного постачальника bj (j = 1, 2,., m). Вартість доставки продукції і-му споживачу от j-го постачальника складає Су. Необхідно знайти такі обсяги поставок матеріалів і-му споживачу від j-го постачальника Ху, при яких буде забезпечена мінімальна загальна вартість доставки матеріалів.

Вихідні дані для розв'язання задачі представлені у таблиці 1.

Таблиця 1 Вихідні дані

Математичне формулювання задачі полягає у знаходженні мінімуму функції:

при умовах

Умова (2) вимагає доставки всього обсягу поставок постачальника; умова (3) передбачає забезпечення необхідного обсягу поставок кожному споживачу; умова (4) виключає від'ємні значення поставок.

Оптимальне розв'язання задачі (1)-(4) досягається з використанням алгоритму транспортної задачі лінійного програмування.

Для розв'язання транспортної задачі методом потенціалів треба мати початковий опорний план. Є декілька методів пошуку початкових опорних планів транспортної задачі:

- метод північно-західного кута;

- метод мінімального елементу в матриці;

- метод подвійної переваги;

- метод апроксимації Фогеля.

Метод північно-західного кута. Побудова початкового опорного плану починається з лівого верхнього кута матриці (табл. 2).

Таблиця 2

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

(290х 13)+(10х 4)+(230х 10)+(20х 7)+

+(220х 10)+(130х 14)+(10х 6)+(140х 3) = 10750 грн.

Метод мінімального елементу в матриці. В матриці вартості шукаємо мінімальний елемент (табл. 3).

Таблиця 3

В цьому випадку мінімальний елемент міститься в клітині (a₄b₅). В цю клітинку ставимо максимально можливу поставку - 140 од. (b₅ = 140 < a₄ = 150). П'ятий стовпець виключаємо з подальшого розгляду. Знову знаходимо мінімальний елемент в матриці, який міститься в клітинці (a₂b₁). Через те, що b₁ = 290 > a₂ = 250, в клітинку (a₂b₁) ставимо максимально можливу поставку - 250 од. В частині матриці, яка залишилися, знову шукаємо мінімальний елемент і т.д.

Загальна вартість перевезень становить:

(240х 4)+(60х 9)+(250х 4)+(30х 15)+

+(180х 10)+(140х 14)+(10х 6)+(140х 3) = 7190 грн.

Іноді при побудові початкового опорного плану або в процесі розв'язання транспортної задачі методом потенціалів виникає випадок виродженості. постачальник алгоритм споживач

Для визначення потенціалів шляхом розв'язання відповідних рівнянь кількість зайнятих місць в матриці повинно дорівнювати m+n-- 1, де m -кількість стовпців в матриці; n - кількість рядків.

Якщо число зайнятих місць в матриці менше m+n--1, має місце випадок вродженості. При числі зайнятих місць в матриці менше ніж m + n--1, неможливо знайти всі значення потенціалів, і отже, неможливо дослідити незайняті місця матриці, тобто задачу розв'язати неможливо. Для усунення вродженості опорного плану в деякі незайняті клітинки ставимо нульові поставки і ці їх вважають зайнятими місцями.

Література

1. Гриньова В.М. Організація виробництва: підручник / В.М. Гриньова, М.М. Салун. - Київ: Знання, 2009. - 580 с.

2. Івченко І. Ю. Математичне програмування / І. Ю. Івченко. - Київ: ЦУЛ, 2007. - 230 с.

3. Лугінін О. Є. Економіко-математичне моделювання / О. Є. Лу- гінін, В.М. Фомішина. - Київ: Знання, 2011. - 342 с.

4. Тригер Г.М. Оптимізація використання будівельних машин і транспорту у будівництві: методичні рекомендації для студентів спеціальності 7.092101 "Промислове і цивільне будівництво" / Г.М. Тригер, С.А. Ушацький. - Київ: КНУБА 2010. - 23 с.

5. Тригер Г.М. Розробка й оптимізація календарних планів зведення комплексу будівель і споруд: навч. посіб. / Г.М. Тригер. - Київ: ІСДО, 2013. - 72 с.

6. Цегелик Г.Г. Лінійне програмування / Г.Г. Цегелик. - Лівів: Світ, 2015. - 216 с.

7. Організація будівництва: підручник / Ю.П. Шейко, Г.М. Тригер и др. ; за ред. С.А. Ушацького. - Київ: Кондор, 2005. - 519 с.

Размещено на Allbest.ru