• Загальний вигляд задачі лінійного програмування
  • Області допустимих рішень для двоїстих змінних


  • Дата конвертації04.07.2017
    Розмір36.63 Kb.
    Типреферат

    Скачати 36.63 Kb.

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

    3

    Державна освітня установа вищої

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

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

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

    реферат

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

    2008

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

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

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

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

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

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

    Загальний вигляд задачі лінійного програмування

    ,

    обмеження:

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

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

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

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

    змінні:

    Всі змінні повинні бути невід'ємними, тобто .

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

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

    .

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

    Чи підлягає максимізації або мінімізації.

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

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

    (1)

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

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

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

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

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

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

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

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

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

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

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

    Пряма задача.

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

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

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

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

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

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

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

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

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

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

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

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

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

    (1)

    (2)

    (3)

    (4)

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

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

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

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

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

    ПЧ

    1

    -

    -

    0

    0

    0

    0

    0

    1

    0

    0

    0

    0

    1

    0

    0

    0

    0

    1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Алгоритм отримання оптимального рішення:

    1. Перехід від нерівностей до рівності з урахуванням правил переходу - введення залишкових, надлишкових, штучних змінних і коефіцієнтів штрафу;

    2. Визначення числа базисних і небазисних змінних;

    3. Отримання - рядки для заповнення СТ (0. Для цього необхідно цільову функцію перетворити до вигляду; для чого з відповідних рівностей обмежень висловити штучні змінні і підставити в рядок і привести до раціонального виду;

    4. Заповнення СТ (0). Перенесення коефіцієнтів - рядки і рівності обмежень у відповідні рядки і стовпці симплекс-таблиці;

    5. Дослідження функції на умова оптимальності:

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

    визначення включається змінної з небазисних змінних;

    6. Визначення роздільної рядка за умовою допустимості:

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

    визначення исключаемой змінної з початкового базису;

    7. Визначення дозволяє елемента РЕ;

    8. Отримання B (0). Заміна в матриці початкового базису коефіцієнтів исключаемой змінної на коефіцієнти включається змінної; обчислення B (0) по відповідному правилу;

    9. Визначення елементів СТ (1) = В (0) СТ (0);

    10. Дослідження -строкі СТ (1) на умова оптимальності.

    Якщо умова не виконана, то обчислення тривають і необхідно повторити пункти 5-10.

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

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

    Двоїста задача.

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

    Двоїста задача має:

    m змінних, відповідних числу обмежень прямої задачі;

    n обмежень, відповідних числу змінних прямої задачі.

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

    Кожному обмеженню ПЗ відповідає змінна ДЗ;

    Кожноїзмінної ПЗ відповідає обмеження ДЗ;

    Коефіцієнти при у обмеженнях ПЗ стають коефіцієнтами лівої частини відповідного обмеження ДЗ;

    Коефіцієнти при у цільової функції ПЗ стають постійними правій частині обмеження ДЗ;

    Постійні обмежень ПЗ стають коефіцієнтами цільової функції ДЗ.

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

    Пряма задачаДвойственная завдання

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

    Області допустимих рішень для двоїстих змінних

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

    1. Розглянемо обмеження (2) прямої задачі:

    Область допустимих рішень ДП () визначається знаками обмежень (8) і (9) двоїстої задачі і знаком обмеження (2) прямої задачі. Для визначення ОДР знайдемо обмеження ДЗ, відповідні залишковим змінним ПЗ. Коефіцієнти цільової функції для залишкових змінних дорівнюють нулю (). Т. о., при вирішенні завдання максимізації обмеженням прямої задачі, які мають знак обмеження, відповідають невід'ємні двоїсті змінні:.

    2. Розглянемо обмеження (3) прямої задачі:

    .

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

    .

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

    3. Розглянемо обмеження (4) прямої задачі:

    В цільової функції надлишкові змінні мають коефіцієнти, рівні нулю (), а штучні змінні коефіцієнти, рівні величині штрафу зі своїм знаком, в результаті для завдання максимізації отримаємо:

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

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

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

    пряма задача

    двоїста задача

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

    обмеження

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

    обмеження

    змінні

    максимізація

    мінімізація

    =

    мінімізація

    максимізація

    =

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

    якщо змінна не обмежена в знаку, то;

    якщо то .

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

    Після приведення ДЗ до стандартного вигляду використовується симплекс - метод. Алгоритм отримання рішення той же, що і для прямої задачі.

    II. Практична частина

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

    Дана наступна задача лінійного програмування (ЗЛП).

    ,

    1.1. Всі обмеження завдання.

    1.2. Мінлива обмежена в знаку, тому. Змінна не обмежена в знаку, тому вводимо заміну, де.

    Область допустимих рішень буде обмежуватися I і IV квадрантом.

    1.3. Побудова обмежень і градієнта цільової функції:

    1.4. Область допустимих рішень - відрізок AB.

    1.5. Точка А - оптимальна. Координати т. А:

    ; ; .

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

    Пряма задача.

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

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

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

    ,

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

    ,

    2. Загальна кількість змінних визначимо за формулою: = 3 + 2 + 2 = 7, де - число штучних змінних. Число базисних змінних визначається числом обмежень, т. К., То система має три базисні змінні і небазисних змінні.

    3. Отримання - рядки для СТ (0). Наведемо цільову функцію до виду

    .

    Отримаємо з (2):, з (3):

    4. Формування симплекс - таблиці на першому кроці:

    початковий базис

    СТ (0) РС

    ПЧ

    1

    -1-4M

    3 + 3M

    -3M-3

    M

    0

    0

    0

    -12M

    0

    1

    2

    -2

    0

    1

    0

    0

    4

    0

    3

    -4

    4

    0

    0

    1

    0

    12

    0

    1

    1

    -1

    -1

    0

    0

    1

    0

    5. Визначення дозволяє стовпця.

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

    6. Визначення роздільної рядка: - виключається змінна.

    7. Дозволяє елемент РЕ = 1.

    8. Отримання матриці переходу

    , Де В (0) - матриця переходу

    9. Визначення елементів таблиці СТ (1) = В (0) СТ (0);

    10. Дослідження z-рядки СТ (1) на умова оптимальності:

    СТ (1)

    z

    ПЧ

    z

    1

    0

    4 + 7M

    -7M-4

    -3M-1

    0

    0

    1 + 4M

    -12M

    0

    0

    1

    -1

    1

    1

    0

    -1

    4

    0

    0

    -7

    7

    3

    0

    1

    -3

    12

    0

    1

    1

    -1

    -1

    0

    0

    1

    0

    СТ (2)

    z

    ПЧ

    z

    1

    0

    0

    0

    5/7

    0

    M + 4/7

    M-5/7

    48/7

    0

    0

    0

    0

    10/7

    1

    1/7

    -10/7

    40/7

    0

    0

    -1

    1

    3/7

    0

    1/7

    -3/7

    12/7

    0

    1

    0

    0

    -4/7

    0

    1/7

    4/7

    12/7

    СТ (2) - оптимальна, т. К. Коефіцієнти при НБП.

    ,,.

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

    Двоїста задача.

    Складемо двоїсту задачу за умовами прямої задачі і визначимо області допустимих рішень ДП:

    Пряма задачаДвойственная завдання

    (1)

    (2)

    Отже, отримано:,,.

    2. Наведемо запис двоїстої задачі до канонічної формі. На підставі отриманих ОДР двоїстих змінних введемо необхідні підстановки:.

    Для зручності рішення звернемо обмеження (1) і (2) в одне зі знаком рівності, а також введемо в обмеження і цільову функцію надлишкові, залишкові і штучні змінні.

    (3)

    (4)

    3. Вирішимо ДЗ симплекс методом:

    З (3): висловимо

    З (4) висловимо:

    СТ (0)

    W

    ПЧ

    W

    1

    -4-M

    7M-12

    12-7M

    0

    -M

    0

    0

    4M

    0

    1

    3

    -3

    -1

    -1

    1

    0

    1

    0

    -2

    4

    -4

    1

    0

    0

    1

    3

    СТ (1)

    W

    ПЧ

    W

    1

    -10 / 3M

    0

    0

    7 / 3M-4

    4 / 3M-4

    -7 / 3M + 4

    0

    5 / 3M + 4

    0

    1/3

    1

    -1

    -1/3

    -1/3

    1/3

    0

    1/3

    0

    -10/3

    0

    0

    7/3

    4/3

    -4/3

    1

    5/3

    СТ (2)

    W

    ПЧ

    W

    1

    -40/7

    0

    0

    0

    -12/7

    -7 / 3M + 4

    -M + 12/7

    48/7

    0

    -1/7

    1

    -1

    0

    -1/7

    1/3

    1/7

    4/7

    0

    -10/7

    0

    0

    1

    4/7

    -4/3

    -3/7

    5/7

    СТ (2) - оптимальна, т.к. коефіцієнти при

    ,,

    завдання:

    1. Вивчити методи розв'язання задачі лінійного програмування (графічний і симплекс-метод):

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

    - графічним методом;

    - симплекс методом для прямої задачі;

    - симплекс методом для двоїстої задачі.



    Головна сторінка


        Головна сторінка



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

    Скачати 36.63 Kb.