Рішення задач лінійного програмування в середовищі Maple

МІНІСТЕРСТВО АГЕНСТВО ОСВІТИ

Псковський державний педагогічний університет

Рішення задач лінійного програмування в середовищі Maple

Курсова робота

Студента 4 курсу

фізико-математичного

факультету відділення «математика»

Ганяла Аршака Арзумановіча

Науковий керівник

Матвєєв Володимир Олександрович

Псков

2008

Зміст

§ 1. Бібліотека «simplex» пакета Maple

§ 2. Постановка завдання лінійного програмування для N змінних

§ 3. Постановка Транспортної завдання (ТЗ) для n змінних

§ 4. Приклад рішення завдання лінійного програмування

§ 5. Приклад рішення Транспортної завдання

Список літератури

§ 1. Бібліотека «simplex» пакета Maple

Бібліотека «simplex» - призначена для оптимізації лінійних систем з використанням симплексного алгоритму. Особливість її в тому, що є можливість виконувати оцінки проміжних етапів симплексного алгоритму, наприклад, визначати базисні змінні і т.п.

Після підключення бібліотеки командою with (simplex) користувачу стає доступні функції і опції, зазначені в наступній таблиці.

basis	Знаходить базисні змінні
cterm	Виводить список елементів вектора ресурсів
display	Представляє систему в матричній формі
dual	Перетворює дану задачу в двоїсту задачу лінійного програмування
feasible	Повертає true - якщо рішення існує, і false - якщо немає
maximize	Знаходить максимум цільової функції
minimize	Знаходить мінімум цільової функції
NONNEGATIVE	Опція: вказівка ​​на умова не заперечності всіх змінних
setup	Приводить систему обмежень до стандартної форми
standardize	Перетворює систему обмежень у пари нерівностей

§ 2. Постановка завдання лінійного програмування для N змінних

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

Побудова економіко-математичної моделі

n - число різних видів продукції.

m - число різних ресурсів.

aij - обсяг i-того ресурсу, який витрачається на виробництво однієї одиниці j-того виду продукції i = 1 .. m, j = 1 .. n.

Xj - обсяг (кількість одиниць) j-того виду продукції у виробничому плані підприємства (j від 1 до n).

Прибуток позначимо F, тоді F = c ₁ X ₁ + c ₂ X ₂ +...+ c _n X _n -> = max

Складемо обмеження для першого ресурсу:

а ₁₁ - обсяг першого ресурсу, який витрачається на виробництво однієї одиниці першого виду продукції;

а ₁₁ Х ₁ - обсяг першого ресурсу, який потрібно на виготовлення Х ₁ одиниць першого виду продукції;

а ₁₂ Х ₂ - обсяг першого ресурсу, який потрібно на виготовлення Х ₂ одиниць другого виду продукції;

а _1n Х _n - обсяг першого ресурсу, який потрібно на виготовлення Х _n одиниць n-ого виду продукції;

а ₁₁ Х ₁ + a ₁₂ X ₂ +...+ a _1n X _n - обсяг першого ресурсу, який потрібно на виготовлення продукції, отже, ми маємо такі обмеження:

а ₁₁ Х ₁ + а ₁₂ +...+ а _1n X _n <= b ₁

Аналогічно для інших ресурсів:

а ₂₁ Х ₁ + а ₂₂ +...+ а _2n X _n <= b ₂

а ₃₁ Х ₁ + а ₃₂ +...+ а _3n X _n <= b ₃

.........................................

а _m1 Х ₁ + а _m2 +...+ a _mn X _n <= b _m

Крім того, кількість випущеної продукції не може бути негативною, отже, Х _1> = 0, X _2> = 0, ..., X _n> = 0.

§ 3. Постановка Транспортної завдання (ТЗ) для n змінних

Нехай є кілька постачальників однорідної продукції (кожен з певним запасом) і кілька споживачів цієї продукції (з відомими потребами у кожного). Задана також мережа комунікацій (доріг, річок, повітряних ліній і т.д.) зв'язує кожного постачальника з кожним споживачем. На кожній комунікації задана ціна перевезення - вартість перевезення одиниці продукції. Якщо будь - яка комунікація відсутня, то вважаємо, що вона є, але ціну перевезення на ній встановлюємо рівній нескінченності (+ ∞). Ця угода зробить невигідним перевезення по ній і автоматично виключить дану комунікацію з плану перевезень.

Таким чином, потрібно скласти план перевезень продукції від постачальників до споживачів так, щоб потреби споживачів були б задоволені за рахунок вивезення запасу від постачальників. Мета - мінімізація сумарної вартості всіх перевезень.

Транспортні задачі бувають:

1) відкриті m ≠ n (сумарний запас продукції, що є у постачальників, не збігається з сумарною потребою в продукції у споживачів.)

2) закриті m = n (сумарний запас продукції, що є у постачальників, збігається з сумарною потребою в продукції у споживачів.)

Метод потенціалів «працює» тільки для закритих ТЗ, причому, закрита ТЗ завжди можна вирішити.

Відкриту ТЗ зводять до закритої ТЗ шляхом додавання до сумарного запасу продукції або сумарної потреби продукції відсутніх одиниць до рівності сумарного запасу продукції та сумарної потреби продукції.

Закрита транспортна задача формулюється як Завдання Лінійного Програмування (ЗЛП) наступного вигляду:

, Де

- Запас i - го постачальника

- Потреба j - го споживача

- Ціна перевезення одиниці продукції з комунікацій (i, j)

(Від i - го постачальника до j - му споживачеві)

- Обсяг перевезення продукції (невідомий) з комунікацій (i, j).

Для виведення критерії оптимальності транспортної задачі побудуємо двоїсту задачу.

Структура матриці обмежень транспортної задачі така, що стовпець, відповідної змінної містить рівно два ненульових елементи: одиницю у рядку з номером i і одиницю у рядку m + i.

Вектор двоїстих змінних Y = ( , ..., , , ..., ) Має m + n компонент (по числі обмежень ТЗ), які називаються потенціалами: змінні , , ..., - Потенціали постачальників змінні , ..., - Потенціали споживачів.

Використовуючи схему для побудови двоїстої задачі до ЗЛП у стандартній формі, маємо:

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

.

Невідомі потенціали і (Їх загальна кількість дорівнює m + n) можуть бути знайдені (і саме так відшукуються) з умови рівності нулю оцінок для базисних змінних (заповнених клітин таблиці) ТЗ (таких рівностей (m + n - 1), що випливає з зауваження нижче).

,

для заповнених клітин (i, j) таблиці ТЗ.

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

§ 4. Приклад рішення завдання лінійного програмування

Вирішимо задачу лінійного програмування симплекс - методом:

f (x) = 2 x ₁ + 3 x ₂ + 4 x ₃ → max

3x ₁ + x ₂ + 3x ₃ <= 5

5 x ₁ + 4 x ₂ + 4 x ₃ <= 12

2 x ₁ + x ₂ + ₂ x ₃ <= 8

x _1> = 0; x _2> = 0; x _3> = 0;

Дані завдання заносимо в симплекс таблицю.

x1	x 2	x 3	x 4	x 5	x 6	значення	базис	оцінка
3	1	3	1	0	0	5	x 4	5 / 3
5	4	4	0	1	0	12	x 5	3
2	1	2	0	0	1	8	x 6	4
2	3	4	0	0	0	0	- F

У цій таблиці перша, друга і третя рядки відповідають обмеженням завдання, останній рядок - функція мети. Це оціночна рядок. Значення функції мети беремо 0. Виділяємо базисні змінні. Ця змінна перебувати в стовпці, для якої є одна одиниця, решта нулі. У стовпці «базис» відзначаємо однойменні змінні в тому рядку, де розташована ця єдина одиниця. Решта змінні називаються вільними.

За заповненої симплекс таблиці визначаємо рішення, відповідне цієї (нульовий) ітерації. Вільні змінні рівні 0. Базисні перемінні і значення функції знаходимо з таблиці. Вони представлені в стовпці «значення». Відзначимо, що значення функції мети беремо з протиставленим знаком. Отже, x ° = (0,0,0,5,12,8) f ° = 0.

У оціночної рядку є позитивні числа. Значить, рішення можна поліпшити. Вибираємо найбільше з позитивних чисел. Якщо таких чисел декілька - беремо будь-яке з них. Відповідний стовпець називають провідним. По провідному стовпа і стовпцем «значення» визначаємо оцінку для кожного рядка. Число з шпальти «значення» ділимо на рядок. За умовою задачі це позитивне число. Оголошуємо провідною рядок ту, оцінка у якої найменше позитивне число.

У першій таблиці провідна рядок і стовпець виділено кольором. На їх перетині знаходиться провідний елемент. У нашому випадку це 3.

Переходимо до першої ітерації. Її суть полягає в тому, щоб вільну x _{3 Зробіть} базисної, а базисну змінну x ₄ - вільною. У таблиці виконуємо перетворення аналогічні елементарним рядковим перетворення аналогічні елементарним рядковим перетворенням в методі Гаусса при вирішенні системи лінійних рівнянь. В результаті перетворень отримаємо:

x1	x 2	x 3	x 4	x 5	x 6	значення	базис	оцінка
1	1 / 3	1	1 / 3	0	0	5 / 3	x 3	5
1	8 / 3	0	-4 / 3	1	0	16 / 3	x 5	2
0	1 / 3	0	-2 / 3	0	1	14 / 3	x 6	1 квітня
-2	5 / 3	0	-4 / 3	0	0	-20 / 3	- F

З таблиці знаходимо базисні змінні і значення функції x ¹ = (0,0,5 / 3,0,16 / 3,14 / 3) f ¹ = 20 / 3. Цей результат можна перевірити. Отримані результати повинні задовольняти функції мети в канонічної (стандартною) задачі лінійного програмування. У оціночної рядку є позитивні числа. Значить, рішення можна поліпшити. Аналогічно будуємо наступну таблицю:

x1	x 2	x 3	x 4	x 5	x 6	значення	базис	оцінка
5 / 8	0	1	1 / 2	-1 / 8	0	1	x 3	-
3 / 8	1	0	-1 / 2	3 / 8	0	2	x 2	-
-1 / 8	0	0	-1 / 2	-1 / 8	1	4	x 6	-
-21 / 8	0	0	-1 / 2	-5 / 8	0	- 10	- F

У оціночної рядку цієї таблиці всі елементи не позитивні. Це й означає, що симплекс метод завершений. Результат останньої ітерації дає відповідь на поставлене завдання.

f * = 10 x * = (0,2,1)

§ 5. Приклад рішення Транспортної завдання

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

КРОК 1. Побудова початкового плану перевезень.

КРОК 2. Перевірка поточного плану на оптимальність.

Якщо план оптимальний, то алгоритм завершено.

КРОК 3. Поліпшення плану перевезень. Перехід до кроку 1.

Опишемо алгоритм по кроках, ілюструючи кожний крок

КРОК 1. Побудова початкового плану перевезень.

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

Клітка (i, j) таблиці відповідає комунікації, що зв'язує i-го постачальника з j-м споживачем.

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

а) число заповнених клітин було (m + n -1). (Тоді план перевезень буде відповідати базисному рішенням ЗЛП);

б) сума перевезень в будь-якому рядку повинна дорівнювати запасу відповідного постачальника, а сума перевезень в кожному стовпці дорівнює потреби споживача. (Умова виконання обмежень ТЗ). Існує кілька способів знаходження початкового рішення, які відрізняються тільки вибором клітини, в яку призначається чергова перевезення. Так, у способі північно-західного кута (СЗУ) для чергового призначення перевезення вибирається ліва верхня клітина таблиці (при цьому ніяк не враховуються ціни перевезень). Навпаки, у способі мінімальної вартості (МС) для заповнення вибирається клітина поточної таблиці з мінімальною ціною перевезення, що в більшості випадків (але не завжди) призводить до більш дешевого (а значить і більш близького до оптимального) початкового плану перевезень.

Ми будемо користуватися способом мінімальної вартості (МС).

Викладемо тепер алгоритм знаходження початкового рішення.

КРОК 1. Певним способом вибираємо клітину в поточній таблиці. Нехай вона має індекси (i, j) (i-номер постачальника, j - номер споживача).

КРОК 2. В якості перевезень в цю клітку призначаємо найменшу з a _i і потреби bj.

x _ij = min { a _i, bj}

КРОК З. Зменшимо запас a _i і потреба bj на величину перевезення x _ij, тобто

a _i = a _i - x _ij,

bj = bj - x _ij

КРОК 4. При вичерпанні запасу (a _i = 0) забороняємо до перевезення залишилися вільні клітини i-го рядка, а при вичерпанні потреби

(Bj = 0) забороняємо такі ж клітини в j-му стовпці.

У разі одночасного вичерпання запасів потреб (ai = bj = 0) забороняємо перевезення або в рядку (тоді вважаємо, що у споживача залишилася потреба в кількості, що дорівнює нулю, яку необхідно задовольнити), або у стовпці (у цьому випадку вважаємо, що у постачальника залишається запас рівний нулю, який необхідно вивезти). Це робиться для того, щоб при одночасному заборону перевезень в рядку і стовпці кількість заповнених клітин таблиці не стало меншим, ніж m + n -1.

Отримаємо нову поточну таблицю, в яку не входять заповнені і заборонені клітини. Якщо таблиця не порожня, переходимо до кроку 1. (При вичерпанні таблиці - кінець).

Спосіб мінімальної вартості

1.Клеткі з мінімальною ціною (3,1), (3,2) і (3,3). Вибираємо, наприклад, (3,2). (Далі всі кроки, як в попередньому способі).

2. x ₃₂ = min {50,60} = 50

3. A ^_'3 = 50-50 = 0, ^b' ₂ = 100-50 = 50

4.Запрещаем рядок 3.

1. Клітка з min ціною ~ (2,3)

2. x ₂₃ = min {70,80} = 70

3. a ₂ = 70-70 = 0, b _'3 = 80-70 = 10

4. Забороняємо рядок 2.

	1	2	3
60	5 60	10	12
Χ	8 -	6 -	4 70
Χ	0	0 50	0 -
		50	10

1. Клітка з min ціною ~ (1,1)

2. x ₁₁ = min {120, 60} = 60

3. a _{1 '} = 120-60 = 60, b _{1 '} = 0

4.У першому стовпці забороняти вже нічого. Поточна таблиця містить дві клітини (1,2) і (1,3).

1.Вибіраем клітину (1,2)

_2. X ₁₂ = min {110,100} = 100

3. A ₁ = 110-100 = 10, b ^_'1 = 0

4.Текущая таблиця містить одну клітку (1,3).

1. Вибираємо останню клітину (1,3)

2. x ₁₃ = min {10,10} = 10

3.a ₁ ^'= b ₃ = 0

4.Табліца вичерпана. Кінець.

Переходимо до опису наступного кроку методу потенціалів.

КРОК 2. Перевірка поточного плану на оптимальність.

Ознакою того, що поточний план перевезень є оптимальним, служить умова

(1) u _i + vj-c _ij ≤ 0

яке виконується для всіх клітин таблиці. Невідомі тут величини u _i і vj (звані потенціалами) визначаються з умов

(2) u _i + v _j = c _ij

Умова (1) означає неможливість появи "спекулятивної" ціни. Сама ж назва "потенціали" запозичено з фізичного закону про те, що робота з переміщення заряду в електростатичному полі дорівнює різниці потенціалів в даних точках поля (У нас: "... ціна перевезення одиниці продукції з комунікації дорівнює різниці цін в кінці і на початку шляху ")

Так як заповнених клітин в таблиці (m + n -1) штук, а невідомих і (m + n) штук, то для їх визначення є система з (m + n -1) рівнянь відносно (m + n) невідомих. Щоб знайти рішення (хоча б яке-небудь) такої системи, досить покласти одне з невідомих (довільне) рівним деякому довільно вибраному числу. Тоді інші визначаються єдиним чином. Можна вирішувати цю систему безпосередньо (продовжуємо працювати з нашим "старим" прикладом і знайдемо потенціали для початкового плану, побудованого способом МС).

Заповнені клітини Рівняння

(1,1) u ₁ + v ₁ = 5

(1,2) u ₁ + v ₂ = 10

(1,3) u ₁ + v ₃ = 12

(2,3) u ₂ + v ₃ = 4

(3,2) u ₃ + v ₂ = 0

Поклавши, наприклад, невідоме u ₁ дорівнює 0 (через нього можна з перших трьох рівнянь знайти v _1, v ₂ і v _3). Послідовно з них знаходимо u _2, u _3.

Цей метод можна сформулювати у вигляді єдиними правилами:

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

Застосуємо це правило для визначення u і v в нашому прикладі і отримаємо:

u ₁ = 0, u ₂ =- 8, u ₃ =- 6

v ₁ = 5, v ₂ = 10, v ₃ = 12

Переходимо до перевірки умов оптимальності (1). Досить перевіряти їх для незаповнених клітин, так як для клітин заповнених ці ​​умови виконуються як рівності. Для перевірки береться незаповнена клітина, складаються відповідні їй потенціали (перший елемент рядка і останній елемент стовпця) і з них віднімається ціна перевезення в даній клітині. Якщо отримане число негативне (або нуль), то оптимальність в даній клітці не порушується (в разі виконання умови (1) для всіх незаповнених клітин, маємо оптимальний план перевезень). Якщо ж у таблиці зустрілася хоча б одна клітина, для якої це число позитивно, тоді рішення не є оптимальним і може бути покращено.

Перевіримо на оптимальність наявне рішення

(2,1) u ₂ + v ₁ - c ₂₁ =- 8 +5-8 =- 11 <0

(2,2) u ₂ + v ₂ - c ₂₂ =- 8 +10-6 =- 4 <0

(3,1) u ₃ + v ₁ - c ₃₁ =- 10 + 5-0 =- 5 <0

(3,3) u ₃ + v ₃ - c ₃₃ =- 10 +12-0 = 2> 0

Отже, умова оптимальності порушено в клітині (3,3).

Наявний план перевезень можна поліпшити.

Дамо опис заключного кроку алгоритму методу потенціалів.

КРОК 3 Поліпшення плану перевезень.

Поліпшення плану відбувається шляхом призначення перевезення θ> 0 в ту клітку (i, j) таблиці, в якій порушилося умова оптимальності. Але призначення ненульовий перевезення порушує умови балансу вивезення продукції від постачальника i (вивозить весь запас і ще плюс θ> 0) і умови балансу привозу продукції до споживача j (отримує все що можна і ще плюс θ> 0). Умови балансу відновлюють шляхом зменшення вивозу від i-постачальника до якогось іншому споживачу j (зменшують на θ перевезення в якийсь заповненої клітці (i, j) рядки i). При цьому порушується баланс привозу продукції до споживача j (отримує на θ менше, ніж йому потрібно). Відновлюють баланс у стовпці j, тоді він порушується в деякій рядку i і т.д. до тих пір, поки цикл переміщення перевезень не замкнеться на клітці, в якій порушувалося умова оптимальності. Продемонструємо ці міркування на нашому прикладі.

1. Оптимальність порушена в клітці (3,3). Призначимо в неї перевезення θ> 0 (+ θ означає, збільшення на θ).

2.Нарушается баланс вивезення від постачальника 3 (вивозить 50 + θ, а це більше його запасу!). Зменшуємо на θ перевезення в заповненій клітці рядка 3 (поза заповненої зменшувати не можна, так як це призведе до негативної перевезення).

Розглянемо ті клітини циклу в яких зменшуємо на θ перевезення і беремо мінімум з вичетаемих, у нас це min {10 - θ, 50 - θ} = 10.

І дане число треба підставити в цикл

Список літератури

1. Матвєєв В.А. Кінцеві безкоаліційний ігри та рівноваги. Псков, 2004,176 с.

2. Аладов В.З., Богдявічюс М. А. MAPLE 6: Рішення математичних, статистичних та фізико - технічних завдань - М.: Лабораторія Базових Знань, 2001 - 824с ..

3. Петросян Л.А., Зенкевич Н.А., Сьоміна Е.А. Теорія ігор. М.: ВШ, Книжковий дім «Університет», 1998.

4. Акулич І.Л. Математичне програмування в прикладах і задачах. М.: Вища школа, 1993.

5. Воробйов М.М. Основи теорії ігор. Безкоаліційний гри. М.: Наука, 1984.

6. Прохоров Г.В., Колбеев В.В., Желнов К.І., Леденьов М.А.. Математичний пакет Maple V Release 4. М. 1998.