28480

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

Доклад

Математика и математический анализ

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

Украинкский

2013-08-20

27.15 KB

6 чел.

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

Існуючі методи розв'язування ЗЛП передбачають певні вимоги на систему основних обмежень, в силу чого розрізняють дві стандартні форми ЗЛП:

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

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

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

Отже, в якості базисних можна вибрати змінні х3, х4. Розв'яжемо систему рівнянь (12) відносно цих змінних методом . За умовою х3 > 0,  х4 > 0, тому праві частини рівнянь другої системи (13) невід'ємні:

Виключимо з цільової функції (11) змінні х3, х4, підставивши в (11) (13):

яка має II стандартну форму і рівносильна вихідній задачі (11)—(12). Відмітимо, що перевагою отриманої задачі є можливість знаходження її розв'язку графічним методом.


 

А также другие работы, которые могут Вас заинтересовать

10686. Наталка Полтавка - Котляревський Іван 15.15 KB
  Наталка Полтавка Котляревський Іван Українська опера на дві дії Дійові особи: Наталка українська дівчина. Горпина Терпилиха її мати. Петро коханий Наталки. Микола далекий родич Терпилихи. Тетерваковський возний жених Наталчин. Макогоненко сільський вибо
10687. Маруся - Квітка-Основяненко 16.75 KB
  Маруся Квітка-Основяненко Наум Дрот та його дружина були людьми богобоязними та праведними. В усьому вони дотримуються Божого і морального людського закону. За це Бог допомагає їм. За молитви й невпинну працю дає їм Бог донечку. Дитина теж росте слухняна покірна на ву
10688. Чорна рада - Пантелеймон Куліш - Хроніка 1663 року 20.2 KB
  Чорна рада Пантелеймон Куліш Хроніка 1663 року І Навесні двоє верхових наближалися до Києва Білгородським шляхом. Де їхали полковник Шрам із сином. Полковник був сином поволоцького попа вивчився на попа але потім пішов до козаків. Після поразки повстання полковник дес...
10689. Вовчок Марко - Максим Гримач 14.49 KB
  Вовчок Марко Максим Гримач Давно це було коли панували в Україні Польща і Московщина. Застави між державами хоч і стояли та не густо спритні люди часто перевозили Дніпром усякий крам не сплачуючи мита. Навпроти Черкас над Дніпром стояв хутір Максима Гримача. Чолові
10690. Кайдашева сімя - Нечуй-Левицький Іван 17.95 KB
  Кайдашева сімя НечуйЛевицький Іван І Село Семигори знаходиться недалеко коло Росі ховається воно в зелених садах навколо розстилаються левади. Хата Омелька Кайдаша притулилася біля однієї гори в старому садку. Старий Кайдаш сидить коло повітки та майструє одягнен...
10691. Хіба ревуть воли, як ясла повні? - Мирний Панас - Роман з народного життя 25.69 KB
  Хіба ревуть воли як ясла повні Мирний Панас Роман з народного життя ЧАСТИНА ПЕРША І Польова царівна Надворі вповні розвинулася весна вся природа буяє. В такий прекрасний весняний день дорогою від села Пісок до Ромодана йшов молодий чоловік. Він із задоволенням розг
10692. Мартин Боруля - Карпенко-Карий Іван 17.35 KB
  Мартин Боруля КарпенкоКарий Іван Мартин Боруля багатий шляхтич чиншовик той хто платить за оренду землі якомусь іншому власникові просить повіреного Трандалєва прочитати документ де вказано що Дворянскоє депутатскоє собраніє зачисляє його Борулю до дворянс
10693. Земля - Кобилянська Ольга 16.55 KB
  Земля Кобилянська Ольга Велике село Д. на Буковині. Горстка хаток притулилася до величного панського лісу. Інші розташувалися серед поля. Заможна селянка Докія занепокоєна долею своєї єдиної доньки Парасинки. Мати вже почуває себе вкрай погано батько ж страшний пият...
10694. Тіні забутих предків - Коцюбинський Михайло 15.78 KB
  Тіні забутих предків Коцюбинський Михайло Ще з народження Іван який був девятнадцятою дитиною в гуцульській сімї Палійчуків лякав матір та родичів неприродно розумним глибоким поглядом. Де викликало в людей містичні згадки про підкинутих нечистим дітей. Змалку п