МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИЧернігівський державний технологічний університетКафедра вищої математикиКонтрольна роботаз дисципліни: Математичнепрограмування
Варіант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) іпідраховуємо значення функції /> іоцінок /> Маємо:
/> />
/> />
/> /> />
/> />
тобто оскільки Мпопередньо не фіксовано, то оцінки /> єлінійними функціями величини М, причому функція складається з двох доданків,одне з яких залежить від М, інше не залежить. Для зручності розрахунків в (F-C) рядок запишемо доданок, незалежнийвід М, а в (М) рядок – тільки коефіцієнти при М, які і дозволяють порівнятиоцінки між собою. Для векторів базису оцінки дорівнюють нулю.
Таблиця1– Першасимплексна таблицяБазис С базису
А0
/>
/>
/>
/>
/>
/>
/>
х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
В (М) рядку є додатніоцінки, тому опорний план Х0не є оптимальним і його можна покращити,включивши в базис вектор, якому відповідає />. Оскільки у насмаксимальне значення 4 належить двом векторам, то в базис включаємо вектор,якому відповідає мінімальне Сj. Розв’язувальним рядком вибирається той, в якому найменшевідношення /> Серед коефіцієнтіврозкладання векторів А1 і А2 по базису є додатні, томухоча б один з векторів існує… Знайдемо ці значення:
/>/>; /> />
Таким чином підтвердилося,що розв’язувальним стовпчиком буде другий, і визначилося, що розв’язувальнимрядком буде перший. Тобто розв’язувальний елемент – число 3. Тоді вектор А2включаємо в базис, а вектор А6 виключаємо з нього.
Складаємо другусимплексну таблицю (таблиця2). При цьому елементи першого (розв’язувального)рядка ділимо на 3. Елементи інших рядків визначаємо використовуючи формулиповного виключення Йордана-Гауса.
Таблиця2– Другасимплексна таблицяБазис С базису
А0
/>
/>
/>
/>
/>
/>
/>
х1
х2
х3
х4
х5
х6
х7
х2 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– Третясимплексна таблицяБазис С базису
А0
/>
/>
/>
/>
/>
/>
/>
х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) і (М)не має додатних значень, то знайдене рішення
(/>)
є оптимальним.Функція при цьому
/>
Перевірка
/>
Кожній задачілінійного програмування можна поставити у відповідність двоїсту задачу. Дляцього першим кроком необхідно впорядкувати запис вихідної задачі. Оскільки унас функція мінімізується, то всі умови-нерівності повинні бути вигляду />. Виконання цієї умовидосягаємо множенням відповідних умов на (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 3 3 4 60 40 20
/> 5 2 7 5 20 10 10
/> 5 4 8 2 30 20 10
/> 7 1 5 7 20 5 15 Потреба в продукті 40 30 30 15 15 130
Таким чином, втаблиці5 отримали початковий опорний план, транспортні витрати за яким складають:
/>
Недолікомвикористаного методу знаходження опорного плану є ігнорування величини тарифівна перевезення продукту.
Для визначення оптимальногоплану перевезень використаємо метод потенціалів. Для цього кожному виробнику Аі(кожному рядку) ставимо у відповідність деяке число /> акожному споживачу Ві (кожному стовпчику)– деяке число /> На основі таблиці5складемо таблицю6, в якій додамо один стовпчик і один рядок для написаннявеличини параметрів />і />. Їх знаходимовикористовуючи першу умову оптимальності транспортної задачі: /> (для кожної зайнятоїклітини сума потенціалів повинна дорівнювати вартості одиниці перевезення, щозаписана в цій клітині).
Таблиця6–Перевірка оптимальності опорного плануВиробник Споживач Запаси продукту
/>
/>
/>
/>
/>
/>
/> 8 3 3 4 60 40 20
/> 5 2 7 5 20 -1 10 10
/> 5 4
/>8 2 30 20 10
/> 7 1 5 7 20 5 5 15 Потреба в продукті 40 30 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).
Таблиця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).
Таблиця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– П’ятийкрок пошуку оптимального рішення задачіВиробник Споживач Запаси продукту
/>
/>
/>
/>
/>
/>
/> 8
/>3 3 4 60 25 5 30
/> 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 × ×
Транспортнівитрати за отриманим планом перевезень складають:
/>
що на 20грн.економніше попереднього варіанту розвезення продукції від постачальників доспоживачів.
Перевірка всіхвільних клітин здійснена в таблиці 13.
Таблиця13–Різниця між сумою потенціалів і транспортними витратами для вільних клітин
/>
/>
/>
/>
/>
/> - - - 1 2
/> 2 - -5 -1 1
/> - -4 -8 - -1
/> -1 - -4 -4 -
Оскільки врезультаті розрахунків отримали додатні значення, то знову будуємо цикл ізаповнюємо необхідну клітину. В даному випадку це буде або клітина А2В1або клітина А1В5. Вибираємо останню, оскільки транспортнівитрати на перевезення в ній менші. На від’ємних кутах циклу об’єм перевезеньстановить 10 і 0. Оскільки min(10;0)=0, то всі клітини залишаються незмінними і лише клітина з нульовимперевезенням переходить з А4В5 на А1В5.
Новий планзображено в таблиці14.
Таблиця14– Шостийкрок пошуку оптимального рішення задачіВиробник Споживач Запаси продукту
/>
/>
/>
/>
/>
/>
/>
/>8 3 3 4 60 25 30 5
/> 5 2 7 5 20 -1 20
/> 5 4 8 2 30 -3 15 15
/> 7 1 5 7 20 10 10 Потреба в продукті 40 30 30 15 15 130 ×
/> 8 1 3 5 × ×
Транспортнівитрати за отриманим планом перевезень складають:
/>
Розрахунки для перевіркавсіх вільних клітин здійснені в таблиці 15:
Таблиця15–Різниця між сумою потенціалів і транспортними витратами для вільних клітин
/>
/>
/>
/>
/>
/> - -2 - 1 -
/> 4 - -3 1 1
/> - -6 -8 - -3
/> 1 - -2 -2 -
З таблиці15видно, що максимальне додатне значення отримали для клітини А2В1,тому заповнюємо її будуючи для неї цикл, який показано в таблиці14. Результатдій в таблиці16.
Таблиця16– Сьомийкрок пошуку оптимального рішення задачіВиробник Споживач Запаси продукту
/>
/>
/>
/>
/>
/>
/>
/>8 3 3 4 60 15 30 15
/> 5 2 7 5 20 -3 10 10
/> 5 4 8 2 30 -3 15 15
/> 7 1 5 7 20 -4 20 Потреба в продукті 40 30 30 15 15 130 ×
/> 8 5 3 5 × ×
Транспортнівитрати:
/>
що на 40грн.економніше попереднього варіанту розвезення продукції від постачальників доспоживачів.
Перевірка всіхвільних клітин наведена в таблиці17.
Таблиця17–Різниця між сумою потенціалів і транспортними витратами для вільних клітин
/>
/>
/>
/>
/>
/> - 2 - 1 -
/> - - -7 -3 -3
/> - -2 -8 - -3
/> -3 - -6 -6 -4
План, зображенийв таблиці8 не є оптимальним, оскільки отримали додатні значення в клітинах А1В2(2) і А1В4 (1). Заповнюємо клітину А1В2і будуємо опорний план (таблиця18).
Таблиця18– Восьмийкрок пошуку оптимального рішення задачіВиробник Споживач Запаси продукту
/>
/>
/>
/>
/>
/>
/>
/>8 3 3 4 60 5 10 30 15
/> 5 2 7 5 20 -3 20
/> 5 4 8 2 30 -3 15 15
/> 7 1 5 7 20 -2 20 Потреба в продукті 40 30 30 15 15 130 ×
/> 8 3 3 5 × ×
Транспортнівитрати за отриманим планом перевезень складають:
/>
що на 20грн.економніше попереднього варіанту розвезення продукції від постачальників доспоживачів. Перевірка всіх вільних клітин здійснена в таблиці 19.
Таблиця19–Різниця між сумою потенціалів і транспортними витратами для вільних клітин
/>
/>
/>
/>
/>
/> - - - 1 -
/> - -2 -7 -3 -3
/> - -4 -8 - -3
/> -1 - -4 -4 -2
Оскільки врезультаті розрахунків отримали додатне значення в єдиній клітині А1В4,то будуємо цикл і заповнюємо її. Новий план зображено в таблиці20.
Таблиця20– Дев’ятийкрок пошуку оптимального рішення задачіВиробник Споживач Запаси продукту
/>
/>
/>
/>
/>
/>
/> 8 3 3 4 60 10 30 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гривень./>
Списоквикористаних джерел
1. Кузнецов Ю.Н.Математическое программирование. Учебное пособие для вузов– М.: Высшая школа,1976.– 352с.
2. Кузнецов А.В.,Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию.–Мн.: Высш. школа, 1978.– 256с.