Симплексен метод за решаване на задачи за линейно програмиране
Заглавие на работата: Симплексен метод за решаване на проблеми с линейно програмиране
Предметна област: Математика и смятане
Описание: Нека запишем системата от уравнения 5 във векторна форма: 6 където Aj B е вектор и елемент от матрица 1. По този начин нулевите стойности на променливите удовлетворяват 6. Векторите Ajj=n1nm могат да служат като основа в m-измерното пространство. Всеки небазисен вектор може да бъде разложен на базисни вектори. Нека разширим някакъв небазисен вектор Ak в базисни вектори: Умножете 8 по положителна константа и извадете 8 от 7. Произволна стойност може да бъде избрана толкова малка, че независимо от стойността, изразът в скоби винаги ще бъде по-голям от нула, тъй като 0.
Дата на добавяне: 2013-07-31
Размер на файла: 102.5 KB
Работата е изтеглена от: 7 души.
Симплексен метод за решаване на задачи от линейното програмиране.
Симплексният метод или методът на последователно подобряване на дизайна позволява известно основно решение да конструира друго основно решение, за което стойността на линейната формула R>gt; отколкото за оригинала. Записваме системата от уравнения 5 във векторна форма:
където Aj , B вектор
a - матричен елемент
1. Да предположим, че е известно някакво основно решение, в което m са променливи, различни от 0. . Така нулевите стойности на променливите удовлетворяват (6) Векторите А j ( j = n +1,…, n + m ) могат да служат като основа в m-мерното пространство. Всеки небазисен вектор може да бъде разложен на базисни вектори.
2. Нека разложим определен нет-базисен вектор A k по базисни вектори:
Умножете (8) по положителна константа и извадете (8) от (7)
- неговата произволна стойност може да бъде избрана толкова малка, че независимо от стойността, изразът в скоби винаги ще бъде по-голям от нула, тъй като >0 (по дефиниция) означаваме: За вектора A k : y k=. За =0 ще имаме първоначалното основно решение. За да получим друго основно решение, трябва да вземем >0. ако коефициентите на вектора A k са отрицателни, тогава е невъзможно да се получи ново основно решение. В този случай трябва да вземете друг небазисен вектор и да го разложите на базисни вектори. Ако неговите коефициенти също са по-малки от нула, тогава следващият небазисен вектор трябва да бъде разширен, докато получим разлагане, в което поне една променлива е положителна.
3. Нека не всички коефициенти на вектора A k са отрицателни, следователно, с непрекъснато нарастване, започвайки от 0, първата, която се превръща в 0, е тази променлива (), за n-то
Съотношението ще бъде минимално и това съотношение трябва да се приеме като:
4. Да предположим, че минималната стойност е получена, когато l =1, тоест за първата от поредицата от променливи: n +1,…. n + m , т.е. = следователно за дадена стойност (от (10)) ще бъде равно на 0 Други стойности ще бъдат 0 за всички j = n +2,…, n + m . y n =. Вместо първоначалното основно решение, получаваме ново решение:
Въз основа на новото основно решение, уравнение (9) ще бъде записано във формата Сравнявайки (11) с (7) стигаме до извода, че в първоначалния базис от вектори A j ( j = n +1. n + m ) . един от тях A n +1 се заменя с вектора A k и новото базисно решение удовлетворява уравнение (11) Все още обаче не е ясно как се променя стойността на критерия при преминаване към основното решение. Заместете в израза на критерия първоначалното основно решение, следователно За новото основно решение: нарастване
Ако >0 по време на прехода към ново основно решение, тогава този преход е целесъобразен. В резултат на това в основата се въвежда нет-базисен вектор и се формира нов базис, според който следващият не-базисен вектор може да бъде разширен и ако отново получим > 0, тогава изграждаме нов базис и го използвамеразширяване на следващия неосновен вектор и т.н. докато заместването на базисни вектори с небазисни вектори доведе до повишаване на критерия. От (12) следва, че >0 е винаги когато и следователно решението за преход към нова база може да бъде проверено преди определяне, с известни коефициенти на разширение на вектора A k .