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

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

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

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

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

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

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

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

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

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

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

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

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

Затверджено

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

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

З М І С Т

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

Передмова

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цільова функція: загальний прибуток від реалізації трьох видів продукції: .

Обмеження:

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

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

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

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

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

Введемо додаткові змінні х₄, х₅, х₆. Перейдемо до розширеної задачі у канонічному виді.

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

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

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

,

,

,

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

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

2) Будуємо вектор градієнтного направлення

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

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

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

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

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

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

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

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

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

Складемо модель задачі. Нехай X = (х₁, х₂) – план випуску продукції. Тоді модель прийме вигляд при обмеженнях:

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

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

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

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

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

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

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

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

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

;

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

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

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

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

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

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

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

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

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

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

(на трудові ресурси),

(на напівфабрикати),

(на верстатне

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

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

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

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

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

БП	Сб	В
-40	-50	-100	-80
			2,5	2,5		1,5
Ц.Ф.

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

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

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

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

і так далі

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

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

1) , стовпець, якому належить ця оцінка називається напрямним.

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

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

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

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

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

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

- розв’язувальний елемент;

- колишній елемент;

- елемент напрямного рядку;

- елемент напрямного стовпця;

- новий елемент =

БП	Сб	В
-40	-50	-100	-80
	-100		1,25	1,25		0,75	0,5
			-1				-2
							-2
Ц.Ф.	-5000	-85	-75			-50

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

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

БП	Сб	В
-40	-50	-100	-80
	-100		1,5					-0,25
	-80		-				-
				-				-
Ц.Ф.	-5100	-	-			-

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

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

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

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

за умовами

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

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

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

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

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

Симетричні

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

1)

2)

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

3)

4)

де , , , , .

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

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

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

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

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

,

де – матриця, обернена до матриці Р.

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

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

.

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

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

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

БП	Сб	В	х1	х2	х3	х4
		-1
х3	-1			-2			-
х4
	-1	-2
х3	-1
х2
	-3	-			-

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

Нехай , тоді , , , , , , вирішивши цю систему, отримаємо , , , , , .

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

,

,

,

,

,

Так як є , то план не оптимальний. Знаходимо

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

Виробники	Споживачі	Запаси
В1	В2	В3	В4
	vj ui
А1		100	100	- -4	-
А2		0	-	- -2	150
А3		- -4	20		-
Потреби

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

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

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

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

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

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

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

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

Знайденим в таблиці опорний план оптимальний, оскільки .

Відповідь:

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

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

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

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

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

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

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

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

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

«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 одиниці. Отримуємо потік Х₀ величиною V₀ = 10 одиниць.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7.

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

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

Визначити, скільки гектарів кожної культури на кожному з ділянок слід зайняти так, щоб загальний збір зерна був максимальний.

• ⇐ Назад
• 1
• 23