Постановка і математичне формулювання задачі про прикріплення споживачів до постачальників
Математичне формулювання задачі про обсяги поставок споживачу від постачальника; знаходження мінімуму функції. Використання алгоритму транспортної задачі лінійного програмування. Розподіл ресурсів постачальника. Метод мінімального елементу в матриці.
| Рубрика | Математика |
| Вид | статья |
| Язык | украинский |
| Дата добавления | 17.06.2022 |
| Размер файла | 44,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Постановка і математичне формулювання задачі про прикріплення споживачів до постачальників
Шатрова І.А.,
Демидова О.О.,
Матвієвський С.В.
1 2' 4' 5Київський національний університет будівництва і архітектури
Постановка задачі. Є n споживачів будівельних матеріалів і m постачальників. Відомі обсяги матеріалів, які треба доставити кожному споживачу йі (і =1, 2,..., n) і можливий обсяг поставок кожного постачальника bj (j = 1, 2,., m). Вартість доставки продукції і-му споживачу от j-го постачальника складає Су. Необхідно знайти такі обсяги поставок матеріалів і-му споживачу від j-го постачальника Ху, при яких буде забезпечена мінімальна загальна вартість доставки матеріалів.
Вихідні дані для розв'язання задачі представлені у таблиці 1.
Таблиця 1 Вихідні дані
|
Постачальник |
Споживач |
Обсяг постачання |
||||
|
Аі |
Аг |
An |
||||
|
Ві |
Сіі |
C12 |
Cln |
bi |
||
|
В 2 |
С 21 |
C22 |
C2n |
hi |
||
|
Вт |
Ст 1 |
Cm2 |
C mn |
bm |
||
|
Обсяг споживання |
a |
Ь2 |
an |
Математичне формулювання задачі полягає у знаходженні мінімуму функції:
при умовах
Умова (2) вимагає доставки всього обсягу поставок постачальника; умова (3) передбачає забезпечення необхідного обсягу поставок кожному споживачу; умова (4) виключає від'ємні значення поставок.
Оптимальне розв'язання задачі (1)-(4) досягається з використанням алгоритму транспортної задачі лінійного програмування.
Для розв'язання транспортної задачі методом потенціалів треба мати початковий опорний план. Є декілька методів пошуку початкових опорних планів транспортної задачі:
- метод північно-західного кута;
- метод мінімального елементу в матриці;
- метод подвійної переваги;
- метод апроксимації Фогеля.
Метод північно-західного кута. Побудова початкового опорного плану починається з лівого верхнього кута матриці (табл. 2).
Таблиця 2
|
ai |
b |
|||||
|
290 |
240 |
240 |
140 |
140 |
||
|
300 |
13 290 |
4 10 |
9 |
12 |
8 |
|
|
250 |
4 |
10 230 |
7 20 |
5 |
4 |
|
|
350 |
15 |
13 |
10 220 |
14 130 |
18 |
|
|
150 |
6 |
12 |
9 |
6 10 |
3 140 |
Розподіл ресурсів першого постачальника здійснюється таким чином, що спочатку задовольняються потреби першого споживача, потім другого і т.д. до повного розподілу ресурсів. Після розподілу ресурсів першого постачальника переходять до другого і розподіляють таким же чином його ресурси. Розподіл ресурсів решти постачальників здійснюють у такому ж порядку. У результаті отримують начальний опорний план. Так як елементами матриці є вартість перевезень будівельних матеріалів за одиницю виміру, то загальна вартість перевезень становить:
(290х 13)+(10х 4)+(230х 10)+(20х 7)+
+(220х 10)+(130х 14)+(10х 6)+(140х 3) = 10750 грн.
Метод мінімального елементу в матриці. В матриці вартості шукаємо мінімальний елемент (табл. 3).
Таблиця 3
|
a |
||||||
|
290 |
240 |
240 |
140 |
140 |
||
|
300 |
13 |
4 240 |
9 60 |
12 |
8 |
|
|
250 |
4 250 |
10 |
7 |
5 |
4 |
|
|
350 |
15 30 |
13 |
10 180 |
14 140 |
18 |
|
|
150 |
6 10 |
12 |
9 |
6 |
3 140 |
В цьому випадку мінімальний елемент міститься в клітині (a4b5). В цю клітинку ставимо максимально можливу поставку - 140 од. (b5 = 140 < a4 = 150). П'ятий стовпець виключаємо з подальшого розгляду. Знову знаходимо мінімальний елемент в матриці, який міститься в клітинці (a2b1). Через те, що b1 = 290 > a2 = 250, в клітинку (a2b1) ставимо максимально можливу поставку - 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
...Подобные документы
Дослідження предмету і сфери застосування математичного програмування в економіці. Класифікація задач цієї науки. Загальна задача лінійного програмування, деякі з методи її розв’язування. Економічна інтерпретація двоїстої задачі лінійного програмування.
курс лекций [59,9 K], добавлен 06.05.2010Розв'язання завдання графічним способом. Зображення розв'язку системи нерівностей, визначення досягнення максимуму та мінімуму функції. Розв'язання транспортної задачі методом потенціалів та симплекс-методом, формування оціночної матриці з елементів.
задача [134,9 K], добавлен 31.05.2010Послідовність графічного розв'язання задачі лінійного програмування. Сумісна система лінійних нерівностей, умови невід'ємності, визначення півплощини з граничними прямими. Графічний метод для визначення оптимального плану задачі лінійного програмування.
задача [320,6 K], добавлен 31.05.2010Сутність симплекс-методу у вирішенні задач лінійного програмування. Рішення задачі на відшукання максимуму або мінімуму лінійної функції за умови, що її змінні приймають невід'ємні значення і задовольняють деякій системі лінійних рівнянь або нерівностей.
реферат [28,5 K], добавлен 26.02.2012Випадок однорідної крайової задачі. Розв’язання виродженого крайового виразу. Теорема Коші, іі доведення. Означення узагальненої функції Гріна крайової задачі. Формулювання алгоритму відшукання узагальненої функції Гріна. Приклади роз'язання завдань.
лекция [108,5 K], добавлен 24.01.2009Поняття та значення симплекс-методу як особливого методу розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального рішення. Розв'язання задачі з використанням програми Simplex Win.
лабораторная работа [264,1 K], добавлен 30.03.2015Складання плану виробництва при максимальному прибутку. Введення додаткових (фіктивних) змінних, які перетворюють нерівності на рівності. Розв’язування задачі лінійного програмування графічним методом та економічна інтерпретація отриманого розв’язку.
контрольная работа [298,3 K], добавлен 20.11.2009Практична реалізація задачі Гамільтона про мандрівника методом гілок та меж. Математична модель задачі комівояжера, її вирішення за допомогою алгоритму Літтла. Програмне знаходження сумарних мінімальних характеристик (відстані, вартості проїзду).
курсовая работа [112,5 K], добавлен 30.09.2014Основні типи та види моделей. Основні методи складання початкового опорного плану. Поняття потенціалу й циклу. Критерій оптимальності базисного рішення транспортної задачі. Методи відшукання оптимального рішення. Задача, двоїста до транспортного.
курсовая работа [171,2 K], добавлен 27.01.2011Розв'язання системи лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць. Будування математичної моделі задачі лінійного програмування. Умови для застосування симплекс-методу. Розв'язка спряженої задачі.
практическая работа [42,3 K], добавлен 09.11.2009Формулювання задачі мінімізації. Мінімум функції однієї та багатьох змінних. Прямі методи одновимірної безумовної оптимізації: метод дихотомії і метод золотого перерізу. Метод покоординатного циклічного спуску. Метод правильного і деформованого симплексу.
курсовая работа [774,0 K], добавлен 11.08.2012Розв'язок задач лінійного програмування симплексним методом, графічне вирішення системи нерівностей, запис двоїстої задачі: визначення прибутку, отриманого підприємством від реалізації виробів; загальних витрат, пов’язаних з транспортуванням продукції.
контрольная работа [296,0 K], добавлен 28.03.2011Опис одного з поширених ітераційних методів, методу хорда — ітераційного методу знаходження кореня рівняння, який ще має назви метод лінійного інтерполювання, метод пропорційних частин, або метод хибного положення. Задачі для самостійного розв’язування.
реферат [336,8 K], добавлен 04.12.2010Необхідні поняття теорії графів. Задача про максимальний потік. Алгоритм Форда знаходження максимального потоку. Модифікація алгоритму Форда розв’язання задачі максимізації кількості призначень у задачах розподілу. Результати числового експерименту.
курсовая работа [499,9 K], добавлен 18.12.2013Розв'язання графічним методом математичної моделі задачі з організації випуску продукції. Розв'язання транспортної задачі методом потенціалів. Знаходження умовних екстремумів функцій методом множників Лагранжа. Розв'язання задач симплекс-методом.
контрольная работа [48,5 K], добавлен 16.07.2010Поняття диференціальних рівнянь. Задача Коші і крайова задача. Класифікація методів для задачі Коші. Похибка методу Ейлера. Модифікований метод Ейлера-Коші. Пошук рішення задачі однокроковим методом Ейлера. Порівняння чисельного рішення з точним рішенням.
презентация [294,4 K], добавлен 06.02.2014Задача продавлення шкідливих збурень. Збурювальні задачі, що видвинуті для розгляду радіотехнікою, в деякому розуміння протилежні задачам класичної теорії збурень. Дійснi нелінійнi диференціальнi рівняння. Завдання радіотехніки, задачі генерації збурень.
дипломная работа [890,8 K], добавлен 17.06.2008Історія створення і різні формулювання теореми Піфагора як актуальної математичної задачі, спроби докази теореми. Визначення теореми Фалеса про пропорційні відрізки, її рішення. Місце теореми Вієта та формули Герона в сучасному шкільному курсі геометрії.
курсовая работа [1,5 M], добавлен 25.05.2019Історія розвитку математичної науки. Математичне моделювання і дослідження процесів і явищ за допомогою функцій, рівнянь та інших математичних об`єктів. Функції, їх основні властивості та графіки, множина раціональних чисел. Розв`язання типових задач.
книга [721,3 K], добавлен 01.03.2011Теорема Куна-Такера. Побудування функції Лагранжа. Задача квадратичного програмування. Узагальнення симплексного метода лінійного програмування згідно методу Біла. Правила переходу від однієї таблиці до іншої. Система обмежень у допустимої області.
курсовая работа [252,9 K], добавлен 08.05.2014
