19812

Знаходження оптимального розподілу поставок методом оцінки клітин

Доклад

Информатика, кибернетика и программирование

2.Знаходження оптимального розподілу поставок методом оцінки клітин Один з найбільш простих методів вирішення транспортної задачі розподільний метод.Нехай для транспортної задачі знайдено початкове опорне рішення і обчислено значення цільової функції на цьому ріше

Украинкский

2013-07-17

28 KB

1 чел.

2.Знаходження оптимального розподілу поставок методом оцінки клітин

Один з найбільш простих методів вирішення транспортної задачі - розподільний метод.
Нехай для транспортної задачі знайдено початкове опорне рішення і обчислено значення цільової функції на цьому рішенні Z (). За теоремою для кожної вільної клітини таблиці завдання можна побудувати єдиний цикл, який містить цю клітку і частина клітин, зайнятих опорним рішенням. Означивши цей цикл і здійснивши зрушення (перерозподіл вантажу) по циклу на величину =, можна отримати нове опорне рішення Х2.
Визначимо, як зміниться цільова функція при переході до нового опорного рішення. При зсуві на одиницю вантажу по циклу, відповідному клітці (l, k), приріст цільової функції дорівнює різниці двох сум: =, де - сума вартостей перевезень одиниць вантажу в непарних клітинах циклу, позначених знаком "+", - сума вартостей перевезень одиниць вантажу в парних клітинах циклу, позначених знаком «-».
У клітинах, позначених знаком "+", величини вантажу додаються, що призводить до збільшення значення цільової функції Z (), а в клітинах, позначених знаком "-", величини вантажу зменшуються, що призводить до зменшення значення цільової функції.
Якщо різниця сум для вільної клітини (l, k) менше нуля, тобто <0, то перерозподіл величини за відповідним циклу призведе до зменшення значення Z () на величину, тобто опорне рішення можна поліпшити. Якщо ж величини, звані оцінками, для всіх вільних клітин таблиці транспортної задачі ненегативні, то значення цільової функції не можна зменшити і опорне рішення оптимально. Отже, ознакою оптимальності розподільного методу є умова = 0. (11)
Для вирішення транспортної задачі розподільним методом необхідно знайти початкове опорне рішення. Потім для чергової опорної клітини (l, k) побудувати цикл і обчислити оцінку. Якщо оцінка ненегативна, перехід до наступного вільної клітці. Якщо ж оцінка негативна, слід здійснити зсув по циклу на величину =. В результаті вийде нове опорне рішення.
Для кожного нового опорного рішення обчислення оцінок починається з першої вільної клітини таблиці. Очевидність перевіряються вільних клітин доцільно встановлювати в порядку зростання вартості перевезень, так як вирішується завдання на знаходження мінімуму.


 

А также другие работы, которые могут Вас заинтересовать

11672. Управління персоналом. На основі методу експортних оцінок визначаємо перспективну місткість ринку антибіотиків фармацевтичної компанії на ринку регіону 435 KB
  ЛАБОРАТОРНА РОБОТА № 5 з дисципліни Менеджмент персоналу На основі методу експортних оцінок визначаємо перспективну місткість ринку антибіотиків фармацевтичної компанії на ринку регіону. Вихідні данні наведені в таблиці 5.1 всі розрахунки проводимо за допомогою MS E...
11673. Учебно-методический комплекс дисциплины: Судовые турбомашины МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНЫМ РАБОТАМ 190.5 KB
  Учебно-методический комплекс дисциплины: Судовые турбомашины МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНЫМ РАБОТАМ ВВЕДЕНИЕ Процесс постоянного увеличения мощности и уменьшения массогабаритных показателей СЭУ обусловил все большее применен...
11674. Робота з інформаційно-довідковою системою Независимые производители товаров и услуг 248.78 KB
  Тема: Робота з інформаційнодовідковою системою Независимые производители товаров и услуг. Мета: вивчити призначення і можливості інформаційнодовідкової системи Независимые производители товаров и услуг навчитися працювати з цією системою. Порядок виконання р...
11675. Створення діаграми класів 65.38 KB
  Тема: Створення діаграми класів. Мета роботи: отримати навички побудови діаграм класів створення пакетів і угруповання класів у пакети. Завдання: створити діаграму класів. Для одного зі сценаріїв діаграми прецедентів створеної в попередній лабораторній робот...
11676. Створення діаграм діяльності 50.69 KB
  Лабораторна робота № 3. Тема: Створення діаграм діяльності. Мета роботи: отримати навички побудови діаграм діяльності. Завдання: створити діаграму діяльності що описує один з бізнеспроцесів обраної предметної області; створити діаграму діяльності що оп...
11677. Баланс ліквідності підприємства 36.76 KB
  Тема: Баланс ліквідності підприємства. Мета: зробити фінансовий аналіз балансу ліквідності підприємства. Хід роботи Висновок: З цих даних отримуємо А1 П1 А2 П2 А3 П3 А4 П4 тобто ліквідність балансу відрізняється від абсолютної. При цьому нестача коштів по одній гру
11678. Моделювання та мінімізація логічних функції в різних пакетах прикладних програм 1.39 MB
  Використання електроніки в електроенергетиці, є досить розвинене. Майже усі технологічні процеси в галузі електроенергетики автоматизуються за допомогою змодельованих на ЕОМ процесів та схем. Найпоширеніше використання має алгебра логіки, яку далі розглянемо більш детальніше.
11679. Ітераційні методи розвязання систем лінійних алгебраїчних рівнянь. Метод Зейделя. Метод релаксації 40.97 KB
  Лабораторна робота №2 Ітераційні методи розвязання систем лінійних алгебраїчних рівнянь. Метод Зейделя. Метод релаксації. Мета роботи: познайомитися з ітераційними методами розвязання систем алгебраїчних рівнянь реалізувати заданий за варіантом метод у серед...
11680. МОДЕРНИЗАЦИЯ ЭЛЕКТРОПРИВОДА ЛЕНТОЧНОГО КОНВЕЙЕРА К-22 УГЛЕПОДГОТОВИТЕЛЬНОГО ЦЕХА №1 ЧерМК ОАО «Северсталь» 1.26 MB
  Развитие электропривода связывается с разработкой российским академиком Б. С. Якоби первого двигателя постоянного тока вращательного движения. Использование данного мотора на небольшом судне, которое в 1838 году произвело пробные поездки на Неве...