Рефераты / Экономико-математическое моделирование /

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

Для вирішення задачі лінейного програмування, потрібно записати вихідну задачу в формі задачі лінейного програмування, а потім застосовувати симплекс-метод . Основною задачею лінійного програмування задача для якої: 1. потрібно визначити максимальне значення ф-ції 2. всі обмеження записані в вигляді рівностей 3. для всіх змінних виконується умова невідємності Якщо обмеження має вид нерівності зі знаком >=, то шляхом множення його на (-1) переходять до нерівності зі знаком <=. Від обмежень нерівностей необхідно перейти до обмежень рівностей. Такий перехід виконується шляхом введення в ліву частину кожної нерівності додаткових незалежних невідємних змінних. При цьому знак нерівності міняють на знак рівності. Вихідне завдання: F = 5х1 +6х2 max -10x1 - 6x2 -60 -4x1 + 9x2 36 4x1 - 2x2 8 x1,x20 x1,x2-цілі числа

Основна задача: F = 5х1 +6х2 max

10x1 + 6x2 + х3 =60 -4x1 + 9x2 +х4= 36 4x1 - 2x2 +х5 = 8

x1,x2,x3,x4,x5 0 x1,x2-цілі числа Кожній змінній в системі відповідає свій вектор стовпець. Вектор стовпець Ро складається із значень правих частин рівнянь і називається вектором вільних членів. Виходячи з основного завдання, складаєм симплекс-таблицю. № рядкаБазисСбР0Р1Р2Р3Р4Р51Р30601061002Р4036-490103Р5084-20014F0-5-6000Таблиця № 1 Вихідна симплекс-таблиця

Знаходження оптимального розвязку ЗЛП за допмогою с-м включає слідуючі етапи: 1. За вихідною с-т знаходять опорне рішення Кожній с-т відповідає своє опорне рішення. Воно може бути представлене у вигляди вектора Х Розмірніст вектора дорівнює кількості змінних в основній задачі. Кожній змінній в симплекс таблиці відповідає свій вектор. Змінній x1вектор Р1 і т.д. Вектор Р0 складений із вільних членів рівнянь. Кожний рядок симплекс-таблиці рівняння відповідно. Четвертий рядокрядок оцінок в ньому записують коефіцієнти при змінних в цільовій ф-ції з протилежним знаком і визначається розвязуємий стовпець, беруться модулі відємних чисел з цієї строки. В векторі Х кожній змінній відповідає певна компонента. Змінній х1 перша компонента змінній х2друга. Значення компонент визначають слідуючим чином, якщо вектор базисний, то компонента дорівнює значенню компоненти вектора стовпця Р0 з того рідка де в базисі стоїть 1. У вихідній таблиці вектори Р1, Р2 не базісні, тобто в Х перша и друга компоненти = 0 Х=(0;0;60;36;8) 2. Зясовують, мається хочаб одне відємне значення врядку оцінок ( рядок 4) Якщо нема то план оптимальний, якщо є треба переходити до новій с-т. Рядок оцінок має (-5) та (-6), отже данний опорний план не оптимальний. 3. Знаходять визначальний стовпець. Стовпець називають визначальним, якщо в рядку оцінок у нього найбільше за модулем значення. Маємо стовпець Р2 |-6|>|-5| 4. Знаходимо визначальний рядок. Визанчальним назівається такий рядок, який відповідає найменшому з відношень компонентів стовпця Ро до додатніх компонентів визначального стовпця. (Рядок оцінок до уваги не приймається) Min = ( 60/6; 36/9) = 4 рядок 2. 5. Будують наступну с-т . Для цього кожний елемент таблиці перераховуємо за формулою aij=aij- (аіk* аnj)/ank де k-номер розвязувального стовпця, а n- номер розвязувального рядка aijелемент строки- і, стовпця- j нової сиплекс таблиці aijелемент строки- і, стовпця-j попередньої симплекс-таблиці аіk-- елемент що знаходиться у визначальному стовпці попер. с-т. аnj-- елемент що знаходиться у визначальному рядку попер с-т. ank элемент що стоїть на перехресті визн рядка и строки у попер сим-т.

a10= 60 (36*6)/9 =
Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ