Лінійні математичні моделі. Математичні моделі задач лінійного програмування Загальний вигляд моделі лінійного програмування

Державний освітній заклад вищого

професійної освіти

"Московський державний технічний університет ім. Н.Е. Баумана"

Калузька філія

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

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

Теоретична частина.

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

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

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

є рівності, то завдання лінійного програмування записано в канонічній формі.

,

Обмеження:

1. Праві частини всіх обмежень мають бути невід'ємними . Якщо якийсь із коефіцієнтів< 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;

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

Якщо вихідні обмеження визначають витрату деякого ресурсу (знак ""), то змінні слід інтерпретувати як залишок або невикористану частину ресурсу. І тут – залишкова змінна і вводиться у рівняння зі знаком "+".

Якщо вихідні обмеження визначають надлишок деякого ресурсу (знак ""), то вводиться надмірна змінна знаком "-".

Змінні:

Усі змінні би мало бути негативними, тобто. .

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

Якщо така змінна потрапляє до оптимального рішення, то

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

Підлягає максимізації чи мінімізації.

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

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

(1)

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

У системі (1) число змінних (невідомих n більше, ніж число обмежень m. Вважатимемо, що ранг цієї системи дорівнює m (система ненадмірна) і що система (1) спільна. Тоді m змінних із загального їх числа утворюють базисні змінні, а решта змінних називають небазисними.Якщо система рівнянь має рішення, то вона має і базисне рішення.Рішення системи рівнянь (1) називають допустимим, якщо всі його компоненти невід'ємні.Якщо система лінійних рівнянь має допустиме рішення, то вона має і базисне допустиме рішення. всіх допустимих рішень системи (1) є опукла множина, тобто безліч рішень задачі лінійного програмування опукло. Оскільки це безліч утворено площинами (гіперплощинами), то воно має вигляд опуклого багатогранника. або вершині) Якщо існує оптимальне рішення задачі лінійного програмування, то існує базово е оптимальне рішення.

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

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

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

Перший крок під час використання графічного методу у геометричному поданні допустимих рішень, тобто. побудову області допустимих рішень (ОДР.), у якій одночасно задовольняються всі обмеження моделі. При отриманні графічного рішення змінна відкладається горизонтальною осі, а – вертикальною. При формуванні ОДР необхідно запобігти отриманню неприпустимих рішень, пов'язаних із необхідністю виконання умови невід'ємності змінних. Перед побудовою необхідно визначити квадранти, в яких розташовуватиметься ОДР. Квадранти визначаються знаками змінних та . Умови невід'ємності змінних обмежують область їх допустимих значень першим квадрантом. Якщо змінна не обмежена у знаку, область обмежується першим і другим квадрантом, якщо , то – першим і четвертим квадрантом. Інші межі простору рішень на площині зображені прямими лініями, побудованими за рівняннями обмежень за умови заміни знака на знак "=". При цьому необхідно враховувати таке: праві частини всіх обмежень мають бути невід'ємними . Якщо якесь обмеження< 0, то необходимо коэффициенты соответствующего ограничения слева и справа до-множить на "-1" и изменить знак неравенства данного ограничения на противоположный. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.

В результаті побудов виходить багатокутник, який визначає простір розв'язків. Якщо одне з обмежень має знак "=", то ОДР вироджується у відрізок.

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

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

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

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

Пряме завдання.

Розглянемо задачу лінійного програмування у канонічній формі:

Знайти максимум (мінімум) функції за умов

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

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

Обчислювальні процедури симплекс – методу.

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

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

Позначимо: – загальну кількість змінних у ЗЛП, представленій у канонічній формі; - Кількість вихідних змінних; - кількість обмежень; - кількість додаткових змінних, тоді .

Кожна вершина багатогранника рішень має - ненульові змінні і () - нульові змінні.

Ненульові змінні називаються базовими, нульові змінні – небазисними.

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

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

При виборі початкового допустимого базису для складання симплекс-таблиці на першому кроці СТ(0) вихідні змінні прирівнюються до нуля і є небазисними, серед введених додаткових змінних вибираються змінні з рівними коефіцієнтами одиниці. Змінні в рівності (2) - (4) є базисними і - рядок входять з коефіцієнтами, рівними 0. Для заповнення симплекс-таблиці необхідно цільову функцію перетворити на вид . Таким чином, остаточно отримуємо:

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

у крайньому лівому стовпці розташовуються базисні змінні та ;

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

у першому рядку розташовуються змінні у визначеному порядку:

Спочатку , потім небазисні змінні, базисні змінні розташовуються останніх стовпцях перед правої частиною (ПЧ). Запишемо коефіцієнти у СТ(0):

Оптимальність будь-якої з вершин визначається коефіцієнтами при небазових змінних – рядку поточної симплекс-таблиці:

Для завдання максимізації дана вершина є оптимальною, якщо всі коефіцієнти при небазових змінних - рядку є невід'ємними (>0);

Для завдання мінімізації дана вершина є оптимальною, якщо всі коефіцієнти при небазисних змінних – рядку є непозитивними (< 0).

Якщо в задачі максимізації (мінімізації) у однієї небазисної змінної – рядку коефіцієнт<0(>0), то поточна точка не є оптимальною і необхідно змінити базис. Для цього вибирають небазову змінну, що має максимально негативний (позитивний) коефіцієнт - рядку. Вибрана небазова змінна буде включатися в новий базис, тому називається змінною, що включається. Базисна змінна, яка буде виведена з базису, називається змінною, що виключається.

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

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

Рядок змінної, що виключається, будемо називати роздільною здатністю.

Перетин роздільного стовпця і рядки визначають роздільну здатність (РЕ).

Щоб визначити змінну, що виключається, необхідно:

розділити праві частини всіх базисних змінних (крім - рядки) на відповідні позитивні коефіцієнти стовпця;

вибрати із отриманих відносин найменше.

Ділити на "0" і негативну величину не можна, тому що це призводить до відсутності вершини, що перетинається, або до вершини поза ОДР.

Для переходу в суміжну вершину необхідно сформувати матрицю переходу B(0), яка визначить зв'язок між СТ(0) та СТ(1): СТ(1) = В(0) СТ(0).

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

Кожен елемент j - стовпця ділиться на РЕ і змінює знак на протилежний, крім роздільної здатності елемента.

Штучний початковий базис. М – метод.

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

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

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

Властивість М: При додаванні (відніманні) з будь-якою кінцевою величиною, що визначає будь-яке значення, яке може набувати кожна зі змінних вихідної ЗЛП, її значення (змінної М) не змінюється, а саме,

Формула (1.2), обмежень не негативності змінних (є, ні) - формула (1.3) (1.1) i = 1,… m (1.2) (1.3) Алгоритм розв'язання задач лінійного програмування вимагає приведення їх постановки в канонічний вигляд, коли цільова функція ...

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

Покажемо, як можна перейти від завдання з обмеженнями-нерівністю до основного завдання лінійного програмування.

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

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

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

де - деякі нові змінні, які ми називатимемо «додатковими». Відповідно до умов (4.1), ці додаткові змінні так само, як і мають бути невід'ємними.

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

Як видно, перед нами у чистому вигляді основне завдання лінійного програмування (ОЗЛП). Рівняння (4.3) задані у формі, вже дозволеній щодо базисних змінних, які виражені через вільні змінні Загальна кількість змінних дорівнює , з них «початкових» та «додаткових». Функція L виражена лише через «первісні» змінні (коефіцієнти при «додаткових» змінних у ній дорівнюють нулю).

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

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

та звертають у мінімум лінійну функцію

Потрібно привести це завдання до виду ОЗЛП.

Рішення. Наводимо нерівності (4.4) до стандартної форми;

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

Завдання зводиться до того, щоб знайти невід'ємні значення змінних

що задовольняють рівнянням (4.6) та обертають у мінімум лінійну функцію (4.5).

Ми показали, як від задачі лінійного програмування з обмеженнями-нерівностями можна перейти до задачі з обмеженнями-рівністю (ОЗЛП). Завжди можливий і зворотний перехід - від ОЗЛП до завдання з обмеженнями-нерівністю. Якщо у першому випадку ми збільшували число змінних, то у другому випадку його зменшуватимемо, усуваючи базисні змінні і залишаючи лише вільні.

Приклад 2. Є завдання лінійного програмування з обмеженнями-рівністю (ОЗЛП):

та мінімізованою функцією

Потрібно записати її як завдання лінійного програмування з обмеженнями-нерівністю.

Рішення. Оскільки , то виберемо якісь дві зі змінних як вільні. Зауважимо, що змінні як вільні вибирати не можна, оскільки вони пов'язані першим із рівнянь (4 7): значення однієї з них повністю визначається значенням іншої, а вільні змінні мають бути незалежними

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

Оскільки умови (4 9) можуть бути замінені нерівностями:

Перейдемо у вираженні лінійної функції L до вільних змінних Підставляючи L замість і їх вирази (4.9). отримаємо.

Основою вирішення економічних завдань є математичні моделі.

Математичною моделлюЗавдання називається сукупність математичних співвідношень, що описують суть задачі.

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

Змінними завданняназиваються величини Х1, Х2, Хn, що повністю характеризують економічний процес. Зазвичай їх записують як вектора: X=(X 1 , X 2 ,...,X n).

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

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

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

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

Допустимим рішенням(планом) задачі лінійного програмування називається будь-який n-мірний вектор X=(X 1 , X 2 ,...,X n), що задовольняє системі обмежень та умов невід'ємності.

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

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

Приклад складання математичної моделі

Завдання використання ресурсів (сировини)

Умова:Для виготовлення n видів продукції використовується m видів ресурсів. Скласти математичну модель.

Відомі:

• b i (i = 1,2,3,..., m) - запаси кожного i-го виду ресурсу;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) - витрати кожного i-го виду ресурсу на виробництво одиниці обсягу j-го виду продукції;
• c j (j = 1,2,3,..., n) - прибуток від одиниці обсягу j-го виду продукції.

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

Рішення:

Введемо вектор змінних X = (X 1, X 2, ..., X n), де x j (j = 1,2, ..., n) - Обсяг виробництва j-го виду продукції.

Витрати i-го виду ресурсу виготовлення даного обсягу x j продукції рівні a ij x j , тому обмеження використання ресурсів виробництва всіх видів продукції має вид:
Прибуток від j-го виду продукції дорівнює c j x j , тому цільова функція дорівнює:

Відповідь- Математична модель має вигляд:

Канонічна форма задачі лінійного програмування

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

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

Вона може бути представлена ​​в координатному, векторному та матричному записі.

Канонічна задача лінійного програмування в координатному записі має вигляд:

Канонічна задача лінійного програмування в матричному записі має вигляд:

• А - матриця коефіцієнтів системи рівнянь
• Х - матриця-стовпець змінних завдання
• Ао - матриця-стовпець правих частин системи обмежень

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

Приведення загального завдання лінійного програмування до канонічної форми

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

Візьмемо лінійну нерівність a 1 x 1 +a 2 x 2 +...+anxn ≤b і додамо до її лівої частини деяку величину x n+1 , таку, що нерівність перетворилася на рівність a 1 x 1 +a 2 x 2 + ...+anxn +x n+1 =b. У цьому дана величина x n+1 є неотрицательной.

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

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

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

3.1. Загальне завдання лінійного програмування

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

Лінійне програмування включає у собі низку евристичних (наближених) методів розв'язання, дозволяють за заданих умов із усіх можливих варіантів рішень виробничих завдань вибрати найкращий, оптимальний. До цих методів належать такі – графічний, симплексний, метод потенціалів (модифікований розподільчий метод – МОДІ), Хічкова, Креко, метод апроксимації Фогеля та інші.

Частина цих методів поєднують загальною назвою – розподільний, або транспортний, метод.

Батьківщиною лінійного програмування є Росія. Перші роботи з лінійного програмування майбутнім академіком Л.В. Канторовичем було опубліковано у 1939 р. У 1975 р. за розробку методів лінійного програмування їм було отримано Нобелівську премію з економіки. Оскільки більшість робіт академіка Л.В. Канторовича присвячено вирішенню транспортних завдань, вважатимуться, що вказана Нобелівська премія зазначає і досягнення російської транспортної науки.

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

Особливості моделі лінійного програмування полягають у наступному:

Цільова функція та обмеження виражені лінійними залежностями (рівностями або нерівностями);

Число залежностей завжди менше числа невідомих (умова невизначеності);

Невід'ємність шуканих змінних. Загальна форма запису моделі лінійного програмування у скороченому вигляді виглядає так:

Знайти х ij ≥ 0 (j = 1, 2...n) при обмеженнях наступного типу:

Ці обмеження мінімізують (або максимізують) цільову функцію

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

а 11 х 1 + а 12 х 2 + … + а 1 n х n = b 1;

а 21 х 1 + а 22 х 2 + … + а 2 n х n = b 2 ; (3.1)

……………………………..

a m х 1 + а m 2 х 2 + … + а mn х n = b m.

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

а 11 х 1 + а 12 х 2 + … + а 1 n х n ≤ b 1;

а 21 х 1 + а 22 х 2 + … + а 2 n х n ≤ b 2 ; (3.2)

……………………………..

a m х 1 + а m 2 х 2 + … + а mn х n ≤ b m.

то цей запис наводиться до канонічноїформі (3.1) шляхом запровадження додаткових змінних х n +1> 0 (i=1,2…m) у ліву частину нерівності (або скорочення числа змінних, якщо знак нерівності спрямований в інший бік). Додаткові змінні становлять базис.

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

L = с 1 х 1 + с 2 х 2 …з n х n → min, (3.3)

де з 1, з 2 … з n- Коефіцієнти цільової функції Lпри змінних х j.

У цільову функцію додаткові змінні входять із нульовими коефіцієнтами.

У разі максимізації цільової функції Lслід знаки при змінних цільової функції змінити на протилежні, і ми знову дійдемо завдання мінімізації, тобто. одне завдання зводиться до іншої заміни Lна – Lабо max L= min (– L).

Базовим рішенням системи лінійних рівнянь (3.1) називається рішення, в якому небазисним змінним надано нульові значення.

Допустимим називається таке базисне рішення, у якому що у базис змінні є неотрицательными.

Оптимальним називається допустиме рішення, що максимізує (або мінімізує) цільову функцію (3.3).

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

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

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

3.2. Графоаналітичний метод

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

Розв'язання задачі з двома змінними х 1і х 2, які за змістом завдання не повинні бути негативними, виконується у системі декартових координат. Рівняння х 1=0 і х 2= 0 є осями системи координат першого квадранту

Метод вирішення розглянемо на конкретному прикладі.

Приклад 3.1.На складі є 300 т виробів із пінобетону та 200 т із сталі. Автопідприємству необхідно доставити ці вироби на об'єкт, що будується. На автопідприємстві є вантажні автомобілі КамАЗ - 5320 та

ЗІЛ-4314. За одну поїздку КамАЗ-5320 може доставити 6 т пінобетону та 2 т сталі, а прибуток від їздки становитиме 4 тис. руб. ЗІЛ-4314 за одну поїздку доставляє 2 т пінобетону та 4 т сталі, прибуток від їздки становить 6 тис. руб. Необхідно організувати перевезення те щоб забезпечити автопідприємству найбільший прибуток.

Побудуємо математичну модель завдання. Позначимо через х 1 потрібну кількість їздок КамАЗ-5320 і через х 2 шукана кількість їздок ЗІЛ-4314.

Загальне перевезення виробів з пінобетону складає 6 х 1+ 2х 2, а зі сталі 2 х 1+ 4х 2. Обмеження з перевезення, виходячи з наявної кількості виробів, становлять 6 х 1+ 2х 2 ≤ 300т по пінобетону та 2 х 1+ 4х 2 ≤ 200т по сталі.

Сумарний прибуток у тис. руб. виражається величиною 4 х 1 + 6х 2 , яку потрібно максимізувати і яка є критерієм оптимальності в даній задачі. Математична модель завдання, таким чином, виглядає такою. Необхідно максимізувати цільову функцію

L = 4х 1+ 6х 2 → mах за умов: 6 х 1+ 2х 2 ≤ 300; 2х 1+ 4х 2 ≤ 200; х 1 ≥ 0;х 2 ≥ 0.

Розглянемо рівняння 6 х 1+ 2х 2 = 300. Щоб побудувати пряму, що описується цим рівнянням, знайдемо дві точки, що лежать на цій прямій. При х 1= 0 із рівняння прямий знайдемо 2 х 2 = 300, звідки х 2 = 150. Отже, точка А з координатами (0,150) лежить на прямій. При х 2= 0 маємо 6 х 1= 300, звідки х 1 = 50, а точка Dз координатами (50,0) також знаходиться на прямій. Через ці дві точки проводимо пряму AD(Рис. 3.1).

Лінійна нерівність 6 х 1+ 2х 2 ≤ 300 являє собою напівплощину, розташовану з однієї зі сторін від побудованої прямої 6 х 1+ 2х 2 = 300. Щоб з'ясувати, з якого боку цієї прямої розташовані точки шуканої напівплощини, підставимо в нерівність 6 х 1+ 2х 2 ≤ 300 координати будь-якої точки, що не лежить на граничній прямій. Наприклад, початок координат 0-(0,0). Для нього справедлива нерівність 6∙0 + 2∙0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой ADта на рис. 3.1 заштрихована.

Рівняння 2 х 1+ 4х 2= 200 побудуємо за двома точками. При х 1 = 0 4х 2 = 200, звідки х 2 = 50. Тоді точка Емає координати (0,50) і належить прямій. При х 2= 0, 2х 2 = 200, точка ззнаходиться на даній прямій з координатами (100,0). Підставивши в нерівність координати точки з(0,0), отримаємо 2∙0 + 4∙0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2х 1+ 4х 2= 200.

Система обмежень завдання вимагає, щоб плани ( х 1; х 2) задовольняли всім чотирьом нерівностям, тобто допустимі плани – точки ( х 1; х 2) повинні одночасно перебувати у всіх чотирьох напівплощинах. Цій вимогі відповідають лише точки, розташовані всередині та на межі багатокутника OEKDщо є багатокутником допустимих рішень.

Вершинами багатокутника допустимих рішень є точки O, E, K, D,відрізки прямих OE, EK, KD, OD- Його ребра. Будь-яка точка багатокутника OEKDє планом завдання, задовольняючи її умови. Вершини багатокутника утворені перетином двох прямих і відповідають опорним планам завдання, серед яких і найкращий (оптимальний) план. Таким чином, опорних планів буде стільки, скільки вершин багатокутника допустимих рішень.

Наочне геометричне уявлення можна отримати і для цільової функції L = 4х 1+ 6х 2. Зафіксуємо будь-яке значення цільової функції, наприклад L= 120. рівняння 4 х 1+ 6х 2 = 120 визначає пряму, що проходить через точку Вз координатами (х 1 = 0; х 2 = 20) та точку Lз координатами (( х 1 = 30; х 2 = 0). Відрізок ВLлежить усередині багатокутника OEKD. Отже, для всіх планів (точок) цього відрізка значення цільової функції однаково і дорівнює 120. Надаючи інші значення цільової функції, отримаємо паралельні прямі, які називають лініями рівняцільової функції.

Переміщаючи пряму Lпаралельно самої собі в одному напрямку, отримаємо зростання цільової функції, а в протилежному напрямку – її спадання. У прикладі, що розглядається, пересування прямої ВLправо визначає зростання цільової функції, яку ми максимізуємо. Так робимо доти, доки пряма ВLматиме хоча б одну загальну точку з багатокутником допустимих рішень OEKD. З рис. 3.1 слід, що останньою точкою, яку перетне пряма рівня цільової функції, буде точка До. Це означає, що точка Довизначає оптимальний план задачі.

Напрямок зростання, перпендикулярний до лінії рівня, називається напрямом найбільшого зростанняцільової функції та визначає її максимальний приріст. Цей напрям можна встановити без побудови ліній рівня. Для цього необхідно на осях х 1і х 2відкласти відрізки, рівні коефіцієнтам цільової функції, і з них, як у координатах, побудувати вектор максимального зростання цільової функції. У математиці його називають градієнтомта позначають знаком grad. Градієнтом для функції L = 4х1 + 6х2буде вектор n| 4; 6 | . Для зручності його побудови збільшимо координати, наприклад, удесятеро, тобто. n | 40; 60 | . Побудуємо градієнт цільової функції Lдля чого з'єднаємо точку з координатами (40; 60) з початком координат. Лінії рівня цільової функції будують перпендикулярно напряму градієнта.

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

6х 1+ 2х 2= 300;

2х 1+ 4х 2= 200.

Зрівняємо коефіцієнти при х 1 помноживши друге рівняння на 3, і віднімемо з другого рівняння перше. Отримаємо 10 х 2= 300,х 2 = 30. Підставивши значення х 2 = 30 у будь-яке з рівнянь, наприклад перше, визначимо значення х 1:

6х 1+ 2х · 30 = 300,

звідки 6 х 1 = 300 - 60 = 240, отже, х 1 = 40.

Таким чином, щоб отримати найбільший прибуток автопідприємству, необхідно виконати 40 їздок на КамАЗ-5320 та 30 їздок на ЗІЛ-4314. Максимальний прибуток при цьому становитиме

L = 4х 1+ 6х 2= 4 · 40 + 6 · 30 = 340 тис. руб.

На основі розглянутого прикладу та геометричної інтерпретації задачі оптимізації з двома змінними можна зробити такі висновки:

1) у двомірному просторі область допустимих рішень є багатокутником;

2) кожній стороні багатокутника відповідає значення однієї змінної, що дорівнює нулю;

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

4) кожному значенню цільової функції відповідає пряма;

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

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

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

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

На рис. 3.2,б зображені неопуклі множини. У невипуклих множинах можна вказати хоча б дві точки відрізка АВ, що не належать множині, що розглядається.

3.3. Симплексний метод

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

Симплексний метод включає отримання невід'ємного базисного рішення системи канонічних лінійних рівнянь типу (3.1), наступну мінімізацію (максимізацію) цільової функції (3.3) та знаходження у такий спосіб оптимальних значень шуканих змінних х 1, х 2… х n.

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

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

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

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

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

Нехай необхідно мінімізувати лінійну форму

L = з 1 х 1 + з 2 х 2 + … з n х n.

За умов (для наочності нульові та одиничні коефіцієнти в рівняннях збережені):

1х 1+ 0х 2 + … 0х m + a 1m+ 1x m+1 …+a 1n x n = b 1;

0х 1+ 1х 2+… 0х m + a 2m+ 1x m+1 …+a 2n x n = b 2;

……………………………………………

0х 1+ 0х 2 + … 1х m + a mm + 1x m +1 … + a mn x n = b m.

У цій системі рівнянь вже є готовий базис, оскільки кожне рівняння обмежень містить невідому з коефіцієнтом, рівним одиниці, якої немає в інших рівняннях, тобто коефіцієнтів при змінних х 1 , х 2 …, х mможна скласти поодиноку матрицю.

Розв'яжемо рівняння щодо базисних змінних:

х 1 = b 1 - (a 1m + 1 · х m + 1 ... + a 1n x n);

х 2 = b 2 - (a 2m + 1 · х m + 1 ... + a 2n x n);

………………………………

х m = b m – (a mm+ 1x m+1 …+ a mn x n),

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

L=c 1 b 1 +c 2 b 2 +cmbm –(c 1 a 1m +c 2 a 2m+1 +…+cma mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+cma mn)xn …+cnx n.

Змінні х 1 , х 2 …, х m, за допомогою яких знайдено перший базисний план, є базисними, а інші x m +1, x m +2, ... x n -вільними. Базисних змінних має бути стільки, скільки рівнянь у системі. З умови неотрицательности, найменше значення вільних змінних дорівнює нулю. Отримане базисне рішення системи рівнянь і його початковим допустимим рішенням, тобто. x 1 = b 1 x 2 = b 2 … x m = b m x m +1 = 0,…, x n = 0.

Цьому рішенню відповідає значення цільової функції

L = з 1 b 1 + з 2 b 2 + … з m b m.

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

Симплексні таблиці становлять так (див. табл. 3.1). Вгорі таблиці поміщають усі змінні х 1 , х 2 …, х nта коефіцієнти c j, з якими відповідні змінні входять до цільової функції. Перший стовпець c iскладається з коефіцієнта цільової функції при змінних, що у базис. Потім слід стовпець базисних змінних та вільних членів рівнянь. Елементи інших стовпців таблиці є коефіцієнти при змінних, із якими останні входять у систему рівнянь. Таким чином, кожному рядку таблиці відповідає рівняння системи, вирішене щодо базової змінної. У таблиці показаний варіант плану, який відповідає цільової функції при даному базисі.

Нижній рядок таблиці називається індексної. Кожен її елемент (оцінка) ∆ jвизначають

∆j = z j - c j ,

де c j– коефіцієнти за відповідних змінних у цільовій функції; z j –сума творів коефіцієнтів цільової функції за базових змінних на відповідні змінні – елементи j-го стовпця таблиці.

Таблиця 3.1

Симплексна таблиця з початковим допустимим

Лекція 2

В канонічної форми

допустимим рішенням ЗЛП(допустимим планом).

оптимальним рішенням ЗЛП.

Необхідність

Приклад.

Запишемо завдання в канонічної форми

Особливі ситуації графічного рішення ЗЛП

Крім випадку, коли завдання має єдине оптимальне рішеннядля і , можуть бути особливі ситуації:

1. завдання має безліч оптимальних рішень - Екстремум функції досягається на відрізку ( альтернативний оптимум)- Рисунок 2;

2. завдання не можна розв'язати через необмеженість ОДР, або – рисунок 3;

3. ОДР - єдина точка А, тоді;

4. завдання не можна розв'язати якщо ОДР є порожня область.

А

Малюнок 2 Малюнок 3

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

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

Приклад. Розв'язати графічно завдання лінійного програмування ( альтернативний оптимум):

Запитання для самоконтролю

1. Запишіть задачу лінійного програмування у загальній формі.

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

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

4. Дайте визначення допустимого та оптимального розв'язання задачі лінійного програмування.

5. Яке з рішень і є «кращим» для завдання мінімізації функції, якщо ?

6. Яке з рішень і є «кращим» для завдання максимізації функції, якщо ?

7. Запишіть стандартну форму математичної моделі задачі лінійного програмування із двома змінними.

8. Як побудувати напівплощину, задану лінійною нерівністю з двома змінними ?

9. Що називається розв'язанням системи лінійних нерівностей із двома змінними? Побудуйте на площині область допустимих розв'язків такої системи лінійних нерівностей, яка:

1) має єдине рішення;

2) має безліч рішень;

3) немає жодного рішення.

10. Запишіть для лінійної функції градієнт вектор, назвіть вигляд ліній рівня. Як розташовані відносно один одного градієнт та лінії рівня?

11. Сформулюйте алгоритм графічного методу розв'язання стандартної ЗЛП із двома змінними.

12. Як знайти координати рішення та значення ?

13. Побудуйте область допустимих рішень, градієнт та лінії рівня для завдань лінійного програмування, в яких:

1) досягається в єдиній точці, а - на відрізку ОДР;

2) досягається в єдиній точці ОДР, а .

14. Дайте геометричну ілюстрацію ЗЛП, якщо вона:

1) має єдині оптимальні рішення для і;

2) має безліч оптимальних рішень для .

Лекція 2

графічний метод знаходження оптимального рішення

1. Форми лінійних математичних моделей та їх перетворення

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

3. Особливі ситуації графічного рішення ЗЛП

4. Графічне вирішення економічних завдань лінійного програмування

Форми лінійних математичних моделей та їх перетворення

Математична модель задачі лінійного програмування (ЗЛП) може бути записана однією з трьох форм.

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

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

У стандартній формі математичної моделі потрібно знайти максимум або мінімум функції; всі обмеження є нерівністю; всі змінні невід'ємні.

Рішення системи обмежень, що задовольняє умовам невід'ємності змінних, називають допустимим рішенням ЗЛП(допустимим планом).

Багато допустимих рішень називають областю допустимих рішень ЗЛП.

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

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

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

Перехід до канонічної форми запису ЗЛП.

Приклад.

Запишемо завдання в канонічної форми, Вводячи в ліву частину першої нерівності системи обмежень додаткову (балансову) змінну зі знаком «+», а в ліву частину другої нерівності додаткову змінну зі знаком «мінус».

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

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