Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Представлення задач ЛП в матричній та векторній формі.
f(x)= c1x1 + c2x2 + …. + cnxn →extr (max/min) (1) a11x1 + a12x2 + a13x3 + ….. +a1nxn{ ≤ = ≥ }b1 a21x1 + a22x2 + a33x3 + …..+ a2nxn{ ≤ = ≥ }b2 ak1x1 + ak2x2 + ak3x3 + …….+ aknxn{ ≤ = ≥ }bk (2) am.1x1 + am.2x2 + am.3x3 + am.nxn { ≤ = ≥ } bm xi≥0 i= 1,m (3) Запишемо задачу ЛП в матричній формі: f(x)=(c,x) →max (4) при обмеженнях АХ=В (5) Х≥0 (6) де (,) – скалярний добуток А – матриця умов задачі В – вектор обмежень (вектор вільних членів задачі) Х – вектор невідомих змінних С – вектор цільової функції. Запишимо задачу ЛП в векторній формі: F(x)=(c,x) →max (7) x1P1 + x2P2 + x3P3 +…… + xnPn= P0 (8) X≥0 (9) P1= (a11,a21,а31…….am1), P2= (a12,a22,а32…….am2), ……….. Pn= (a1n,a2n,а3n…….anm), P0=(b1,b2, b3……. bm) – m-мерні вектор столбці. 2. Симплексний метод розв ’ язання задач ЛП. Теоретичні основи симплекс-метода. Симплекс метод полягає в послідовних переходах від одних опорних планів до інших так, щоб значення цільової функції зростало (якщо задача ЛП задається на пошук максимуму) або на зменшення цільової функції (якщо задача ЛП задається на пошук мінімуму). Оскільки число опорних планів задачі скінченне, то через скінченне число кроків отримаємо оптимальний опорний план (якщо він існує, або впевненість, що цільова функція на множені планів необмежена). Розглянемо два різновиди симплексного метода: · Симплекс – метод із стандартним базисом; · Симплекс метод із штучним базисом (М- метод). Симплекс – метод із стандартним базисом Для застосування цього методу розглянемо задачу ЛП у канонічному вигляді
Z=∑cixi →max за умов х1e1+ х2e2+ х3e3 + ….. + хmem + хm+1Pm+1 + ….. + хnPn=P0, де ei – одиничні вектори, Pk = (a1k, a2k,….. amk) (k=m+1,m+2,…. n), P0 = (b1, b2,… bm) Оскільки перші m векторів еi одиничними, то легко бачити, що виконується рівність b1e1+ b2e2+ b3e3 + ….. + bmem =P0. Тоді очевидним є початковий опорний план: X=(b1,b2,b3, ….. bm, 0….0), який перевіряємо на оптимальність. Для цього заповнюємо симплексну таблицю. Таблиця 1.
Усі рядки за винятком останнього рядка заповнюються за даними системи обмежень і цільової функції. Останній рядок обчислюється за формулою:
Δj=∑ciaij – cj, (j=1,2, …. n) і Δ0=∑cibi. Останній рядок називається індексним. Отриманий план перевіряють на оптимальність, зміст якої розкривається у наступних теоремах. Теорема 1. Якщо для деякого вектора Pj, який не входить у базис, виконується умова Δj<0, (j=1,2,3…..n) (для задачі на максимум) або Δj>0, (j=1,2,3…..n) (для задачі на мінімум), то можна отримати новий опорний план, для якого значення цільової функції f(x) буде більше (якщо f(x)→max),або менше (якщо f(x)→min) вихідного; при цьому можуть бути два випадки: а) якщо координати вектора Pj, який необхідно ввести у базис, недодатні, то задача ЛП не має розв’язку; б) якщо існує хоча б одна додатня координата вектора Pj, який необхідно ввести у базис, то можна отримати новий опорний план. Теорема 2. Якщо для всіх векторів Pj, виконується умова Δj≥0, (j=1,2,3…..n) (для задачі на максимум) або Δj≤0, (j=1,2,3…..n) (для задачі на мінімум), то опорний план Х*=((х1)*, (х2)*,......... (хn)*) є оптимальним. Якщо після побудови симплекс-таблиці виявилось, що виконуються умови Т.1 (пункт а)), або Т.2 розв’язання задачі припиняється. Якщо виконуються умови Т.1 (пункт б)), то потрібно перейти до нового оптимального опорного плану, побудувавши наступну симплексну таблицю. Для переходу до нового опорного плану треба один вектор вивести з базису і на його місце ввести новий вектор, який не належить базису. У базис вводять вектор, якому відповідає найбільша за абсолютною величиною від’ємна оцінка Δj. Нехай існує така оцінка в k- му стовпці, тобто max| Δj | = Δk. Δj≤0 Тоді вектор Рк вводимо у новий базис. Для знаходження вектора Рr, який необхідно вивести, обчислюють співвідношення Q= min(bi/aik) (i=1,2…..m), мінімальне значення якого досягається при i=r. Елемент ark називається розв’язувальним. Рядок Рr і стовпець Рк на перетині яких знаходиться розв ’ язувальний елемент ark, називають розв’язувальним. Для перерахунку елементів нової (наступної) симплекс – таблиці користуються методом Жордана – Гауса. Метод штучної бази. Застосовується у тих випадках, коли в вихідній задачі ЛП, яка записана у канонічному вигляді, в системі обмежень немає необхідної кількості одиничних ортогональних незалежних векторів Pj, тобто важко вказати початковий опорний план.
М-метод полягає у використанні правил симплекс – методу до так званої задачі ЛП. Вона отримується із початкової додованням до лівої частини системи рівнянь таких штучних одиничних векторів з відповідними невід’ємними штучними змінними, щоб знову отримати m одиничних ортогональних лінійно незалежних векторів. У цільовій функції задачі ЛП штучні змінні мають коефіцієнт - М (f(x)→max) або +М (f(x)→min), де під М ми розуміємо досить велике додатне число. При розв’язанні цієї задачі симплекс-методом оцінки Δj будуть залежити від М. Для порівняння оцінок, треба пам’ятати, що М – достатньо велике додатне число, тому із базису будуть виключатися у першу чергу штучні вектори. Якщо із базису всі штучні вектори вийшли, то ми отримали вихідну задачу. Якщо оптимальний розв’язок М – задачі містить штучні змінні або М – задача нерозв’язна, то початкова задача також нерозв’язна. Питання для самоконтролю. 1. В чому полягає симплекс-метод із стандартним базисом? 2. Коли використовують симплекс-метод зі штучним базисом? 3. Принципи заповнення симплекс-таблиці. 4. Що таке розв’язувальний елемент симплекс-таблиці? 5. Як перевірити опорний план на оптимальність? 6. Поясніть метод Жордана-Гауса. 7. Що таке штучні змінні?
Лекція 4
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-02-05; просмотров: 264; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.189.14.219 (0.009 с.) |