Короткі теоретичні відомості та вказівки до розв’язання задач

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Запорізький національний технічний університет

МЕТОДИЧНІ РЕКОМЕНДАЦІЇ

до самостійної роботи студентів з дисципліни

«Математичне програмування»

для студентів спеціальності

«Управління трудовими ресурсами» денної форми навчання

Методичні рекомендації до самостійної роботи студентів з дисципліни «Математичне програмування» для студентів спеціальності «Управління трудовими ресурсами» денної форми навчання / Укл.: С.С. Козлова, – Запоріжжя: ЗНТУ, 2009. - 60 с.

Укладачі: С.С.Козлова, ст. викладач

?????????????????

Рецензент: ?????????????

Відповідальний за випуск:

Затверджено

на засіданні кафедри «Інформа-ційні технології в туризмі»

Протокол № ?? від ????????р.

З М І С Т

Передмова………………………………………….………….…..…...... 4
Тематичний план дисципліни ...………………………………….….....5
Короткі теоретичні відомості та вказівки до розв’язання задач…........6
Завдання для самостійних робіт………………………………….…......27
Список рекомендованої літератури ……………………………………56

Передмова

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

Мета курсу «Математичне програмування» – це надання фундаментальних теоретичних знань і практичних навичок з питань постановки та розв'язування оптимізаційних економічних задач засобами математичного програмування.

В процесі засвоєння дисципліни студент повинен:

– розширити та поглибити теоретичні знання з якісних властивостей економічної системи, кількісних взаємозв'язках та закономірностях економічного розвитку;

– оволодіти методологією та методикою побудови, аналізу та застосування математичних моделей економічних процесів;

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

– ознайомитися з основними аналітичними та чисельними методами розв'язування різного класу задач прийняття рішення.

Тематичний план дисципліни

№ з/п Теми лекції (Л) практ., лаб. зан. (ПЗ, ЛЗ)
Математичне програмування – наука про обґрунтування та прийняття рішень.  
Задача лінійного програмування. Графічний метод розв’язання задач лінійного програмування
Симплексний метод розв’язання задач лінійного програмування
Двоїстість у лінійному програмуванні. Економічна інтерпретація двоїстих задач
Транспортна задача. Метод потенціалів розв’язання транспортних задач
Задача про максимальний потік. Угорський метод розв’язання транспортної задачі
Цілочислове програмування. Метод Гоморі та метод віток та меж розв’язання задачі комівояжера.
Дробово-лінійне програмування. Метод Ленд і Дойг
Нелінійне програмування. Метод множників Логранжа.
Динамічне програмування. Функціональне рівняння Белмана
Стохастичне програмування
Елементи теорії ігор.

Короткі теоретичні відомості та вказівки до розв’язання задач

1. Математичне моделювання економічних задач

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

Приклад. Підприємство реалізує продукцію трьох видів: П1, П2, П3. Для цього використовується два обмежених ресурси – корисна площа приміщень, яка з використанням коефіцієнту оборотності становить 460 м2, та робочий час в 500 людино-ч. Товарообіг підприємства повинен бути не більше 240 од. Необхідно розробити план товарообігу, який дає максимум прибутку. Вихідні дані приведені в таблиці.

Ресурси Витрати ресурсів на реалізацію 1 тис. грн. Об’єм ресурсу
П1 П2 П3
Корисна площа, м2 1,5
Робочий час, людино-ч. 1,5
Прибуток, грн.  

Скласти математичну модель задачі та привести її до канонічного виду.

Змінні: х1, х2, х3 – об’єми продукції, які підлягають реалізації.

Цільова функція: загальний прибуток від реалізації трьох видів продукції: Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

Обмеження:

1) обмеження на корисну площу приміщень:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

2) робочий час не повинен перевищувати його запасу:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

3) урахування планового завдання:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

4) природне обмеження полягає в тому, що обсяги реалізації продукції не можуть бути від’ємними:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Таким чином, математична модель задачі має вигляд:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Введемо додаткові змінні х4, х5, х6. Перейдемо до розширеної задачі у канонічному виді.

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

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

2. Графічний метод розв’язання задач лінійного програмування

Якщо задача лінійного програмування має дві змінні, тобто

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ,

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ,

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ,

тоді її графічно можна вирішити згідно наступного алгоритму:

1) Будуємо безліч допустимих розв’язків Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru з врахуванням системи обмежень ( Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ).

2) Будуємо вектор градієнтного направлення Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

3) Проводимо довільну лінію рівня Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru перпендикулярну до вектора Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

4) При рішенні задачі на max переміщаємо пряму Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru у напрямку вектора Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru так, щоб вона зайняла крайнє положення. При подальшому її переміщенні лінії рівня не мають спільних крапок з областю допустимих розв’язків Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . В разі рішення задачі на min лінію рівня Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru переміщуємо в антіградієнтному напрямку.

5) Визначаємо оптимальний план. Можливі наступні випадки:

а) Оптимальний план єдиний. Тоді лінія рівня і область Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru в крайньому положення матимуть одну спільну точку.

б) Оптимальних планів може бути безмежна кількість. В цьому випадку в крайньому положенні лінія рівня проходить через грань області Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

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

г) Задача вирішення не має; оскільки область допустимих розв’язків порожня, тобто система обмежень несумісна.

Приклад: Майстерня виготовляє два види продукції, використовуючи два ресурси: першого виду – 156 одиниць, другого – 63. Прибуток від реалізації одиниці першого виду продукції – 4 грн., другого – 5 грн. Норми витрат представлено в таблиці.

Визначити план випуску, що максимізує прибуток.

Ресурси Витрати на одиницю продукції Об’єм ресурсу
П-1 П-2
1,6
0,5 0,8
Прибуток, грн.  

Складемо модель задачі. Нехай X = (х1, х2) – план випуску продукції. Тоді модель прийме вигляд Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru при обмеженнях:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

С
В
А
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Побудуємо багатокутник розв’язків. Для цього в системі координат х12 на плоскості намалюємо граничні прямі: Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Візьмемо довільну точку площини, наприклад, початок координат і з'ясуємо, яку півплощину визначає відповідне обмеження. Півплощину, визначену відповідним обмеженням, показано на малюнку штрихами. Враховуючи умову невід’ємності багатокутник розв’язків задачі змальований чотирикутником ОАВС.

Далі побудуємо довільну лінію рівня, наприклад Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . Для цього змалюємо вектор градієнтного напрямку Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . Оскільки вектор необхідний лише для визначення напрямку зростання цільової функції, то враховуючи масштаб креслення, можна для більшої наочності побудувати вектор Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , в нашому випадку вектор 10 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . Через початок координат проведемо пряму, перпендикулярно до вектора Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . Пряму Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru переміщаємо паралельно самій собі у напрямі вектора Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru в крайнє положення (точка В). У цій точці функція досягає найбільшого значення. Вирішуючи спільно рівняння прямих АВ і ВС знаходимо координати точки В х1=30, х2=60.

Отже майстерня повинна виготовляти 30 одиниць продукції першого вигляду і 60 – другого. Максимальний прибуток складає 420 грн.

Зауваження. Графічно можна також вирішити завдання лінійного програмування з п>2 змінними, якщо в її канонічному запису число невідомих п і число лінійно незалежних рівнянь т зв'язане співвідношенням п-т£2 (тобто ранг системи обмежений).

3. Симплексний метод розв’язання задач лінійного програмування

Алгоритм симплекс – методу вирішення ЗЛП

1. Побудова початкового опорного плану:

а) приведення задачі до канонічного вигляду;

б) приведення системи обмежень до переважного вигляду

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ;

в) побудова першої симплексної таблиці;

г) перевірка умови оптимальності;

2. Перехід до нового опорному плану.

а) вибір напрямного стовпця;

б) вибір напрямного рядка;

а)б) = > вибір розв’язувального елементу;

в) симплексні перетворення і побудова 2-ой симплексної таблиці;

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

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

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

При обмеженнях:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru (на трудові ресурси),

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru (на напівфабрикати),

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru (на верстатне

устаткування),

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

1) Перейдемо до канонічного вигляду:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

2) Додамо до лівих частин обмежень додаткові невід’ємні змінні:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Тепер система обмежень має переважний вигляд

3) Будуємо симплексну таблицю

БП Сб В Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
-40 -50 -100 -80
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 2,5 2,5 1,5
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Ц.Ф.

Сб – стовпець коефіцієнтів базисних в ц.ф.

БП – базисні змінні; змінні що входять в переважні обмеження;

В – стовпець вільних членів в системи обмежень, представлених в переважному вигляді.

На перетині стовпців і рядків розташована матриця коефіцієнтів системи обмежень. Рядок "Ц.Ф." (Z-рядок або індексний рядок) в ній розташовані коефіцієнти Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru і Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , які розраховуються по формулах:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru і так далі

Початковий опорний алан задачі Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . Всі оцінки вільних змінних Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . План не оптимальний.

Виберемо найбільшу оцінку.

1) Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , стовпець, якому належить ця оцінка називається напрямним.

2) Елементи стовпця В ділимо на відповідні елементи напрямного стовпця. Рядок, що містить найменше з набутих значень, називається напрямним. Елемент, що стоїть на перетині напрямного рядка і напрямного стовпця називається розв’язувальним.

3) Будуємо другу симплексну таблицю

а) Елементи стовпців В і Сб – заповнюються відповідно до аналізу попередньої таблиці

б) Елементи напрямного рядка діляться на розв’язувальний елемент і записуються у відповідному по номеру рядку нової таблиці.

у) Елементи напрямного стовпця дорівнюють нулю (у новій таблиці), за винятком елементу відповідного місцю розв’язувального елементу. Цей елемент дорівнює одиниці.

г) Щоб знайти будь-який інший елемент нової таблиці, скористаємося правилом чотирикутника

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - розв’язувальний елемент;

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - колишній елемент;

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - елемент напрямного рядку;

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - елемент напрямного стовпця;

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - новий елемент = Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

БП Сб В Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
-40 -50 -100 -80
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru -100 1,25 1,25 0,75 0,5
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru -1 -2
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru -2
Ц.Ф. -5000 -85 -75 -50

4) План не оптимальний, оскільки існують позитивні оцінки вільних змінних.

Будуємо нову таблицю, аналогічно попередній.

БП Сб В Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
-40 -50 -100 -80
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru -100 1,5 -0,25
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru -80 - Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Ц.Ф. -5100 - Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Оптимальний план завдання Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , так як оцінки вільних змінних індексного рядка останньої симплексної таблиці відмінні від нуля, то завдання має єдине вирішення Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

4. Двоїсті задачі лінійного програмування

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

Так, для початкової задачі, яка полягає у максимізації функції

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

за умовами

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Двоїстою буде наступна задача:

знайти мінімум функції

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

при обмеженнях

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Двоїста пара задач лінійного програмування може бути симетричною і несиметричною. В симетричних задачах систем обмежень здається у вигляді нерівностей і на змінні накладаються умови невід’ємності. У несиметричних задачах система обмежень задається рівностями, а у двоїстій – нерівностями, причому змінні останньої можуть бути від’ємними.

Пари двоїстих задач можуть бути записані так:

Симетричні

Пряма Двоїста

1) Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

2) Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Несиметричні

3) Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

4) Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

де Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

Наприклад, маємо задачу

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Запишемо її у вигляді (1)

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

тоді двоїстою буде задача:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

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

Крім того, розв’язуючи симплекс-методом початкову задачу, можна одночасно отримати оптимальний розв’язок двоїстої. Нехай Х* – оптимальний план початкової задачі, а Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru – базисні змінні в останній симплекс-таблиці. Позначимо через С* – матрицю-рядок з коефіцієнтів цільової функції початкової задачі при цих базисних змінних, а через Р – матрицю коефіцієнтів при цих змінних в системі обмежень початкової задачі. Тоді оптимальний розв’язок Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru двоїстої задачі можна знайти за формулою:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ,

де Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru – матриця, обернена до матриці Р.

Приклад. Для даної задачі записати двоїсту і знайти її розв’язок.

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Розв’язання. Двоїста задача полягає в знаходженні значення функції Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru за умовами

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

Оптимальний розв’язок цієї двоїстої задачі знайдемо графічним методом.

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

А
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

З малюнка видно, що максимального значення функція Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru досягає в точці А. Таким чином, Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru є оптимальним планом, при якому Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

Розв’яжемо тепер двоїсту задачу іншим методом. По-перше, визначимо оптимальний план початкової задачі за допомогою симплекс-методу.

БП Сб В х1 х2 х3 х4 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
-1
х3 -1 -2 -
х4
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru -1 -2  
х3 -1 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru  
х2 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru  
Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru -3 - Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru  

Отже, Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . В останній симплекс-таблиці базисні змінні – Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . Тоді з коефіцієнтів при цих змінних у цільовій функції складемо Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , а з коефіцієнтів в системі обмежень – Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . Обчислимо обернену матрицю: Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

Тоді оптимальний розв’язок двоїстої задачі:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

5. Транспортна задача лінійного програмування

Алгоритм знаходження оптимального розв’язку транспортної задачі:.

1) Знаходження початкового опорного плану (методами північно-західного кута, мінімальної вартості)

2) Побудова системи потенціалів

3) Перевірка виконання умови оптимальності для незанятих кліток

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

4) Перехід до кращого опорного плану

а) вибір клітин, в яку необхідно зробити перевезення;

б) побудова циклу і визначення величини перерозподілу вантажу;

в) контроль обчислень;

5) Зміна системи потенціалів, і перехід до п.3.

Умови в таблиці

Виробники Споживачі Запаси
В1 В2 В3 В4
А1
А2
А3
Потреби

Методом мінімальної збалансованості знаходимо початковий опорний план.

Будуємо систему потенціалів Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , виходячи з умови Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru для зайнятих клітин в опорному плані.

Виробники Споживачі Запаси
В1 В2 В3 В4
А1 - -
А2 - -
А3 - -
Потри

Нехай Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , тоді Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , вирішивши цю систему, отримаємо Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

Обчислюємо значення Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru для незанятих клітин (записуємо в лівий нижній кут клітин), якщо все Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , то план оптимальний; якщо існують Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , то план не оптимальний і переходимо до побудови кращого опорного плану.

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ,

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ,

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ,

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ,

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ,

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Так як є Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , то план не оптимальний. Знаходимо Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Будуємо цикл з вершинами у вибраній клітці і позначаємо його вершини знаками.

Виробники Споживачі Запаси
В1 В2 В3 В4
  vj ui Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
А1 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 100 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 100 - -4 -
А2 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 0 - - -2 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 150
А3 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - -4 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 20 -
Потреби

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - величина перерозподілу вантажу. Робимо зрушення по циклу на величину Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , переходимо до нового оптимального плану, перехід здійснюємо по формулі:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Виробники Споживачі Запаси
В1 В2 В3 В4
  vj ui Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
А1 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 80 - -2 - Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 1
А2 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 20 - -
А3 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - -6 -  
Потреби

Складаємо нову систему потенціалів. Знаходимо оцінки вільних клітин Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru вони пишуться в лівому нижньому кутку. Умова оптимальності порушується в клітці (1;3). Включаємо її в набір заповнених. Будуємо цикл перерахунку і робимо зрушення по циклу на величину постачання Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

Виробники Споживачі Запаси
В1 В2 В3 В4
  vj ui Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
А1 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - -1 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 120 - -3 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru 80  
А2 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - -
А3 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - -6 - -1  
Потреби

Обчислення аналогічні обчисленням для попередньої таблиці.

Порушується оптимальність в клітці (2;2). Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru , робимо зрушення по циклу, на величину Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru .

Виробники Споживачі Запаси
В1 В2 В3 В4
  vj ui Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru
А1 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - - -3  
А2 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru   - -1 - -1
А3 Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru - -5 - -1  
Потреби

Обчислення аналогічні попереднім обчисленням.

Знайденим в таблиці опорний план оптимальний, оскільки Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Відповідь:

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

6. Задача про максимальний потік

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

Алгоритм визначення максимального потоку

1) Побудувати початковий допустимий план-потік. Вирішення можна почати, наприклад, з нульового потоку.

2) Перевіряємо, чи немає ненасичених шляхів, які йдуть з S в S'. Якщо вершина S' не потрапила в безліч вершин S, досяжних по ненасиченим ребрах з S, то побудований потік максимальний. Завдання вирішене. Якщо вершина S' потрапила в безліч S, то потік можна збільшити.

3) Виділяємо шлях, що складається з ненасичених ребер, ведучий з S в S'. Збільшуємо потік цього шляху на величину Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru . Переходимо до нового потоку, збільшеного на Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru і так далі

Ідею алгоритму можна, реалізувати табличним способом або графічно. Розгледимо графічний спосіб рішення задачі.

Приклад. Задана мережа, числа, записані над ребрами, означають пропускну спроможність ребер

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Будуємо початковий допустимий потік Х0, для цього розглянимо, наприклад, шляхи

«1» S-1-3-2-s' min = {10, 7, 6, 8} = 6

«2» S-4-5-s' min = {4, 10, 13} = 4

По шляху «1» пропустили 6 одиниць. По шляху «2» пропустили 4 одиниці. Отримуємо потік Х0 величиною V0 = 10 одиниць.

Мережа, відповідна потоку Х0 намальована на рис.1

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

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

Пунктиром малюються насичені ребра, тобто ребра, потік через які рівний їх пропускній спроможності.

Перевіряємо, чи немає ненасичених шляхів. Такі шляхи є, тобто початковий потік можна збільшити. Для цього вибираємо шляхи «3», «4».

«3» S-1-2-s' min = {4, 5, 2} = 2

«4» S-3-s' min = {2, 2} = 2

По шляху «3» пропускаємо потік величиною 2 одиниці, а по шляху «4» також 2 одиниці. Отримаємо потік в мережі величиною V1 = 14 одиниць, йому відповідає мережа на рис.2.

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Оскільки більше ненасичених шляхів з вершин S в S' немає, то отриманий потік є max і задача вирішена.

Завдання для самостійних робіт

Завдання 1. Побудувати економіко-математичну модель задачі

1. Для виготовлення 3-х видів виробі А, В і С використовується токарне, фрезерне, зварювальне та шліфувальне обладнання. Витрати часу на обробку одного виробу для кожного з типів обладнання вказані в таблиці. Там же вказаний загальний фонд (ЗФ) робочого часу кожного типу обладнання, а також прибуток від реалізації одного виробу кожного виду

  А Б С ЗФ
Фрезерне
Токарне
Зварювальне
Шліфувальне
Прибуток  

Визначити план випуску підприємства, щоб прибуток від реалізації був максимальним.

2. Для виробництва n видів виробів підприємство використовує m груп взаємозамінного обладнання. Виробів i-го виду необхідно виготовити Bi одиниць ( Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ), причому j-а група обладнання може бути зайнята виготовленням виробів не більше, ніж аj годин ( Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ). Час виготовлення одного виробу i-го виду на j-й групі устаткування дорівнює аij годинам, а ціна виробництва дорівнює сij грн. Визначити, скільки виробів даного виду з використанням кожної з груп обладнання слід виготовити, щоб виробити потрібну кількість виробів кожного виду при найменшій загальній вартості їх виготовлення.

3. При вирощуванні певної культури може бути використаний i-й вид добрив в кількості не більшій ніж bi кг ( Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ). Уся посівна площа містить n ґрунтово-кліматичних зон, причому площа j-ї зони дорівнює dj га ( Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru ).Внесення на кожен гектар площі j-ї зони 1 кг добрив i-го виду збільшує середню врожайність на сij центнерів. Потрібно розподілити виділений фонд добрив між посівними зонами так, щоб сумарний приріст врожайності культур за рахунок внесення добрив був максимальним.

4. Для виробництва чавунного лиття використовується n різних вихідних шихтових матеріалів (чавун різних марок, сталевий брухт, Ферофосфор та ін.). Хімічний склад чавунного лиття визначається вмістом в ньому хімічних елементів, (кремнію, марганцю, фосфору та ін.). Готовий чавун повинен мати строго визначений хімічний склад, який задається величинами Нj, що представляють собою частки (у %) j-го хімічного елемента в готовому продукті. При цьому відомі величини: hij – зміст (у %) j-го хімічного елемента в i-му вихідному шихтовому матеріалі; сi – ціна одиниці кожного i-го шихтового матеріалу. Визначити склад шихти, що забезпечує отримання лиття заданої якості при мінімальній загальній вартості використовуваних шихтових матеріалів.

5. З листового прокату потрібно викроїти заготовки чотирьох видів. Один лист довжиною 184 см можна розрізати на заготовки довжиною 45, 50, 65 і 85 см. Всього заготовок кожного виду необхідно відповідно 90, 96, 88, 56 шт. Способи розрізу одного листа на заготовки і величина відходів при кожному способі наведені в таблиці. Визначити, яка кількість аркушів по кожному із способів слід розрізати, щоб отримати потрібну кількість заготовок даного виду при мінімальних загальних відходах.

Довжина заготовки (см) Кількість заготовок, яка викроюється з одного листа при розрізі способом
- -
- - - -
- - -
- - -
Відходи (см)

6. Для виробництва трьох видів виробів А, В і С використовується три різних види сировини. Кожен з видів сировини може бути використаний у кількості, відповідно не більшій 180, 210 і 244 кг. Норми витрат кожного з видів сировини на одиницю продукції даного виду і ціна одиниці продукції кожного виду наведені в таблиці. Визначити план випуску продукції, при якому забезпечується її максимальна вартість.

Вид сировини Норми витрат сировини (кг) на 1 од. продукції
А В С
Ціна од. продукції (грн.)

Пароплав може бути використаний для перевезення 6 найменувань вантажу, маса, об'єм і ціна одиниці кожного з яких наведені в таблиці. На пароплав може бути занурено не більше 500 т вантажу загальним обсягом, що не перевищує 600 м3. Визначити, скільки одиниць кожного вантажу слід помістити на пароплав так, щоб загальна вартість розміщеного вантажу була максимальною.

7.

Параметри одиниці грузу Номер грузу
Маса (т)
Об’єм (м3)
Ціна (тис.грн.) 2,8 3,3 3,5 4,7 3,9 4,0

8. В аеропорту для перевезення пасажирів по n маршрутами може бути використано m типів літаків. Місткість літака i-го типу дорівнює аi чоловік, а кількість пасажирів, що перевозяться по j-му маршруту за сезон, становить bj чоловік. Витрати, пов'язані з використанням літака i-го типу на j-му маршруті, складають сij грн. Визначити, скільки літаків цього типу і на якому з маршрутів слід використовувати, щоб задовольнити потреби в перевезеннях при найменших загальних витратах.

9. .Є три ділянки землі, на яких можуть бути засіяні кукурудза, пшениця, ячмінь і просо. Площа кожної з ділянок відповідно дорівнює 600,180 і 220 га. З урахуванням наявності насіння кукурудзи, пшениці, ячменю і проса слід відповідно засіяти 290, 280, 110 і 420 га. Врожайність кожної з культур для кожного з ділянок різна і задається матрицею

Короткі теоретичні відомості та вказівки до розв’язання задач - student2.ru

Наши рекомендации