Постановка задачі. Знайти графічним способом максимум цільової функції. Розв'язання задач лінійного програмування графічним методом

Тести для поточного контролюзнань

1. Будь-яка економіка – математична модельзавдання лінійного програмуванняскладається з:

A. цільової функціїта системи обмежень

B.цільової функції, системи обмежень та умови невід'ємності змінних

C. системи обмежень та умови невід'ємності змінних

D. цільової функції та умови невід'ємності змінних

A.цільова функція

B. система рівнянь

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

D. умова невід'ємності змінних

3. Оптимальне вирішення задачі математичного програмування – це

A. допустиме рішення системи обмежень

B. будь-яке рішення системи обмежень

C.допустиме рішення системи обмежень, що призводить до максимуму або мінімуму цільової функції

D. максимальне або мінімальне рішення системи обмежень

4. Система обмежень називається стандартною, якщо вона містить

A. всі знаки

B.всі знаки

C. всі знаки

D. всі знаки

5. Завдання лінійного програмування вирішується графічним способомякщо в задачі

A. одна змінна

B.дві змінні

C. три змінні

D. чотири змінні

6. Нерівність виду описує

B. коло

C.напівплощина

D. площина

7. Максимум або мінімум цільової функції знаходиться

A. на початку координат

B. на сторонах опуклого багатокутника рішень

C. всередині опуклого багатокутника рішень

D.у вершинах опуклого багатокутника рішень

8. Канонічним видом ЗЛП називається такий її вид, у якому система обмежень містить знаки

A. всі знаки

B. всі знаки

C.всі знаки

D. всі знаки

9. Якщо обмеження задано зі знаком «>=», то додаткова змінна вводиться в це обмеження з коефіцієнтом

B.-1

10. До цільової функції додаткові змінні вводяться з коефіцієнтами

C.0

A.кількість ресурсу з номером i, необхідного для виготовлення 1 одиниці продукції j – го виду

B. невикористані ресурси i - го виду

C. прибуток від реалізації 1 одиниці продукції j – го виду

D. кількість продукції j – го виду

12. Стовпець, що дозволяє, при вирішенні ЗЛП на max цільової функції вибирається виходячи з умови

A.найбільше позитивне значеннякоефіцієнта Cj цільової функції

B. найменше позитивне значення коефіцієнта Cj цільової функції

C. найбільше негативне значення коефіцієнта Cj цільової функції

D. будь-який стовпець коефіцієнтів при невідомих

13. Значення цільової функції у таблиці з оптимальним планом знаходиться

A. на перетині рядка коефіцієнтів цільової функції зі стовпцем коефіцієнтів при х1

B.на перетині рядка коефіцієнтів цільової функції зі стовпцем b

C. у стовпці коефіцієнтів при хn

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

14. Штучні змінні до системи обмежень у канонічному вигляді вводяться з коефіцієнтом

A.1

15. Оптимальність плану в симплексній таблиці визначається

A. по стовпцю b

B.по рядку значень цільової функції

C. за роздільною здатністю

D. по роздільному стовпцю

16. Дана задача лінійного програмування

B.1

17. Дана задача лінійного програмування

Кількість штучних змінних для цього завдання дорівнює

C.2

18. Якщо вихідна ЗЛП має вигляд

тоді обмеження двоїстої задачі

A. мають вигляд

B.мають вигляд

C. мають вигляд

D. мають вигляд

19. Якщо вихідна ЗЛП має вигляд

A. мають вигляд

B. мають вигляд

C. мають вигляд

D.мають вигляд

20. Коефіцієнтами за невідомих цільової функції двоїстої задачі є

A. коефіцієнти при невідомих цільової функції вихідної задачі

B.вільні члени системи обмежень вихідного завдання

C. невідомі вихідні завдання

D. коефіцієнти при невідомих системах обмежень вихідного завдання

21. Якщо вихідна ЗЛП була на максимум цільової функції, то подвійне завдання буде

A. теж на максимум

B. або на максимум, або на мінімум

C. і на максимум, і на мінімум

D.на мінімум

22. Зв'язок вихідної та двоїстої задач полягає в тому, що

A. треба вирішувати обидві задачі

B.рішення однієї з них виходить із рішення іншої

C. з вирішення двоїстої задачі не можна отримати рішення вихідної

D. обидві мають однакові рішення

23. Якщо вихідна ЗЛП має вигляд

тоді цільова функція двоїстої задачі

A. мають вигляд

B. мають вигляд

C.мають вигляд

D. мають вигляд

24. Якщо вихідна ЗЛП має вигляд

то кількість змінних у подвійному завданні дорівнює

B.2

25. Модель транспортного завдання закрита,

A.якщо

26. Цикл у транспортному завданні – це

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

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

C. замкнута прямокутна ламана лінія, одна вершина якої у зайнятій клітці, решта у вільних клітинах

D.замкнута прямокутна ламана лінія, одна вершина якої у вільній клітині, а решта у зайнятих клітинах

27. Потенціалами транспортного завдання розмірності (m*n) називаються m+n чисел ui та vj, для яких виконуються умови

A.ui+vj=cij для зайнятих клітин

B. ui+vj=cij для вільних клітин

C. ui+vj=cij для перших двох стовпців розподільчої таблиці

D. ui+vj=cij для перших двох рядків розподільчої таблиці

28. Оцінками транспортного завдання розмірності (m+n) називаються числа

yij=cij-ui-vj, які обчислюються

A. для зайнятих клітин

B.для вільних клітин

C. для перших двох рядків розподільчої таблиці

D. для перших двох стовпців розподільчої таблиці

29. При вирішенні транспортного завдання значення цільової функції повинне від ітерації до ітерації.

A. збільшуватися

B. збільшуватися чи змінюватися

C. збільшуватися на величину будь-якої оцінки

D.зменшуватися чи не змінюватися

30. Число зайнятих клітин невиродженого плану транспортного завдання має бути рівним

C.m+n-1

31. Економічний зміст цільової функції транспортного завдання

A. сумарний обсяг перевезень

B.сумарна вартість перевезень

C. сумарні постачання

D. сумарні потреби

Вступ

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

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

1. Постановка задачі

мінімум цільова функція

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

Малюнок 1 - Багатокутник розв'язання задачі

Система обмежень та цільова функція задачі представлені нижче:

Необхідно вирішити задачу, використовуючи такі методи:

Графічний метод розв'язання задач ЛП;

Алгебраїчний метод розв'язання задач ЛП;

Симплекс-метод розв'язання задач ЛП;

Спосіб відшукання припустимого вирішення завдань ЛП;

Розв'язання двоїстої задачі ЛП;

Метод «гілок та кордонів» вирішення цілих задач ЛП;

Метод Гоморі вирішення цілих задач ЛП;

Метод Балаша розв'язання булевських завдань ЛП.

Порівняти результати рішення різними методамизробити відповідні висновки щодо роботи.

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

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

Рис. 2 Графічне розв'язання задачі ЛП

Точка мінімуму

Рівняння прямої через дві точки A1 і A2:

АВ: (0; 1); (3;3)

НД: (3;3); (4;1)

CD: (4; 1); (3;0)

EА: (1; 0); (0;1)

ЦФ: (0; 1); (5;2)

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

Розв'язання задачі лінійного програмування алгебраїчним симплекс-методом

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

Перетворити нерівності в такий спосіб, щоб зліва перебували змінні і вільні члени, а праворуч - 0 тобто. щоб ліва частинабула більшою або рівною нулю;

Ввести додаткові змінні, число яких дорівнює числу нерівностей у системі обмежень;

Ввівши додаткові обмеження на невід'ємність доданих змінних, замініть знаки нерівностей на знаки суворої рівності.

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

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

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

Вільних змінних

св.пер. - Дод. набір

Умови не негативності виконані, отже, знайдено оптимальне рішення.

3. Розв'язання задачі лінійного програмування з використанням симплекс-таблиці

Рішення: Наведемо завдання до стандартного виду для вирішення за допомогою симплекс-таблиці.

Усі рівняння системи наведемо до виду:

Будуємо симплекс-таблицю:

У верхній кут кожної клітини таблиці вписуємо коефіцієнти із системи рівнянь;

Вибираємо максимальний позитивний елемент у рядку F, крім цього буде генеральний стовпець;

Для того, щоб знайти генеральний елемент, будуємо відношення для всіх позитивних. 3/3; 9/1; - мінімальне співвідношення у рядку x3. Отже – генеральний рядок і = 3 – генеральний елемент.

Знаходимо =1/=1/3. Вносимо у нижній кут клітини, де знаходиться генеральний елемент;

У всі незаповнені нижні кути генерального рядка вносимо добуток значення у верхньому кутку клітини;

Виділяємо верхні кути генерального рядка;

У всі нижні кути генерального стовпця заносимо добуток значення у верхньому кутку на - і виділяємо отримані значення;

Інші клітини таблиці заповнюються як твори відповідних виділених елементів;

Потім будуємо нову таблицю, в якій позначення клітин елементів генерального стовпця та рядки змінюються місцями (x2 та x3);

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

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

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

Нехай дана система лінійних рівнянь алгебри:

Можна припустити, що все, інакше множимо відповідне рівняння на -1.

Вводимо допоміжні змінні:

Вводимо також допоміжну функцію

Мінімізуватимемо систему при обмеженнях (2) та умовах.

ПРАВИЛО ВІДшукАННЯ ДОПУСТИМОГО РІШЕННЯ: Для відшукання допустимого рішення системи (1) мінімізуємо форму (3) при обмеженнях (2), як вільні невідомі беремо xj, як базисні.

При вирішенні задачі симплекс-метод можуть виникнути два випадки:

min f=0, тоді все i повинні бути рівними нулю. А значення xj, що виходять, будуть становити допустиме рішення системи (1).

min f>0, тобто. вихідна система немає допустимого рішення.

Вихідна система:

Використовується умова завдання попередньої теми.

Внесемо додаткові змінні:

Знайдено припустиме рішення вихідної задачі: х1 = 3, х2 = 3, F = -12. Ґрунтуючись на отриманому допустимому рішенні знайдемо оптимальне рішення вихідного завдання, користуючись симплекс-методом. Для цього побудуємо нову симплекс-таблицю з отриманої таблиці, видаливши рядок і рядок з цільовою функцією допоміжної задачі:

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

6. Подвійне завдання лінійного програмування

Вихідна система обмежень та цільова функція задачі показані на малюнку нижче.

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

Рішення: Наведемо систему обмежень до стандартного вигляду:

Завдання, двоїсте даної мати вигляд:

Розв'язання двоїстої задачі виконуватиметься простим симплекс-методом.

Перетворимо цільову функцію так, щоб вирішувалося завдання мінімізації, та запишемо систему обмежень у стандартній формі для вирішення симплекс-методом.

y6 = 1 - (-2 y1 + 2y2 + y3 + y4 + y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Побудуємо вихідну симплекс-таблицю на вирішення двоїстої завдання ЛП.

Другий крок симплекс-методу

Отже, на третьому кроці симплекс-метода знайдено оптимальне рішення задачі мінімізації з наступними результатами: y2 = -7 /8, y1 = -11/8, Ф = 12. Для того, щоб знайти значення цільової функції двоїстої задачі, підставимо знайдені значення базисних та вільних змінних у функцію максимізації:

Фmax = - Фmin = 3 * (-11 / 8) + 9 (-7 / 8) + 3 * 0 + 0 = -12

Так як значення цільової функції прямої та двоїстої задач збігаються, рішення прямої задачі знайдено і дорівнює 12.

Fmin = Фmax = -12

7. Розв'язання задачі цілісного лінійного програмування методом «гілок та кордонів»

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

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

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

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

В результаті рішення знайдено оптимальний планЗавдання: х1 = 9/4, х2 = 5/2, F = -41/4. Це рішення не відповідає умові цілісності, поставленої в задачі. Розіб'ємо вихідний багатокутник рішень на дві області, виключивши з нього область 3

Змінений багатокутник розв'язання задачі

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

Система обмежень для лівої області

Права область є точку З.

Система обмежень для правої галузі рішень представлена ​​нижче.

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

В результаті рішення знайдено оптимальний план задачі: х1 = 3, х2 = 3, F = -12. Цей план задовольняє умові цілісної кількості змінних у завданні і може бути прийнятий в якості оптимального опорного плану для вихідної задачі цілісного лінійного програмування. Проводити рішення для правої галузі рішень немає сенсу. На малюнку нижче представлений хід вирішення цілої задачі лінійного програмування у вигляді дерева.

Хід вирішення цілої задачі лінійного програмування методом Гоморі.

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

Потрібно знайти ціле рішення системи (1), яке мінімізує цільову функцію F, причому, всі коефіцієнти - цілі.

Один із методів розв'язання задачі цілісного програмування запропонований Гоморі. Ідея методу полягає у використанні методів безперервного лінійного програмування, зокрема симплекс-метода.

1) Визначається за допомогою симплекс-метода розв'язання задачі (1), (2), у якої знято вимогу цілісності розв'язання; якщо рішення виявляється цілою, то шукане рішення цілісної задачі буде також знайдено;

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

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

В іншому випадку вводиться додаткове лінійне обмеження, яке відсікає від допустимого багатогранника частину, безперспективну для розв'язання задачі цілісного програмування;

3) Для побудови додаткового лінійного обмеження, вибираємо l-ту рядок з дрібним вільним членом і записуємо додаткове обмеження

де і - відповідно дробові частини коефіцієнтів та вільного

члена. Введемо до обмеження (3) допоміжну змінну:

Визначимо коефіцієнти та, що входять в обмеження (4):

де і - найближчі цілі знизу для та відповідно.

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

Рішення: Наведемо систему лінійних обмежень та функцію мети до канонічної форми:

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

Вирішення булевських завдань ЛП методом Балаша.

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

Виконання обмежень

Значення F

Фільтруюче обмеження:

Визначення зниження трудомісткості обчислень

Розв'язання задачі методом повного перебору становить 6*25=192 обчислені вирази. Розв'язання задачі методом Балаша становить 3*6+(25-3)=47 обчислених виразів. Разом зниження трудомісткості обчислень стосовно вирішення задачі методом повного перебору становить.

Висновок

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

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

Література:

1. Лященко І.М. Лінійне та нелінійне програмування / І.М.Лященко, Є.А.Карагодова, Н.В.Чернікова, Н.З.Шор. – К.: «Вища школа», 1975, 372 с.

2. Методичні вказівки для виконання курсового проекту з дисципліни «Прикладна математика» для студентів спеціальності «Комп'ютерні системи та мережі» денної та заочної форм навчання / Упоряд.: І.А.Балакірєва, А.В.Скатков- Севастополь: Вид-во СевНТУ , 2003. – 15 с.

3. Методичні вказівки щодо вивчення дисципліни «Прикладна математика», розділ «Методи глобального пошуку та одновимірної мінімізації» / Упоряд. А.В.Скатков, І.А.Балакірєва, Л.А.Литвинова - Севастополь: Вид-во ПівнГТУ, 2000. - 31с.

4. Методичні вказівки для вивчення дисципліни «Прикладна математика» для студентів спеціальності «Комп'ютерні системи та мережі» Розділ «Рішення завдань цілочисельного лінійного програмування» денної та заочної форм навчання / Упоряд.: І.А.Балакірєва, А.В.Скатков – Севастополь : Вид-во СевНТУ, 2000. – 13 с.

5. Акуліч І.Л. Математичне програмування в прикладах та задачах:

6. Навч. посібник для студентом економ. спец. вузів.-М.: Вищ. шк., 1986. - 319с., іл.

7. Андронов С.А. Методи оптимального проектування: Текст лекцій / СПбГУАП. СПб., 2001. 169 с.: іл.

Подібні документи

Алгоритм розв'язання задач лінійного програмування симплекс-методом. Побудова математичної моделі задачі лінійного програмування. Розв'язання задачі лінійного програмування в Excel. Знаходження прибутку та оптимального плану випуску продукції.

курсова робота , доданий 21.03.2012


Графічний розв'язок задач. Складання математичної моделі. Визначення максимального значення цільової функції. Рішення симплексним методом зі штучним базисом канонічного завдання лінійного програмування. Перевіряє оптимальність рішення.

контрольна робота , доданий 05.04.2016


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

курсова робота , доданий 09.12.2008


Побудова математичної моделі. Вибір, обґрунтування та опис методу рішень прямого завдання лінійного програмування симплекс-методом, з використанням симплексної таблиці. Складання та розв'язання двоїстої задачі. Аналіз моделі на чутливість.

курсова робота , доданий 31.10.2014


Побудови математичної моделі з метою отримання максимального прибутку підприємства, графічне вирішення задачі. Вирішення задачі за допомогою надбудови SOLVER. Аналіз змін запасів ресурсів. Визначення меж зміни коефіцієнтів цільової функції.

курсова робота , доданий 17.12.2014


Математичне програмування. Лінійне програмування. Завдання лінійного програмування. Графічний метод розв'язання задачі лінійного програмування. Економічна постановка задачі лінійного програмування. Побудова математичної моделі.

курсова робота , доданий 13.10.2008


Розв'язання задачі лінійного програмування графічним методом, його перевірка у MS Excel. Аналіз внутрішньої структури розв'язання задачі у програмі. Оптимізація плану виробництва. Розв'язання задачі симплекс-методом. Багатоканальна система масового обслуговування.

контрольна робота , доданий 02.05.2012


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

контрольна робота , доданий 11.04.2012


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

курсова робота , доданий 17.12.2012


Аналіз розв'язання задачі лінійного програмування. Симплексний метод із використанням симплекс-таблиць. Моделювання та розв'язання завдань ЛП на ЕОМ. Економічна інтерпретація оптимального розв'язання задачі. Математичне формулювання транспортного завдання.

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

Приклади

Гладкі функції та системи рівнянь

Завдання розв'язання будь-якої системи рівнянь

( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matrix) )\right.)

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

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad (1))

Якщо функції гладкі, завдання мінімізації можна вирішувати градієнтними методами.

Для будь-якої гладкої цільової функції можна прирівняти до 0 (displaystyle 0) приватні похідні по всіх змінних. Оптимум цільової функції буде одним із рішень такої системи рівнянь. У разі функції (1) (\displaystyle (1)) це буде система рівнянь методу найменших квадратів (МНК). Будь-яке рішення вихідної системи є рішенням системи МНК. Якщо вихідна система несумісна, то система МНК, що завжди має рішення, дозволяє отримати наближене рішення вихідної системи. Число рівнянь системи МНК збігається з числом невідомих, що іноді полегшує і вирішення спільних вихідних систем.

Лінійне програмування

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

Комбінаторна оптимізація

Типовим прикладом комбінаторної цільової функції є цільова функція завдання комівояжера. Ця функція дорівнює довжині гамільтонового циклу на графі. Вона задана на безлічі перестановок n − 1 (displaystyle n-1) вершини графа і визначається матрицею довжин ребер графа. Точне вирішення подібних завдань часто зводиться до вибору варіантів.

Глава 1. Постановка основного завдання лінійного програмування

1. Лінійне програмування

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

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

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

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

завдання про суміші (планування складу продукції);

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

транспортні завдання (аналіз розміщення підприємства, переміщення вантажів).

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

математичні моделі великої кількості економічних завдань лінійні щодо шуканих змінних;

даний тип завдань у час найбільш вивчений. Для нього розроблені спеціальні методи, за допомогою яких ці завдання вирішуються, та відповідні програми для ЕОМ;

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

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

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

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

цільова функція

(1.1) при обмеженнях

(1.2) вимоги невід'ємності

(1.3) де x j- Змінні (невідомі);

- Коефіцієнти завдання лінійного програмування.

Завдання полягає у знаходженні оптимального значення функції (1.1) при дотриманні обмежень (1.2) та (1.3).

Систему обмежень (1.2) називають функціональними обмеженнями завдання, а обмеження (1.3) – прямими.

Вектор, що відповідає обмеженням (1.2) і (1.3), називається допустимим рішенням (планом) завдання лінійного програмування. План, у якому функція (1.1) досягає свого максимального (мінімального) значення, називається оптимальним.

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

Симплекс-метод було розроблено і вперше застосований на вирішення завдань 1947 р. американським математиком Дж. Данцигом.

Двовимірні завдання лінійного програмування вирішуються графічно. Для випадку N=3 можна розглянути тривимірний простір і цільова функція буде досягати свого оптимального значення в одній з вершин багатогранника.

Допустимим рішенням (допустимим планом) завдання ЛП, даної в стандартній формі, називається впорядкована безліч чисел (х1, х2, …, хn), що задовольняють обмеження; це точка в n-мірному просторі.

Багато допустимих рішень утворює область допустимих рішень (ОДР) задачі ЛП. ОДР є опуклим багатогранником (багатокутником).

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

Базисним називається рішення, у якому всі вільні змінні дорівнюють нулю.

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

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

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

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

З його допомогою можна вирішити будь-яку задачу лінійного програмування.

В основу симплексного методу покладено ідею послідовного поліпшення одержуваного рішення.

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

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

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

спосіб визначення будь-якого початкового допустимого базового рішення задачі;

правило переходу на краще (точніше, не гіршому) рішенню;

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

Симплексний метод включає ряд етапів і може бути сформульований у вигляді чіткого алгоритму (чіткого припису про виконання послідовних операцій). Це дозволяє успішно програмувати та реалізовувати його на ЕОМ. Завдання з невеликою кількістю змінних та обмежень можуть бути вирішені симплексним методом вручну.

6.1.

Оптимізація. Частина 1

Методи оптимізації дозволяють вибрати найкращий варіант конструкції із усіх можливих варіантів. В останні роки цим методам приділялася велика увага, і в результаті було розроблено цілу низку високоефективних алгоритмів, що дозволяють знайти оптимальний варіант конструкції за допомогою ЕЦОМ. У цьому розділі викладаються основи теорії оптимізації, розглядаються принципи, що лежать в основі побудови алгоритмів оптимальних рішень, описуються найбільш відомі алгоритми, аналізуються їх переваги та недоліки.

6.2.Основи теорії оптимізації

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

Розглядаючи деяку довільну систему, що описується m рівняннями з n невідомими, можна виділити три основні типи завдань. Якщо m=n, завдання називають алгебраїчною. Таке завдання зазвичай має одне рішення. Якщо m>n, завдання перевизначена і, зазвичай, немає решения. Нарешті, при m

Перш ніж розпочати обговорення питань оптимізації, введемо низку визначень.

Проектні параметри

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

X1, x2, x3, ..., xn.

Цільова функція

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

M = M (x 1, x 2, ..., x n).

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

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

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

Рис.1.Одномірна цільова функція.

Рис.6.2.Двомірна цільова функція.

замкнутої математичної форми, в інших випадках вона може

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

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

Пошук мінімуму та максимуму

Одні алгоритми оптимізації пристосовані для пошуку максимуму, інші – для пошуку мінімуму. Однак незалежно від типу розв'язуваної задачі на екстремум можна користуватися одним і тим же алгоритмом, так як задачу мінімізації можна легко перетворити на задачу на пошук максимуму, змінивши знак цільової функції на зворотний. Цей прийом ілюструється рис.6.3.

Простір проектування

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

умов, пов'язаних із фізичною сутністю завдання. Обмеження можуть бути настільки сильними, що завдання не матиме жодного

Рис.6.3.Зміною знака цільової функції на протилежний

завдання на максимум перетворюється на завдання на мінімум.

задовільного рішення. Обмеження поділяються на дві групи: обмеження – рівності та обмеження – нерівності.

Обмеження – рівності

Обмеження – рівності – це залежність між проектними параметрами, які мають враховуватися при знайденні рішення. Вони відбивають закони природи, економіки, права, панівні смаки та наявність необхідних матеріалів. Число обмежень – рівностей може бути будь-яким. Вони мають вигляд

C 1 (x 1 x 2 ..., x n) = 0,

C 2 (x 1 x 2 ..., x n) = 0,

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

C j (x 1 x 2 ... x n) = 0.

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

Обмеження – нерівності

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

z 1 r 1 (x 1 , x 2, ..., x n) Z 1

z 2 r 2 (x 1, x 2, ..., x n) Z 2

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

z k r k (x 1, x 2, ..., x n) Z k

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

Локальний оптимум

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

Довільна цільова функція може мати декілька

локальних оптимумів.

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

Глобальний оптимум

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

Приклад 6.1

Нехай потрібно спроектувати прямокутний контейнер об'ємом 1м, призначений для перевезення невпакованого волокна. Бажано, щоб на виготовлення таких контейнерів витрачалося якомога менше матеріалу (за умови постійності товщини стінок це означає, що площа поверхні повинна бути мінімальною), так як при цьому він буде дешевшим. Щоб контейнер було зручно брати автонавантажувачем, його ширина повинна бути не менше 1,5м.

Сформулюємо це завдання у вигляді, зручному застосування алгоритму оптимізації.

Проектні параметри: x 1, x 2, x 3.

Цільова функція (яку потрібно мінімізувати) - площа бічної поверхні контейнера:

A = 2 (x 1 x 2 + x 2 x 3 + x 1 x 3), м2.

Обмеження - рівність:

Об'єм = x 1 x 2 x 3 = 1м3.

Обмеження - нерівність:

Завдання лінійного програмування

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

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

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

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

У загальному виглядізавдання ЛП має такий вигляд:

, (5.1)

, , (5.2)

, , (5.3)

де , , – задані постійні величини.

Функцію (5.1) називають цільовою функцією; системи (5.2), (5.3) – системою обмежень; умова (5.4) – умовою невід'ємності проектних властивостей.

Сукупність проектних параметрів, що задовольняють обмеженням (5.2), (5.3) та (5.4), називають допустимим рішеннямабо планом.

Оптимальним рішеннямабо оптимальним планомЗавдання ЛП називається допустиме рішення , при якому цільова функція (5.1) набуває оптимального (максимальне або мінімальне) значення.

Стандартним завданнямЛП називають завдання знаходження максимального (мінімального) значення цільової функції (5.1) за умови (5.2) та (5.4), де , , тобто. тобто. обмеження лише у вигляді нерівностей (5.2) та всі проектні параметри задовольняють умові невід'ємності, а умови у вигляді рівностей відсутні:

,

, , (5.5)

.

Канонічним (основним) завданнямЛП називають завдання знаходження максимального (мінімального) значення цільової функції (5.1) за умови (5.3) та (5.4), де , , тобто. тобто. обмеження лише у вигляді рівностей (5.3) та всі проектні параметри задовольняють умові невід'ємності, а умови у вигляді нерівностей відсутні:

,

.

Канонічну задачу ЛП можна також записати в матричній та векторній формі.

Матрична форма канонічної задачі ЛП має такий вигляд:

Векторна форма канонічного завдання ЛП.

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

Будуємо в системі координат х 1 ох 2 прямі

Знаходимо напівплощини, що визначаються системою. Так як нерівності системи виконується для будь-якої точки з відповідної напівплощини, їх достатньо перевірити для будь-якої однієї точки. Використовуємо точку (0; 0). Підставимо її координати у першу нерівність системи. Т.к. , то нерівність визначає напівплощину, що не містить точку (0; 0). Аналогічно визначаємо інші напівплощини. Знаходимо безліч допустимих рішень як загальну частину отриманих напівплощин - це заштрихована область.

Будуємо вектор та перпендикулярно до нього пряму нульового рівня.

Переміщуючи пряму (5) у напрямку вектора і бачимо, що область максимальна точка буде в точці А перетину прямий (3) і прямий (2). Знаходимо розв'язання системи рівнянь:

Отже, отримали точку (13; 11) і.

Переміщуючи пряму (5) у напрямку вектора і бачимо, що область мінімальна точка буде в точці В перетину прямий (1) і прямий (4). Знаходимо розв'язання системи рівнянь:

Отже, отримали точку (6; 6) і.

2. Меблева фірма виробляє комбіновані шафи та комп'ютерні столики. Їх виробництво обмежене наявністю сировини (високоякісних дощок, фурнітури) і часом роботи верстатів, що їх обробляють. Для кожної шафи потрібно 5 м2 дощок, для столу – 2 м2. На одну шафу витрачається фурнітури на 10 $, на один столик також на 8 $. Фірма може отримувати від своїх постачальників до 600 м2 дощок на місяць та фурнітури на 2000 $. Для кожної шафи потрібно 7 годин роботи верстатів, для столу – 3 години. На місяць можна використовувати всього 840 годин роботи верстатів.

Скільки комбінованих шаф та комп'ютерних столиків фірмі слід випускати на місяць для отримання максимального прибутку, якщо одна шафа приносить 100 $ прибутку, а кожен стіл - 50 $?

• 1. Скласти математичну модель завдання та вирішити її симплексним методом.
• 2. Скласти математичну модель двоїстої задачі, записати її рішення, виходячи з рішення вихідної.
• 3. Встановити ступінь дефіцитності використовуваних ресурсів та обґрунтувати рентабельність оптимального плану.
• 4. Дослідити можливості подальшого збільшення випуску продукції залежно від використання кожного виду ресурсів.
• 5. Оцінити доцільність запровадження нового виду продукції - книжкових полиць, якщо виготовлення однієї полиці витрачається 1 м 2 дощок і фурнітури на 5$,і потрібно витратити 0,25 години роботи верстатів і прибуток від однієї полиці становить 20$.
• 1. Побудуємо математичну модель для цієї задачі:

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

Завдання вирішуємо симплекс-метод. Запишемо її в канонічному вигляді:

Запишемо ці завдання у вигляді таблиці:

Таблиця 1

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