Двоїсті задачі та їх рішення

 

Кожній задачі лінійного програмування ставлять у відповідність іншу задачу, побудовану на основі тих же даних за визначеними правилами.

Ці правила зводяться до наступного:

§ всі обмеження вихідної задачі приводять до одного виду: у випадку обмеження повинні мати вид нерівностей типу “ ”, у випадку - типу “ ”. Нерівності, що не відповідають цій умові, множать на (- 1);

§ виписують матрицю коефіцієнтів при невідомих і транспонують її ;

§ використовують нові змінні (невід’ємні) і на основі транспонованої матриці формують обмеження двоїстої задачі. Знак нерівностей беруть протилежним стосовно знака нерівностей вихідної задачі. Для правої частини обмежень використовують коефіцієнти цільової функції вихідної задачі;

§ складають цільову функцію двоїстої задачі, беручи для коефіцієнтів праві частини обмежень вихідної задачі. Спрямованість цільової функції двоїстої задачі буде протилежна спрямованості цільової функції вихідної задачі.

Наприклад, для задачі, вирішеної симплексним методом, складемо двоїсту, виходячи з приведених правил.

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

 

	- 1	- 2	- 4
	- 5	- 1	- 5
	- 1
	- 2

 

Запис однієї задачі йде по рядках, іншої – по стовпцях.

 

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

Наприклад, у розглянутій задачі мали:

 

-рядок		-8/3				-1/6	-7/6

 

Додатковими були стовпці , , , тому одержуємо:

.

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

Аналіз матричної гри

Теорія ігор – це математична теорія конфліктних ситуацій. Гра – конфліктна ситуація, регламентована визначеними правилами:

§ порядок виконання ходів;

§ порядок виконання кожного ходу;

§ кількісний результат гри.

Найбільш вивчені матричні ігри. Наприклад,

 

 

 

У цій грі два учасники – сторона і сторона , у кожного учасника по 3 стратегії. Будемо уважати, що матриця характеризує виграш сторони (і відповідно програш сторони ).

 

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

а) Аналізуємо гру з позицій сторони . Якщо гравець вибирає стратегію , то його гарантований виграш (або саме гірше, що його очікує) дорівнює 3. Якщо він вибирає другу стратегію, то гарантована величина виграшу дорівнює 2. Нарешті, якщо він використовує стратегію , то гарантує собі виграш 2. Ці величини є мінімальними в рядках. Очевидно, що з цих гарантованих виграшів сторона намагається вибрати найбільше значення – це 3. Дану величину називають нижньою ціною гри або максиміном і позначають: .

б) Аналізуємо гру з позиції сторони . Якщо гравець вибирає стратегію , то саме гірше для нього – програш 5. Якщо він зупиниться на стратегії , то гірший результат – програш 6. Якщо ж він вибере стратегію , то найгірший для нього результат – програш 5. Ці величини є максимальними в стовпцях. Звичайно, гравець вибере чи стратегію , щоб зменшити гарантований програш – це число 5. Цю величину називають верхньою ціною гри або мінімаксом і позначають: .

в) Ціна гри – це величина, що відображає об’єктивне співвідношення сил, вона завжди задовольняє умові: . У даному прикладі: .

Якщо , то гра має рішення в конкретних стратегіях, що називаються оптимальними. Ці оптимальні стратегії є стійкими, забезпечують рівновагу в грі, а ціна гри називається “ сідловою точкою ”. Якщо такої ситуації нема, то оптимальні стратегії будуть виглядати так:

; .

де – ймовірності стратегій сторони ;

– ймовірності стратегій сторони .

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

Аналіз матричної гри проводиться в два етапи:

§ формулюються двоїсті задачі, вирішують одну з них симплекс-методом і записують рішення обох двоїстих задач;

§ визначають рішення гри.

1. Запишемо дві двоїсті задачі на основі приведеної платіжної матриці:

а) для учасника	б) для учасника

Симплексне рішення зручно проводити для першої задачі, тому що в ній не буде штучних змінних.

Дана задача приймає вигляд:

У результаті використання симплекс-алгоритму одержимо:

 

Базис			– 1	– 1	– 1
-рядок
		2/5		11/5	19/5			–3/5
		3/5		24/5	16/5			–2/5
	– 1	1/5		3/5	2/5			1/5
-рядок	–1/5		2/5	3/5			–1/5
	– 1	2/19		11/19		5/19		–3/19
		5/19		56/19		–16/19		2/19
	– 1	3/19		7/19		–2/19		5/19
-рядок	–5/19		1/19		–3/19		–2/19
	– 1	3/56				24/56	–11/56	–10/56
	– 1	5/56				–16/56	19/56	2/56
	– 1	7/56					–7/56	14/56
-рядок	–15/19				–8/56	–1/56	–6/56

 

Рішення буде мати вигляд:

а)

 

б)

 

2. Знайдемо рішення гри:

а) визначимо ціну гри, – ця величина характеризує кількісний результат гри:

.

б) знайдемо ймовірності стратегій:

; .

; ; .

; ; .

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

; .

Як бачимо, для досягнення оптимального результату стороні рекомендується з 15 разів стратегію використовувати 3 рази, стратегію – 5 разів, стратегію – найчастіше, а саме 7 разів. Для сторони стратегію – рекомендується використовувати рідше всього – 1 раз з 15, набагато частіше потрібно застосовувати стратегію – 6 разів з 15, і найбільше – стратегію . Якщо хтось з учасників відхилиться від цих рекомендацій, то він погіршить тільки своє власне становище.

 

 

Метод потенціалів

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

§ необхідною і достатньою умовою існування рішення є баланс між попитом та пропозицією;

§ по завантажених клітинках визначають систему потенціалів:

,

де – потенціал рядка;

– потенціал стовпця;

– тариф відповідної клітинки.

§ в оптимальному розподілі сума потенціалів рядка і стовпця не повинна перевершувати тариф відповідної незавантаженої клітинки;

§ кількість постачань повинна дорівнювати величині , де - число постачальників, - число споживачів.

Метод потенціалів здійснюється в три етапи:

1. Побудова первісного опорного плану (початковий розподіл вантажів).

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

3. Поліпшення плану перевезень, якщо воно можливо.

Другий і третій етапи повторюються доти, поки рішення не стане оптимальним.

 

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

Початковий розподіл можна виконувати різними способами: способом північно-західного кута, способом найменших тарифів, подвійної переваги, способом Фогеля, способом Лебедєва-Тихомирова й ін. Найбільш простим і легко реалізованим на ЕОМ є спосіб північно-західного кута. Він полягає в тім, що від кожного постачальника, починаючи з першого, вивозять весь вантаж з урахуванням потреби споживачів. Розподіл завершено, якщо весь вантаж від постачальників вивезений, а кожен споживач одержав необхідний обсяг.

Розглянемо приклад: є три постачальники і три споживачі , відомі потужності постачальників, попит споживачів і тарифи на перевіз вантажу (табл. 1).

Таблиця 1

 

Постачальники	Потужність
			50 –	^+(4)
		(3)		(1)	– 1
		(2)	50 +	– 200	– 2
					–

 

Установимо, насамперед, наявність балансу між попитом та пропозицією

250 + 150 + 250 = 650

200 + 250 + 200 = 650

Баланс є. Тепер розподілимо вантаж, починаючи з першої верхньої клітинки, звідси і назва способу – північно-західний кут. Розподіл завершено, необхідно визначити витрати (величину ) і оцінити оптимальність рішення.

.

 

II етап. Оцінка оптимальності рішення

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

; ;

; ; .

Маємо систему з 5 рівнянь з 6 невідомими, тому один з потенціалів приймемо рівним 0. Частіше за все беруть і знаходять всі інші потенціали:

; ; ; ; .

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

; ;

; .

Умова оптимальності для жодної з порожніх клітинок не виконується. Варто поліпшити рішення.

 

III етап. Побудова нового розподілу

З усіх клітинок, для яких умова оптимальності не виконується, вибирають ту, у якій розбіжність найбільша. Якщо таких клітинок декілька, то вибирають клітину з меншим тарифом. Її позначають знаком “+”. Починаючи від обраної клітинки, будують прямокутну фігуру, всі інші вершини якої розташовуються в заповнених клітинках. Знаки вершин чергують.

Прямокутні фігури можуть бути наступних видів:

Рідше зустрічаються фігури такого виду:

 

 

Вид фігури зумовлюється розподілом постачань.

З усіх клітинок, відзначених знаком мінус, вибирають найменший вантаж. Його переміщують уздовж прямокутної фігури, додаючи, якщо стоїть знак “+”, і, віднімаючи, якщо стоїть знак “–”. Усі зміни відображають у новій таблиці. Величини, що не беруть участь у перерозподілі, у нову таблицю переносять без зміни. Звернемося до приклада: у таблиці 1 знаком “–” відзначені дві клітинки, вибираємо найменший вантаж 50 і переміщуємо його уздовж прямокутної фігури. Усі зміни показані у табл. 2. Отримано новий розподіл: необхідно оцінити його, тому повертаємося до II етапу алгоритму.

Таблиця 2

 

Постачальники	Потужність
		200 –	l	+ 50
		(7) +	– 150	(1)
		(6)	+ 100	– 150
					–

 

.

Перевіримо число заповнених клітинок, їх як і раніше 5. Знову знаходимо потенціали, причому можна не складати систему, а використовувати правила:

1. У 1 рядку беремо 0.

2. Невідомий потенціал стовпця дорівнює різниці між тарифом заповненої клітинки і відомим потенціалом рядка.

3. Невідомий потенціал рядка дорівнює різниці між тарифом заповненої клітинки і відомим потенціалом стовпця.

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

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

У нашому прикладі найбільша розбіжність між сумою потенціалів і тарифами – у клітинці (2; 1). Будуємо прямокутну фігуру і зауважуємо, що дві клітинки, відзначені знаком “–”, мають однакову найменшу величину 150, – цей факт веде до виродженого розподілу. І дійсно, після переміщення одержимо таблицю 3, у якій число завантажених клітинок дорівнює 4.

Таблиця 3

 

Постачальники	Потужність
		50 –	+ (2)
			l	l	– 4
		0 +	– 250	l	– 4
				–

 

Виродженість може з’явитися і зникнути при переході від таблиці до таблиці. Щоб продовжити рішення у випадку виродженої задачі, вводять нульові постачання, відповідні клітинки вважають умовно заповненими. Нулів буде стільки, скільки бракує постачань. Їх вписують у клітинки, що мають малі витрати, і при цьому стежать, щоб не виходив замкнутий цикл (прямокутна фігура, у всіх вершинах якої – заповнені клітинки). У даному прикладі варто вписати один нуль і найкраще в клітинку (3; 1). Подальше рішення звичайне: знаходять потенціали, перевіряють умову оптимальності. Після чергового перерозподілу одержимо таблицю 4.

Таблиця 4

 

Постачальник	Потужність
		l
			l	l	– 2
				l	– 2
				–

 

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

Зауваження 1. Якщо ми маємо справу з відкритою транспортною задачею, то для її рішення необхідно спочатку забезпечити баланс між попитом та пропозицією. Для цього вводять додаткового постачальника, якщо попит перевищує пропозицію, у противному випадку вводять додаткового споживача. Якщо додають постачальника, то його “потужністю” буде величина, яку бракує до балансу, транспортні тарифи беруть рівними нулю. Аналогічно діють, якщо додають споживача. Надалі рішення проводять по викладеному вище алгоритму. Уведення додаткового постачальника або споживача має цілком визначене економічне пояснення. У першому випадку ми визначаємо, якому споживачу вигідніше недопоставити вантаж, виходячи з інтересів всіх учасників, у другому випадку – у якого постачальника доцільніше за все залишити частину вантажу.

Зауваження 2. Раніше був докладно розглянутий спосіб північно-західного кута для початкового розподілу вантажів. Число ітерацій (таблиць) можна зменшити, якщо скористатися способом найменших тарифів. Він полягає в аналізі всієї матриці тарифів, виборі найменших значень і максимальному заповненні відповідних клітинок таблиці. Ці дії виконуються доти, поки не буде розподілений весь вантаж і вдоволений попит усіх споживачів. У результаті заповнення однієї з клітинок виключається з розгляду якийсь постачальник або споживач. При цьому додаткові учасники транспортної задачі приймаються до уваги в останню чергу.

Розглянемо приклад транспортної задачі.

 

Постачальники	Потужність

 

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

 

Постачальники	Потужність
			-	-	-
		-
				-	-	-2
			-	-	-
			-1		-

Отриманий план не оптимальний, варто перейти до кращого. Це можна зробити на основі викладеного алгоритму.

 

 

Задачі про призначення

 

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

,

чи ,

де – показники витрат (чи ефективності)

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

§ приходиться вносити в таблицю значну кількість нулів, що викликає деякі утруднення;

§ прямокутна фігура перерозподілу величин частіше за все буває досить складною.

Приклад.

Сім претендентів розподіляються на 7 ділянок діяльності. Розв’язується задача на мінімум витрат. Послідовність використання претендентів і перерозподіли відображені в таблицях 1 – 3.

Таблиця 1

 

ділянки   претенденти
1
								–3
								–1
	+
								–

 

Навчальний розподіл був виконаний по методу найменших тарифів. . Це розміщення виявилося не оптимальним, що привело до необхідності покращення рішення, тобто до перерозподілу претендентів.

Таблиця 2

 

ділянки   претенденти
								–3
								–1
								–2
								–3
		+
								–

В таблиці 2 розподіл потребує поліпшення. .

Таблиця 3

 

ділянки   претенденти
								–1
								–

 

У таблиці 3 умова оптимальності виконується, конкретні призначення помітні. .

Якщо розглядається задача на максимум ефективності використання персоналу, то крім зазначених особливостей істотно міняється алгоритм методу потенціалів:

§ розподіл варто вести за найбільшими показниками ефективності;

§ розташовувати нулі також треба в клітинки з великими тарифами;

§ умова оптимальності протилежна традиційній – сума потенціалів для порожніх клітинок повинна бути не менше тарифу, саме в цьому випадку буде досягнутий максимум.

Приклад.

Розглянемо ту ж саму матрицю тарифів, припускаючи, що в ній зазначені показники ефективності.

Таблиця 1

 

ділянки   претенденти
1
1
							+
								–

 

Таблиця 2

 

ділянки   претенденти