Вирішення задач лінійного програмування графічним методом презентація до уроку з алгебри на тему. Лінійне програмування Презентація графічного методу лінійного програмування

Вирішення систем лінійних нерівностей

Нерівності

Лінійні нерівності – це нерівності виду ∑ai xi +b≥c

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

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

Розглянемо рівняння першого ступеня з двома невідомими x та y

Тлумачуючи x та y як координати точки

на площині, можемо сказати, що

множина точок, що визначаються рівнянням (1), є пряма лінія на площині.

Геометричний сенс рівняння першого ступеня

Аналогічно для нерівності ax+by+c≥0. (2)

Якщо b≠0, то ця нерівність наводиться до одного з видів у≥kх+p або у≤kх+р.

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

Якщо ж b=0, то нерівність наводиться одному з видів х≥h або х≤h. Першому з них задовольняють всі точки, що лежать «правіше» прямої х = h або на цій прямій, другому – всі точки, що лежать «лівіше» прямої х = h або на цій прямій.

Геометричний сенс системи лінійних нерівностей

Нехай дана система нерівностей із двома невідомими х і у. a1 x+b1 y+c1 ≥0,

a2 x+b2 y+c2 ≥0,

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

am x+bm y+cm ≥0.

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

Приклад

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

Необмежена область рішень

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

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

Щоб завантажити архів з документом, в полі, розташоване нижче, впишіть п'ятизначне число та натисніть кнопку "Завантажити архів"

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

Завдання оптимізації. Обмеження на допустиму множину. Класична задача оптимізації. Функція лагранжа. Лінійне програмування: формулювання завдань та його графічне рішення. Алгебраїчний метод розв'язання задач. Симплекс-метод, симплекс-таблиця.

реферат, доданий 29.09.2008

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

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

Загальні завдання лінійного програмування. Опис алгоритму симплекс-метода, записаного у канонічній формі з односторонніми обмеженнями. Алгоритм побудови початкового опорного плану на вирішення задачи. Розширений алгоритм штучного базису.

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

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

реферат, доданий 21.08.2008

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

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

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

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

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

Прийняття рішень за умов невизначеності Якщо перший суб'єкт має m стратегій, а другий - n стратегій, то кажуть, що маємо справу з грою m x n. Розглянемо гру m x n. Нехай задано безліч стратегій: для першого гравця (Аi), для другого гравця (Bj), платіжна матриця, де aij – виграш першого гравця або програш другого гравця під час вибору ними стратегій Аi та Bj відповідно. Кожен із гравців вибирає однозначно з ймовірністю I деяку стратегію, тобто. користується під час виборів рішення чистою стратегією. При цьому рішення гри буде у чистих стратегіях. Оскільки інтереси гравців протилежні, перший гравець прагне максимізувати свій виграш, а другий гравець, навпаки, мінімізувати свій програш. Рішення гри полягає у визначенні найкращої стратегії кожним гравцем. Вибір найкращої стратегії одним гравцем проводиться за повної відсутності інформації про рішення другим гравцем, що приймається.

Слайд 2

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

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

Слайд 3

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

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

У короткому записі ЗЛП має вигляд: при обмеженнях

Слайд 8

Для складання математичної моделі ЗЛП необхідно: 1) позначити змінні; 2) укласти цільову функцію; 3)записати систему обмежень відповідно до метою завдання; 4)записати систему обмежень з урахуванням наявних за умови завдання показників. Якщо всі обмеження завдання задані рівняннями, модель такого виду називається канонічної. Якщо хоч одне з обмежень дано нерівністю, модель неканонічна.

Слайд 9

Приклади завдань, що зводяться до ЗПЛ.

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

Слайд 10

1. Завдання оптимального розподілу ресурсів.

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

Слайд 11

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

Слайд 12

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

Слайд 13

Приклади

Слайд 14
Припустимо, що буде виготовлено виробів виду А, виробів виду В і виробів виду С. Тоді для виробництва такої кількості виробів потрібно витратити станко-годин фрезерного обладнання. Оскільки загальний фонд робочого часу верстатів даного типу не може перевищувати 120, то має виконуватись нерівність

Слайд 15
Розмірковуючи аналогічно, можна скласти систему обмежень

Слайд 16
Тепер складемо цільову функцію. Прибуток від виробів виду А складе 10 , від реалізації - виробів виду В -14 і зажадав від реалізації - виробів виду С-12 Загальна прибуток за реалізації всіх виробів складе

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

Слайд 18
Приклад 2

Продукцією міськмолокозаводу є молоко, кефір та сметана, розфасовані в тару. На виробництво 1 т молока, кефіру та сметани потрібно відповідно1010,1010 та 9450 кг молока. При цьому витрати робочого часу при розливі 1 т молока та кефіру становлять 0,18 та 0,19 машино-годин. На фасуванні 1 т сметани зайняті спеціальні автомати протягом 3,25 години.

Слайд 19
Усього для виробництва цільномолочної продукції завод може використовувати 136 000 кг молока. Основне обладнання може бути зайняте протягом 21,4 машино-годин, а автомати розфасовки сметани – протягом 16,25 годин. Прибуток від 1 т молока, кефіру і сметани відповідно дорівнює 30, 22 і 136 руб. Завод повинен щодня виробляти щонайменше 100 т молока, розфасованого у пляшки. На виробництво іншої продукції немає обмежень.

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

Слайд 21
Рішення

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

Слайд 22
Обмеження тимчасово за фасуванням молока і кефіру і за розфасовкою сметани. Оскільки щодня має вироблятися щонайменше 100 т молока, то. За економічним змістом

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

Слайд 24
Завдання про суміші.

Є два види продукції, що містять поживні речовини (жири, білки і т.д.)

Слайд 25
Таблиця
Слайд 26
Рішення

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

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

Слайд 28
Введемо позначення: -кількість j-го матеріалу, що входить до суміші; -ціна матеріалу j-го виду; -це мінімально необхідний вміст i-го компонента суміші. Коефіцієнти показують питому вагу i-го компонента в одиниці j-го матеріалу

Слайд 29
Економіко-математична модель завдання.

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

Слайд 30
Завдання про розкрій

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

Слайд 31
Рішення. Припустимо, що з j-ого варіанту розкривається сотень тканини. Оскільки при розкрої тканини за j-им варіантом виходить деталей i-го виду, по всіх варіантах розкрою з тканин буде отримано Загальна величина відходів по всіх варіантах розкрою складе
Слайд 35
Основне завдання ЛП

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

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

Слайд 41
Опорний план називається невиродженим, якщо він містить m позитивних компонентів. Інакше він називається виродженим. План, при якому цільова функція ЗЛП набуває свого максимального (мінімального) значення, називається оптимальним.

Переглянути всі слайди

Опис презентації з окремих слайдів:

1 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевикин, 2004 р. Лінійне програмування До цього класу лінійного програмування (75% розв'язуваних американцями задач) відносяться завдання, в яких цільова функція Wm(x), m=1,2,..., M, обмеження як рівностей hk(x)=0, k=1,2...K, і нерівностей gj(x)>0, j=1,2,...J, - лінійні і немає математичного рішення. Можливі тематики завдань ЛП: раціональне використання сировини та матеріалів; завдання оптимізації розкрою; оптимізації виробничої програми підприємств; оптимального розміщення та концентрації виробництва; на складання раціонального плану перевезень, роботи транспорту; управління виробничими запасами; та багато інших, що належать сфері оптимального планування. Постановка задачі ЛП (визначення показника ефективності, змінних задач, завдання лінійної цільової функції W(x), що підлягає мінімізації або максимізації, функціональних hk(x), gj(x) та обласних xli
2 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевикин, 2004 Приклад задачі ЛП Приклад - Оптимізація розміщення побічного виробництва лісництва Лісництво має 24 га вільної землі під парою і зацікавлено витягти з неї дохід. Воно може вирощувати саджанці гібрида новорічної ялини, що швидко зростає, які досягають стиглості за один рік, або бичків, відвівши частину землі під пасовища. Дерева вирощуються та продаються в партіях по 1000 штук. Потрібно 1.5 га для вирощування однієї партії дерев та 4 га для вигодовування одного бичка. Лісництво може витратити лише 200 год на рік на своє побічне виробництво. Практика показує, що потрібно 20 год. для культивації, підрізання, вирубування та пакетування однієї партії дерев. Для догляду за одним бичком також потрібно 20 год. Лісництво може витратити з цією метою 6 тис. крб. Річні витрати однією партію дерев виливаються в 150 крб. та 1,2 тис. руб. на одного бичка. Вже укладено контракт на постачання 2 бичків. За цінами, одна новорічна ялина принесе прибуток у 2,5 руб., один бичок - 5 тис. руб.

3 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевикин, 2004 Постановка завдання 1. Як показник ефективності доцільно взяти прибуток за операцію (річний прибуток із землі в рублях). 2. В якості керованих змінних завдання слід взяти: x1 - кількість бичків, що відгодовуються, на рік; x2 - кількість партій, що вирощуються, швидкозростаючих новорічних ялинок по 1000 шт. кожна на рік. 3. Цільова функція: 5000 x1 + 2500 x2  max, де 5000 – чистий дохід від одного бичка, руб.; 2500 – чистий дохід від однієї партії дерев (1000 шт. по 2,5 руб.). 4. Обмеження: 4.1. З використання землі, га: 4 x1 + 1,5 x2  24 4.2. По бюджету, руб.: 1200 х1 + 150 х2  6000 4.3. За трудовими ресурсами, год: 20 x1 + 20 x2  200 4.4. Зобов'язання за контрактом, прим.: x1  2 4.5. Обласні обмеження: x1  0, x2  0

4 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевікін, 2004 р. Графічне вирішення задачі ЛП Відображаючи на графіку прямі, що відповідають наступним рівнянням, 4 x1 + 1,5 x2 = 24 1200 x1 + 150 x2 = 6000 20 x1 = 2 x2 = 0 заштриховуємо область, у точках якої виконуються всі обмеження. Кожна така точка називається допустимим рішенням, а множина всіх допустимих рішень називається допустимою областю. Вочевидь, що розв'язання завдання ЛП полягає у відшуканні найкращого рішення у допустимій області, яке, своєю чергою, називається оптимальним. У аналізованому прикладі оптимальне рішення є допустимим рішенням, що максимізує функцію W=5000 x1 + 2500 x2. Значення цільової функції, що відповідає оптимальному рішенню, називається оптимальним значенням завдання ЛП.

5 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевікін, 2004 р. Графічне вирішення завдання ЛП

6 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевикин, 2004 Графічне рішення задачі ЛП Перебір всіх кутових точок області допустимих рішень призводить до знаходження максимального доходу в розмірі 34 тис. руб. (W=5000x1+2500x2), яке лісництво може витягти, вирощуючи 3,6 бичка та 6,4 партії новорічних ялинок. Цілочисленні методи (наприклад, перебір) дають x1=3 і x2=6, що призводить до доходу 30 тис. руб., x1=4 і x2=5 призводить до більш оптимального результату 32,5 тис. руб., точка x1 =3 та x2=7 призводить до аналогічного результату. Графічний метод через велику розмірність реальних практичних завдань ЛП досить рідко застосовується, проте він дозволяє ясно усвідомити одну з основних властивостей ЛП - якщо в задачі ЛП існує оптимальне рішення, то принаймні одна з вершин допустимої області є оптимальним рішенням. Незважаючи на те, що допустима область завдання ЛП складається з нескінченної кількості точок, оптимальне рішення завжди можна знайти шляхом цілеспрямованого перебору кінцевого числа її вершин. Даний симплекс-метод розв'язання задачі ЛП грунтується на цій фундаментальній властивості.

7 слайд

Опис слайду:
Однією з вбудованих функцій редактора електронних таблиць MS Excel (необхідно відзначити галочку під час установки MS Office) є "Пошук рішення". Цей пакет дозволяє швидко вирішувати завдання лінійного та нелінійного програмування.

8 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевікін, 2004 р. Завдання ЛП у стандартній формі Завдання ЛП у стандартній формі з m обмеженнями та n змінними має такий вигляд: W = c1x1 + c2x2 + ... + cnxn  min (max) при обмеженнях a11x1+a12x2+...+a1nxn=b1; a21x1 + a22x2 + ... + a2nxn = b2; ... am1x1 + am2x2 + ... + amnxn = bm; x10; x20;...; xn0 b10; b20;...; bm0 У матричній формі W = cx  min (max) при обмеженнях Ax = b; x0; b0, де A - матриця розмірності m*n, x - вектор-стовпець змінних розмірності n*1, b - вектор-стовпець ресурсів розмірності m*1, з - вектор рядок оцінок задачі ЛП 1*n.

9 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевикин, 2004 р. Перетворення нерівностей Обмеження як нерівностей можна перетворити на рівності з допомогою запровадження так званих залишкових чи надлишкових змінних. Рівняння з попереднього прикладу 4x1 + 1,5x2  24 можна перетворити на рівність за допомогою залишкової неотрицательной змінної 4x1 + 1,5x2 + x3 = 24. Змінна x3 неотрицательна і відповідає різниці правої та лівої частин нерівності. Аналогічно x1  2 можна перетворити шляхом запровадження надмірної змінної x4: x1 - x4 = 2.

10 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевікін, 2004 Преобр-е неогр. по знаку перем-х Перетворення необмежених по знаку змінних Змінні, які набувають як позитивних, і негативні значення, слід замінювати різницею двох неотрицательных: x = x+ - x-; x+0; x-  0. Приклад. 3x1+4x2+5x3+4x4  max 2x1+x2+3x3+5x4  5 5x1+3x2+x3+2x4  20 4x1+2x2+3x3+x4 = 15 x10; x20; x3 0; x4 =  знак -3x1-4x2+5x3-4x4  min 2x1+x2-3x3+5x4-x5 = 5 5x1+3x2-x3+2x4+x6 = 20 4x1+2x2-3x3+x4 = 15 x1; x20; x30; x4 =  знак; x4 =x8-x7 -3x1-4x2+5x3-4x8+4x7 min 2x1+x2-3x3+5x8-5x7-x5 = 5 5x1+3x2-x3+2x8-2x7+x6 = 20 4x1+2x2-3x3+8 -x7 = 15 x1, x2, x3, x5, x6, x7, x8 0; x4=x8 -3x1-4x2+5x3-4x4+4x7 min 2x1+x2-3x3+5x4-5x7-x5 = 5 5x1+3x2-x3+2x4-2x7+x6 = 20 4x1+2x2-3x3+x4-x7 = 15 x1, x2, x3, x4, x5, x6, x70; x8 замінили на x4

11 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевикин, 2004 Симплекс-метод ЛП Симплекс-метод є ітеративною процедурою вирішення завдань ЛП, записаних у стандартній формі, система рівнянь в якій і за допомогою елементарних операцій над матрицями приведена до канонічного виду: x1 + a1, m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2, m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ...xm+am,m+1xm+1+...+amsxs+...+amnxn = bm. Змінні x1, x2,...,xm, що входять з одиничними коефіцієнтами тільки одне рівняння системи і з нульовими - до інших, називаються базисними. У канонічній системі кожному рівнянню відповідає одно одна базисна змінна. Інші n-m змінних (xm+1, ...,xn) називаються небазисними змінними. Для приведення системи до канонічного виду можна використовувати два типи елементарних операцій над рядками: Збільшення будь-якого рівняння системи на позитивне чи негативне число. Додаток до будь-якого рівняння іншого рівняння системи, помноженого на позитивне чи негативне число.

12 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевікін, 2004 Симплекс-метод ЛП Запис задачі у вигляді рівнянь x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2, m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ...xm+am,m+1xm+1+...+amsxs+...+amnxn = bm. тотожна запису у вигляді матриць 1 0 .. 0 a1,m+1 .. a1s .. a1n x1 b1 0 1 .. 0 a2,m+1 .. a2s .. a2n x2 = b2 . . .. . . .. . .. . .. .. 0 0 .. 1 am,m+1 .. ams .. amn xn bm

13 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевікін, 2004 Алгоритм симплекс-метода 1. Вибираємо початкове допустиме базисне рішення. Базовим рішенням називається рішення, отримане при нульових значеннях небазових змінних, тобто. xi=0, i=m+1,...,n. Базисне рішення називається допустимим базисним рішенням, якщо значення вхідних нього базисних змінних неотрицательны, тобто. xj = bj  0, j=1,2,...,m. У цьому випадку цільова функція набуде наступного вигляду: W=cbxb=c1b1+c2b2+...+cmbm. Заповнюємо початкову таблицю симплекс - методу:

14 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевікін, 2004 Алгоритм симплекс-метода 2. Обчислюємо вектор відносних оцінок c за допомогою правила скалярного твору сj = сj - cbSj, де сb - вектор оцінок базисних змінних; Sj - j-ий стовпець з коефіцієнтів aij в канонічній системі, що відповідає аналізованому базису. Доповнюємо початкову таблицю c – рядком.

15 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевікін, 2004 р. Алгоритм симплекс-метода 3. Якщо всі оцінки cj  0 (cj  0), i=1,...,n, то поточне допустиме рішення - максимальне (мінімальне ). Рішення знайдено. 4. Інакше в базис необхідно ввести небазисну змінну xr з найбільшим значенням cj замість однієї з базисних змінних (див. таблицю).

16 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевікін, 2004 Алгоритм симплекс-метода 5. За допомогою правила мінімального відношення min(bi/air) визначаємо змінну xp, що виводиться з базису. Якщо коефіцієнт air негативний, bi/air=. В результаті перетин стовпця, де знаходиться введена небазисна змінна xr, і рядки, де знаходиться базова змінна xp, що виводиться, визначить положення провідного елемента таблиці. 6. Застосовуємо елементарні перетворення для отримання нового допустимого базового рішення та нової таблиці. В результаті провідний елемент повинен дорівнювати 1 а інші елементи стовпця провідного елемента прийняти нульове значення. 7. Обчислюємо нові відносні оцінки з використанням правила скалярного перетворення та переходимо до кроку 4.

17 слайд

Опис слайду:
Теорія прийняття рішень ПетрГУ, А.П.Мощевикин, 2004 Приклад реш-я симплекс-методом Приклад - Оптимізація розміщення побічного виробництва лісництва 3. Цільова функція: 5000 x1 + 2500 x2  max, 4. Обмеження: . З використання землі, га: 4 x1 + 1,5 x2  24 4.2. По бюджету, руб.: 1200 х1 + 150 х2  6000 4.3. За трудовими ресурсами, год: 20 x1 + 20 x2  200 4.4. Зобов'язання за контрактом, прим.: x1  2 4.5. Обласні обмеження: x1  0, x2  0 Наведемо завдання до стандартної форми: 4 x1 + 1,5 x2 +x3= 24 1200 x1 + 150 x2 +x4= 6000 20 x1 + 20 x2 +x5= 200 x1 – x1 ... x6  0 Перші три рівняння мають відповідно за базовою змінною x3, x4, x5, однак у четвертому вона відсутня через те, що при змінній x6 стоїть негативний одиничний коефіцієнт. Для приведення системи до канонічного виду використовуємо метод штучних змінних. x1 – x6+x7= 2, запровадили штучну змінну x7.