Управлінські рішення в задачах розподільного типу
1. Приклади розподільних завдань: транспортна і завдання про призначення.
2. Постановка транспортної задачі і її математична модель.
3. Методи побудови плану перевезень
4. Метод потенціалів знаходження оптимального рішення.
5. Множинність управлінських рішень.
6. Управлінські рішення в відкритих завданнях розподільного типу.
1. Приклади розподільних завдань: транспортна і завдання про призначення
Умова. Студентські загони СО-1, СО-2 і СО-3 чисельністю 70, 99 і 80 чоловік беруть участь в сільськогосподарських роботах.
Для збирання картоплі на полях П1. П2. П3 і П4 необхідно виділити відповідно 47, 59, 49 і 43 людини. Продуктивність праці студентів залежить від врожайності картоплі, від чисельності загону, характеризується для зазначених загонів і полів в центнерах на людину за робочий день і представлена в матриці:
2. Постановка транспортної задачі і її математична модель
Економічна постановка транспортної задачі
У пунктах відправлення знаходиться однорідний вантаж в кількостях, який повинен бути відправлений споживачам в кількостях.
Відомі транспортні витрати (тарифи) на перевезення одиниці продукції з кожного пункту в пункт, що утворюють матрицю транспортних витрат.
Потрібно знайти такий план перевезень, при якому весь вантаж буде вивезено, всі потреби задоволені, а вартість усього перевезеного вантажу буде найменшою.
Математична модель транспортної задачі
Позначимо через кількість вантажу, що перевозиться з пункту в пункт. План перевезень можна записати у вигляді матриці.
За змістом, змінні невід'ємні:. (1)
Цільова функція означає загальні транспортні витрати, які повинні бути найменшими:
Система обмежень включає умови вивезення вантажу і доставки вантажу.
1) Якщо запас вантажу дорівнює потребам, то система обмежень набуде вигляду:
. (Умови вивезення наявного вантажу) (3)
. (Умови доставки необхідного вантажу) (4)
2) Якщо запас вантажу більше потреб, то всі потреби будуть задоволені, але не всі запаси будуть вивезені, і умова вивезення набуде вигляду
3) Якщо ж запас вантажу менше потреб, то всі запаси будуть вивезені, але не всі потреби будуть задоволені, і умова доставки вантажу набуде вигляду
Математична постановка транспортної задачі.
серед безлічі невід'ємних розв'язків системи лінійних рівнянь (3) і (4) знайти таке рішення, при якому лінійна функція (2) приймає мінімальне значення.
План перевезень називається допустимим, якщо він задовольняє обмеженням (1), (3), (4).
Допустимий план перевезень, який доставляє мінімум цільової функції, називається оптимальним.
Зазвичай дані транспортної задачі записують у вигляді розподільчої таблиці (таблиця 1).
Для того щоб транспортна задача мала рішення, необхідно і достатньо, щоб сумарні запаси постачальників дорівнювали сумарним потребам споживачів
В цьому випадку транспортна задача називається збалансованою, а модель - закритою. Якщо ж це рівність не виконується, то завдання називається незбалансованої (з неправильним балансом), а її модель - відкритою.
Якщо транспортна задача відкрита. то необхідно додати фіктивного постачальника (або споживача) з недостатнім обсягом поставки і нульовий вартістю перевезення. Розподіл поставки фіктивному споживачеві (постачальнику), йде в останню чергу.
Транспортні завдання вирішуються за допомогою загального прийому послідовного поліпшення плану перевезень. Він включає в себе наступні етапи:
Побудова вихідного плану перевезень.
Перевірка плану перевезень на оптимальність.
Поліпшення плану перевезень.
3. Методи побудови плану перевезень
Розглянемо два методи побудови початкового плану перевезень в розподільній таблиці.
Метод "північно-західного кута".
Будемо розподіляти вантаж, починаючи з верхньої лівої клітки, умовно званої північно-західній: в клітку (1.1) заносять число, мінімальне з чисел і, тобто .
Якщо, то і потреби пункти повністю задоволені. Після цього заповнюється клітка (1.2) числом.
Якщо ж. то і запас вантажу в повністю вичерпаний. Після цього заповнюється клітка (2.1) числом.
Процес триває до тих пір, поки не вичерпаються всі ресурси і повністю не буде задоволений попит. Останньою заповнюється клітка.
Незаповненим клітинам таблиці відповідають значення змінних (вільні змінні), а заповненим - значення змінних (базисні змінні).
Число заповнених кленок в опорному плані перевезень повинно бути рівно. Якщо в процесі заповнення таблиці одночасно вичерпується запас вантажу і повністю задоволений попит (одночасно виключається рядок і стовпець), то в будь-яку вільну клітину треба умовно вважати зайнятої. Для цього в неї потрібно вписати число 0, але щоб ця клітина не утворила циклу з раніше зайнятими клітинами.
Метод "мінімального елемента".
Збалансувати завдання (переконатися, що ТЗ закрита).
Визначити вільну клітину з найменшою вартістю перевезення. Якщо таких клітин кілька, то вибрати клітку з найбільшою потенційною вантажоперевезенням. Якщо і таких клітин кілька, то вибирається будь-яка з цих клітин.
В обрану клітку
у поставити максимально можливу вантажоперевезення для споживача від постачальника.
З решти клітин таблиці знову вибирають клітку з найменшим тарифом. Процес розподілу вантажу закінчується, коли всі запаси постачальників вичерпані, а попит споживачів повністю задоволений.
В результаті отримуємо опорний план, який повинен містити заповнених клітин.
Завдання 1. Наведемо як приклад два плану перевезень транспортної задачі: перший побудований за методом "північно-західного кута" (табл.2), другий - методом "мінімального елемента" (табл.3).
Таблиця 2 - План перевезень за методом «північно-західного кута»
Таким чином, ТЗ закрита і, отже, має оптимальне рішення.
2) Запишемо математичну модель ТЗ.
Позначимо через кількість перевезеного вантажу з () в (), при цьому. Складемо систему обмежень:
умови вивезення вантажу
умови доставки вантажу
Сумарні витрати на перевезення вантажу рівні
Потрібно знайти таке невід'ємне рішення системи обмежень, при якому функція приймає найменше значення.
3) Побудуємо вихідне опорне рішення методом «мінімального елемента».
Заповнення клітин в розподільній таблиці наступна: (2,1), (1,4), (3,3), (3,4), (3,2), (2,2).
У плані перевезень число заповнених клітин одно m + n - 1 = 3 + 4 - 1 = 6. Транспортні витрати складають.
Знайдемо потенціали і з системи рівнянь, складених для заповнених клітин.
В системі число рівнянь менше числа невідомих, тому система має безліч рішень, при цьому число вільних невідомих дорівнює 7 - 6 = 1.
Додамо невідомої (вона найчастіше зустрічається в системі) довільне значення. Тоді решта потенціали рівні:
Обчислимо оцінки вільних змінних, відповідних вільним клітинам:
Оцінка, тому план перевезень не оптимальний і транспортні витрати не є найменшими.
6) Покращимо план перевезень.
Побудуємо для клітини (2,4) в таблиці 5 замкнутий цикл: (2,4), (2,2), (3,2), (3,4). Припишемо знаки «+» і «-» вершин циклу, починаючи з клітини (2,4), послідовно чергуючи їх. Знайдемо число і перемістимо його по циклу: віднімемо 100 з значень негативних клітин і додамо 100 до значень позитивних. В результаті клітина (2,4) стала зайнятою,, а дві клітини (2,2) і (3,4) звільнилися.
Потреби у вантажі
У новому плані перевезень заповнених клітин 5, а повинно бути. З двох звільнених клітин (3,4) і (2,2) заповнимо базисним нулем клітку (3,4), так як їй відповідає менша вартість перевезень, а клітку (2,2) залишимо вільною.
Потреби у вантажі
Отримаємо таблицю 7 з новим опорним планом перевезень, для якого транспортні витрати дорівнюють.
Перевіримо правильність розрахунків, використовуючи формулу (11.7):
7) Перевіримо рішення на оптимальність.
Знайдемо потенціали і з нової системи рівнянь, складених для заповнених клітин таблиці 7:
При отримаємо одне з рішень цієї системи:
Всі оцінки вільних змінних позитивні:
Відсутність негативних оцінок є ознакою оптимальності плану перевезень, при якому значення цільової функції мінімально і одно.
8) Дадімекономіческое тлумачення оптимального рішення.
Для того, щоб витрати на перевезення вантажу з пунктів,, були найменшими і становили 2200, потрібно відправити: 1) 100 од. вантажу з в; 2) 300 од. вантажу з в і 100 од. з в; 3) 500 од. вантажу з в і 100 од. вантажу з в.
5. Множинність управлінських рішень
Наявність нульових оцінок вільних змінних для оптимального плані перевезень є ознакою того, що завдання має альтернативний оптимум (множинність оптимальних рішень).
У будь-якому оптимальному плані для каждойсвободной клітини снулевойоценкой будують цикл і переміщують по ньому відповідне число, в результаті отримують набір оптимальних рішень.
Загальна оптимальне рішення є лінійна опукла комбінація оптимальних рішень:
6. Управлінські рішення в відкритих завданнях розподільного типу
Транспортна задача називається відкритою, якщо.
1) Нехай для ТЗ виконується умова (загальні запаси вантажу менше сумарних потреб).
Для вирішення ТЗ вона наводиться до закритого виду: вводиться фіктивний постачальник з "запасом" вантажу і нульовими тарифами на перевезення вантажу від постачальника до всіх споживачів:. У розподільну таблицю додається знизу () -я рядок, в якій запаси вантажу рівні, а тарифи на перевезення.
В оптимальному плані перевезень даної відкритої ТЗ завантаження будь-якої клітини для фіктивного постачальника вказує на недопоставкугруза відповідному споживачеві.
2) Нехай для ТЗ виконується (загальні запаси вантажу більше сумарних потреб).
Для приведення ТЗ до закритого виду вводиться фіктивний споживач з "потребою" у вантажі і нульовими тарифами на перевезення вантажу від усіх постачальників до споживача, тобто . У розподільну таблицю додається праворуч () -й стовпець, в якому потреба у вантажі дорівнює, а тарифи на перевезення до фіктивного споживача.
В оптимальному плані перевезень такий ТЗ завантаження будь-якої клітини для фіктивного споживача вказує на залишок нерозподіленого вантажу у постачальника послуг.
Контрольні питання
Дайте економічну постановку транспортної задачі (ТЗ) за критерієм вартості.
Яка транспортна задача називається: 1) закритою; 2) відкритої?
Скільки змінних містить математична модель закритої ТЗ?
Запишіть математичну модель закритої ТЗ за критерієм вартості, дайте економічне тлумачення змінним, обмеженням і цільової функції.
Опишіть правило перетворення відкритої моделі ТЗ в закриту ТЗ, якщо 1); 2).
Опишіть побудова в розподільній таблиці вихідного плану перевезень методом "північно-західного кута". Скільки заповнених клітин має бути в розподільній таблиці і як цього досягти?
Опишіть побудова в розподільній таблиці вихідного опорного плану перевезень методом "мінімального елемента".
Опишіть сутність методу потенціалів знаходження оптимального плану перевезень ТЗ.
Сформулюйте ознаку оптимальності плану перевезень ТЗ, розв'язуваної методом потенціалів.
З якою метою і як будується цикл перерахунку в розподільній таблиці, якщо план перевезень не є оптимальним? Як визначається завантаження вільної клітини, за допомогою якої відбувається переміщення вантажу по циклу?
Запишіть формулу для обчислення оцінок вільних змінних в ТЗ.
Як обчислити зміну цільової функції при поліпшенні плану перевезень?
Сформулюйте ознаку альтернативного оптимуму в ТЗ. Як знайти в цьому випадку загальне оптимальне рішення?
Який економічний сенс нерівності? Складіть математичну модель цієї ТЗ. Опишіть процес вирішення даної відкритої транспортної задачі.
Який економічний сенс нерівності? Складіть математичну модель цієї ТЗ. Опишіть процес вирішення даної відкритої транспортної задачі.
Який економічний сенс додаткових змінних в оптимальному плані перевезень відкритих транспортних задач, якщо 1), 2)?
Схожі роботи:
Управленческійрешенія
Реферат >> Держава і право
орієнтація управленческіхрешеній і основні технології розробки управленческогорешенія (РУР) ... .5 1. 1. Формування управленческогорешенія (. Відомі різні способи вирішення цього завдання розподільний метод потенціалів і. і закритого типу 100 тис.
Управленческіерешенія (31)
Контрольна робота >> Менеджмент
рішення. Розглянувши ці відмінні риси прийняття рішень в організаціях, можна дати наступне визначення управленческогорешенія. Управленческоерешеніе. різні способи вирішення цього завдання розподільний метод. ситуаціями (типу - імовірність.
Психологічні аспекти прийняття управленческіхрешеній (1)
Курсова робота >> Психологія
Сама діяльність по прийняттю управленческогорешенія полягає в побудові декількох типів моделей: інформаційної та конкретизованої. Xg> = 0 Відомі різні способи вирішення цього завдання - розподільний метод потенціалів та ін. Як правило.
Шпаргалки по управленческімрешеніям
вибір альтернативи, реалізація рішення. коригування, уточнення, доведення. Типи структур управленческіхрешеній. формальна, її компоненти. Xg> = 0 Відомі різні способи вирішення цього завдання розподільний метод потенціалів та ін. Як правило.
Управленческіерешенія (27)
ринкову. Натомість планово-розподільчої системи почав працювати. роботі щодо прийняття управленческіхрешеній. Виділивши мети і завдання. позначивши об'єкт і. процес прийняття управленческіхрешеній. Стиль керівництва Тіпиуправленческіхрешеній Організаційні.