МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Чернігівський державний технологічнийуніверситет
Кафедра вищої математики
Контрольна робота
з дисципліни: Математичне програмування
Варіант 06
Чернігів 2009
Зміст
Завдання №1
Завдання №2
Завдання №3
Завдання №4
Завдання №5
Список використаних джерел
Завдання №1
Звести до канонічної форми задачу лінійного програмування:
/>
Дана задача лінійного програмування задана в симетричній формі запису: умови, при яких функція Fбуде максимальною, задані у вигляді нерівностей. Для того, щоб отримати канонічну форму задачі лінійного програмування необхідно нерівності перетворити у рівності, використовуючи теорему, за якою нерівність
/>
еквівалентна рівнянню
/>і нерівності />
а нерівність вигляду
/>
еквівалентна рівнянню
/>, в якому />
Враховуючи наведене вище дану задачу запишемо у наступній канонічній формі:
/>
Завдання №2
Визначити оптимальний план задачі лінійного програмування графічним методом (знайти максимум і мінімум функції):
/>
Для задач з двома змінними можна використовувати графічний спосіб розв’язку задач лінійного програмування. Побудуємо область допустимих розв’язків системи лінійних нерівностей. Для цього будуємо відповідні даним нерівностям граничні прямі:
/>
Потім знаходимо напівплощини, в яких виконуються задані нерівності (рисунок1).
/>
Рисунок1– Графічне визначення максимального і мінімального значення функції
Область допустимих рішень визначається як загальна частина напівплощин, відповідних даним нерівностям, які при цьому знаходяться в першій четвертині, тобто обмежуються прямими /> і />. З малюнку 1 видно, що функція не має рішення, оскільки напівплощина, утворена прямими
/>
не співпадає з площиною, утвореною обмеженнями
/>/>.
Завдання №3
Побудувати двоїсту задачу. Симплексним методом знайти оптимальний план початкової задачі. Використовуючи першу теорему двоїстості, визначити план другої задачі.
/>
Для перетворення нерівностей в рівності вводимо змінні одиничні матриці х3, х4 і х5. Для розв’язку задачі симплексним методом необхідно мати три одиничних матриці при невід’ємних правих частинах рівнянь. Для отримання одиничної матриці в першій і третій нерівностях вводимо введемо штучні змінну х6 і х7 та отримаємо одиничні матриці А6 і А7. Де
/>і />
В результаті наведених перетворень отримаємо наступну задачу:
/>
У виразі функції величину М вважаємо достатньо великим додатнім числом, оскільки задача розв’язується на знаходження мінімального значення функції.
Запишемо задачу у векторній формі:
/>
де
/>
В якості базису вибираємо одиничні вектори А6, А4, А7. Вільні невідомі прирівнюємо нулю />. В результаті отримаємо початковий опорний план розширеної задачі
/>,
якому відповідає розкладення
/>
Для перевірки початкового опорного плану складаємо першу симплексну таблицю (таблиця1) і підраховуємо значення функції />і оцінок />Маємо:
/>/>
/>/>
/>/>/>--PAGE_BREAK--
/>/>
тобто оскільки М попередньо не фіксовано, то оцінки />є лінійними функціями величини М, причому функція складається з двох доданків, одне з яких залежить від М, інше не залежить. Для зручності розрахунків в (F-C) рядок запишемо доданок, незалежний від М, а в (М) рядок – тільки коефіцієнти при М, які і дозволяють порівняти оцінки між собою. Для векторів базису оцінки дорівнюють нулю.
Таблиця1– Перша симплексна таблиця
Базис
С базису
А
/>
/>
/>
/>
/>
/>
/>
х1
х2
х3
х4
х5
х6
х7
х6
М
8
1
/>
-1
1
х4
20
3
4
1
х7
М
6
3
1
-1
1
F-C
–
-5
-2
М
–
14
4
4
-1
-1
В (М) рядку є додатні оцінки, тому опорний план Хне є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає />. Оскільки у нас максимальне значення 4 належить двом векторам, то в базис включаємо вектор, якому відповідає мінімальне Сj. Розв’язувальним рядком вибирається той, в якому найменше відношення />Серед коефіцієнтів розкладання векторів А1і А2по базису є додатні, тому хоча б один з векторів існує… Знайдемо ці значення:
/>/>; />/>
Таким чином підтвердилося, що розв’язувальним стовпчиком буде другий, і визначилося, що розв’язувальним рядком буде перший. Тобто розв’язувальний елемент – число 3. Тоді вектор А2включаємо в базис, а вектор А6виключаємо з нього.
Складаємо другу симплексну таблицю (таблиця2). При цьому елементи першого (розв’язувального) рядка ділимо на 3. Елементи інших рядків визначаємо використовуючи формули повного виключення Йордана-Гауса.
Таблиця2– Друга симплексна таблиця
Базис
С базису
А
/>
/>
/>
/>
/>
/>
/>
х1
х2
х3
х4
х5
х6
х7
х2 продолжение
--PAGE_BREAK--
2
2,67
0,33
1
-0,33
0,33
х4
9,33
1,67
1,33
1
-1,33
х7
М
3,33
/>
0,33
-1
-0,33
1
F-C
–
5,33
-4,33
-0,67
0,67
М
–
3,33
2,67
0,33
-1
-1,33
В (М) рядку є додатні оцінки, тому план, зображений в таблиці2 не є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає />. Тобто за розв’язувальний стовпчик вибираємо перший. Мінімальне відношення
/>
тому розв’язувальним рядком є третій. Таким чином розв’язувальний елемент – число 2,67. Тоді вектор А1включаємо в базис, а вектор А7виключаємо з нього.
Складаємо другу симплексну таблицю (таблиця3). При цьому елементи третього (розв’язувального) рядка ділимо на 2,67. Елементи інших рядків визначаємо використовуючи формули повного виключення Йордана-Гауса.
Таблиця3– Третя симплексна таблиця
Базис
С базису
А
/>
/>
/>
/>
/>
/>
/>
х1
х2
х3
х4
х5
х6
х7
х2
2
2,25
1
-0,375
0,125
0,375
-0,125
х4
7,25
1,125
1
0,625
-1,125
-0,625
х1
5
1,25
1
0,125
-0,375
-0,125
0,375
F-C
–
10,75
-0,125
-1,625
0,125
1,625
М
–
-1
-1
В результаті проведеної ітерації з базису виключено штучні елементи, тому в рядку (М) всі оцінки, крім оцінки штучного вектору, перетворилися на нуль. Оскільки в рядках (F-C) і (М) не має додатних значень, то знайдене рішення
(/>)
є оптимальним. Функція при цьому
/>
Перевірка
/> продолжение
--PAGE_BREAK--
Кожній задачі лінійного програмування можна поставити у відповідність двоїсту задачу. Для цього першим кроком необхідно впорядкувати запис вихідної задачі. Оскільки у нас функція мінімізується, то всі умови-нерівності повинні бути вигляду />. Виконання цієї умови досягаємо множенням відповідних умов на (1-). В результаті система обмежень матиме наступний вигляд:
/>
Оскільки вихідна задача є задачею мінімізації, то двоїста буде задачею максимізації. Двоїста задача буде мати три змінні />, оскільки вихідна задача має три обмеження. При цьому вектор, отриманий із коефіцієнтів при невідомих цільової функції вихідної задачі />, співпадає з вектором констант у правих частинах обмежень двоїстої задачі. Аналогічно пов’язані між собою вектори, утворені з коефіцієнтів при невідомих цільової функції двоїстої задачі />, і константи в правих частинах обмежень вихідної задачі. Кожній змінній />двоїстої задачі відповідає і-те обмеження вихідної задачі, і, навпаки, кожній змінній />прямої задачі відповідає j-те обмеження двоїстої задачі. Матриця з коефіцієнтів при невідомих двоїстої задачі />утворюється транспортуванням матриці А, складеної з коефіцієнтів при невідомих вихідної задачі. Якщо на j-ту змінну вихідної задачі накладена умова невід’ємності, то j-те обмеження двоїстої задачі буде нерівністю, в іншому випадку j-те обмеження буде рівністю; аналогічно пов’язані між собою обмеження вихідної задачі і змінні двоїстої.
Складаємо матрицю при невідомих вихідної задачі:
/>,
тоді матриця при невідомих двоїстої задачі матиме наступний вигляд:
/>
На /> накладено умову невід’ємності, тому обмеження двоїстої задачі матимуть вигляд нерівності, а не рівності. Оскільки в початковій задачі всі обмеження мають вигляд нерівності, то накладаємо умови />
Враховуючи все наведене, двоїста задача матиме наступний вигляд:
/>
Якщо розглянути першу симплексну таблицю з одиничним додатковим базисом, то можна помітити, що в стовбцях записана вихідна задача, а в рядках – двоїста. Причому оцінками плану вихідної задачі є />, а оцінками плану двоїстої задачі – /> З таблиці3, отриманої в результаті рішення вихідної задачі знаходимо:
/>
Завдання №4
Визначити оптимальний план транспортної задачі:
а) побудувати початковий опорний план методом «північно-західного» напрямку;
б) побудувати оптимальний план методом потенціалів:
/>
Нехай в матриці А міститься інформація про кількість продукту в кожному місці виробництва, який необхідно доставити споживачам в кількості записаній в матриці В. Транспортні витрати, пов’язані з перевезенням одиниці продукту із одного місця виробництва одному споживачеві, записані в матриці С. Задані матриці і сказане вище для спрощення сприйняття узагальнимо в таблиці4.
Таблиця4–Поставка продукту із різних місць виробництва різним споживачам і пов’язані з цим витрати
Виробник
Споживач
Запаси продукту
/>
/>
/>
/>
/>
8
3
3
4
60
/>
5
2
7
5
20
/>
5
4
8
2
30
/>
7
1
5
7
20
Потреба в продукті
40
30
30
15
130
115
З таблиці4 видно, що запаси продукту у виробника на складах на 15 одиниць більші ніж необхідно споживачу, тобто маємо транспортну задачу з відкритою моделлю. Для розв’язку такої задачі введемо фіктивного споживача, якому необхідно отримати />одиниць продукту. Всі тарифи на доставку продукту цьому споживачеві будемо вважати рівними нулю, і весь продукт потрібний цьому споживачеві залишаємо у місці виробництва. Для побудови початкового плану перевезень (таблиця5) використаємо метод «північно-західного» напрямку: заповнювати таблицю починаємо з лівого верхнього кута, рухаючись вниз по стовбцю або вправо по рядку (тарифи перевезень напишемо в правому верхньому куту кожної клітини, кількість продукту – в нижньому лівому). В першу клітину заносимо менше з чисел (min(40;60): 40. Тобто потреба в продукті першого споживача повністю задовільнено і інші клітини першого стовпця заповнювати не будемо. Рухаємося далі по першому рядку в другий стовпчик. В цю клітину записуємо менше з 30 і (60-40), тобто пишемо 20. Таким чином перший рядок заповнювати далі не будемо, оскільки запаси першого місця виробництва остаточно вичерпано: з нього ми повністю задовольняємо потребу у продукті першого споживача і частково (20одиниць, а не 30) другого. Рухаємося по другому стовпчику на другий рядок. Сюди записуємо менше з (30-20) або 20: маємо 10, тобто другому споживачеві ми веземо 20одиниць продукту з першого місця виробництва і 10– з другого. Аналогічно заповнюємо інші клітини.
Таблиця5– Розподіл продукту по споживачам
Виробник
Споживач
Запаси продукту
/>
/>
/>
/>
/>
/>
8 продолжение
--PAGE_BREAK----PAGE_BREAK--
30
15
15
130
×
/>
8
3
8
2
-5
×
×
Систему потенціалів можна побудувати лише для невирожденого опорного плану. Такий план містить m+n-1 лінійно незалежних рівнянь виду />з m+nневідомими (де m– кількість постачальників, n– кількість споживачів). Рівнянь на одне менше, ніж невідомих, тому система є невизначеною і для її розв’язку одному невідомому (нехай ним буде u1)придамо нульове значення.
Для того, щоб план був оптимальним, повинна виконуватись умова: для кожної незайнятої клітини сума потенціалів повинна бути менша або дорівнювати вартості одиниці перевезення, що стоїть в цій клітині: />тобто />Робимо перевірку для всіх вільних клітин:
/>
З розрахунків бачимо, що умова оптимальності не виконується для клітин, А1В3, А2В1, А3В1, А4В1, А4В2, і А4В3. Клітину, в якій додатне число отримали максимальним (А2В3, оскільки max(5;2;3;6;7;8)=8)зробимо зайнятою, для цього побудуємо цикл і отримуємо таблицю7.
Таблиця7– Другий крок пошуку оптимального рішення
Виробник
Споживач
Запаси продукту
/>
/>
/>
/>
/>
/>
/>
8
3
3
4
60
40
20
/>
5
2
7
5
20
-1
10
10
/>
5
4
8
2
30
15
15
/>
7
1
5
7
20
-3
5
15
Потреба в продукті
40
30
30
15
15
130
×
/>
8
3
8
2
3
×
×
Транспортні витрати при такому плані перевезення складають:
/>
Перевірка всіх вільних клітин:
/>
Отримали від’ємні значення у всіх клітинах окрім А1В3(5), А1В5(3), А2В1(2), А2В5(2), А3В1(3) і А3В5(3). Максимальне значення max(5;3;2;2;3;3)=5 в клітині А1В3, тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці7, результат дій в таблиці8). продолжение
--PAGE_BREAK--
Таблиця8– Третій крок пошуку оптимального рішення
Виробник
Споживач
Запаси продукту
/>
/>
/>
/>
/>
/>
/>
8
3
3
4
60
-
40
10
10
/>
5
2
7
5
20
-1
20
/>
5
4
8
2
30
5
15
15
/>
7
1
5
7
20
2
5
15
Потреба в продукті
40
30
30
15
15
130
×
/>
8
3
3
-3
-2
×
×
Транспортні витрати:
/>
тобто при такому плані перевезення товару транспортні витрати знизилися на 50грн. в порівнянні з попереднім планом перевезення. Але, щоб визначити є отриманий план оптимальним чи ні, виконаємо перевірку.
Перевірку всіх вільних клітин зобразимо в таблиці9, в якій для всіх вільних клітин запишемо різницю між сумою потенціалів і транспортними витратами в клітині.
Таблиця9– Перевірка плану отриманого в результаті третього кроку пошуку оптимального рішення задачі
/>
/>
/>
/>
/>
/>
-
-
-
-7
-2
/>
2
-
-5
-9
-3
/>
8
4
-
-
3
/>
3
4
-
-8
-
З таблиці9 видно, що додатне значення отримали для клітин А2В1(2), А3В1(8), А3В2(4), А3В5(3), А4В1(3) і А4В2(4). Максимальне значення max(2;8;4;3;3;4)=8 в клітині А3В1, тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці8, результат дій в таблиці10). продолжение
--PAGE_BREAK--
Таблиця1– Четвертий крок пошуку оптимального рішення задачі
Виробник
Споживач
Запаси продукту
/>
/>
/>
/>
/>
/>
/>
8
3
3
4
60
25
10
25
/>
5
2
7
5
20
-1
20
/>
5
4
8
2
30
-3
15
15
/>
7
1
5
7
20
2
5
15
Потреба в продукті
40
30
30
15
15
130
×
/>
8
3
3
5
-2
×
×
Транспортні витрати:
/>
що на 120грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів.
Перевірка всіх вільних клітин наведена в таблиці11.
Таблиця11– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
/>
/>
/>
/>
/>
/>
-
-
-
1
-2
/>
2
-
-5
-1
-3
/>
-
-4
-8
-
-5
/>
3
4
-
-
План, зображений в таблиці10 не є оптимальним, оскільки отримали додатні значення в клітинах А1В4 (1), А2В1 (2), А4В1 (3), А4В2 (4). Заповнюємо клітину А4В2 і будуємо опорний план (таблиця12).
Таблиця12– П’ятий крок пошуку оптимального рішення задачі
Виробник
Споживач
Запаси продукту продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
5
15
/>
5
2
7
5
20
-2
20
/>
5
4
8
2
30
-2
20
10
/>
7
1
5
7
20
-2
20
Потреба в продукті
40
30
30
15
15
130
×
/>
7
3
3
4
×
×
Розрахунки для перевірка всіх вільних клітин здійснені в таблиці 21:
Таблиця21– Різниця між сумою потенціалів і транспортними витратами для вільних клітин
/>
/>
/>
/>
/>
/>
-1
-
-
-
-
/>
-
-1
-6
-3
-2
/>
-
-3
-7
-
-2
/>
-2
-
-4
-5
-2
Рішення, зображене в таблиці20 є оптимальним, оскільки для кожної незайнятої клітини сума потенціалів менша вартості перевезень, що знаходиться у відповідній клітинці. Транспортні витрати по оптимальному плану перевезень становлять:
/>
Знайдений оптимальний план покращив результат діяльності у порівнянні з початковим (зменшив транспортні витрати) на 685-380=305гривень.
Список використаних джерел
Кузнецов Ю.Н. Математическое программирование. Учебное пособие для вузов– М.: Высшая школа, 1976.– 352с.
Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию.– Мн.: Высш. школа, 1978.– 256с.