Симплекс метод за решаване на оптимизационни задачи на линейното програмиране, BSEU на икономиката - блог

Симплекс метод - изчислителен процедура се основава на принципа на непрекъснатото подобряване извършване на прехода от една референтна точка (основен разтвор) към друга. Стойността на обективната функция се подобрява.

Референтният разтвор е един от възможните решения, които са във върховете на възможно региона. Проверка за оптимално върха на върховете, стигне до желания оптимум. Този принцип се основава на симплекс метода.

Симплекс - изпъкнал многоъгълник в п-тримерно пространство с N + 1 върхове, които не лежат в една hyperplane (hyperplane разделя пространството на две половината).

Например, линията разделя бюджетните ограничения на наличните и недостъпни ползи.

Доказано е, че ако съществува оптимално решение, че е задължително да се намери в краен брой повторения (стъпки), с изключение на "цикъл".

Симплекс алгоритъм се състои от няколко етапа.

Първи етап. Построен на оригиналния модел за оптимизация. Други условия на оригиналната матрица се превръща в намалена канонична форма, която наред с всички други канонични форми отличават с това, че:

а) дясната страна на условия (свободен отношение BI) са не-отрицателни стойности;

б) условията самите равенства;

в) включва матрица от условия пълна идентичност подматрица.

Ако свободните термини са отрицателни, тогава двете страни на неравенството се умножават по - 1, и неравенството се възстановява. За да се превърне неравенства в равенства се въвеждат допълнителни променливи, които обикновено представляват сумата на неизползвани ресурси. В това, те правят икономически смисъл.

И накрая, ако добавите допълнителни променливи, условия матрица не съдържа пълната идентичност подматрица, а след това влезе изкуствените променливи, които нямат икономически смисъл. Те се въвеждат само за да получите подматрица за самоличност и да започне процеса на решаване на проблема с помощта на симплекс метода.

Оптималното решение на всички изкуствени променливи (SP) трябва да е равна на нула. За тази изкуствени променливи са въведени в целевата функция на проблема с големи отрицателни коефициенти (-т) в решаване на проблема при макс и големи положителни коефициенти (М +), когато проблемът е решен в мин. В този случай, дори малка ненулева стойност променлива изкуствен ще намали драстично (увеличаване) стойността на обективната функция. Обикновено M 1000 пъти трябва да са по-големи от стойността на коефициентите на основните променливи.

Вторият етап. Построен първоначално симплекс таблицата и търсят някакъв първоначален основен разтвор. Редица променливи, които съставляват една единица под-матрица е взето, тъй като първоначалното основно решение. Стойностите на тези променливи са свободни да се членове. Всички други extrabasis променливи са равни на нула.

Третият етап. Проверка на основното решение за оптималност се извършва с помощта на специални коефициенти на обективни оценки на функцията. Ако всички изчислени коефициентите на обективната функция са отрицателни или нула, тогава съществуващата основен разтвор - оптимално. Ако поне един оценка на коефициента на целевата функция е по-голяма от нула, действащата основна решение не е оптимално и трябва да се подобри.

Четвъртият етап. Преходът към новия основен решение. Очевидно е, че в оптималния план следва да се прилага така, променлива, която увеличава целевата функция в най-голяма степен. В решаването на проблемите на печалбите на оптималния план въведени продукти, чието производство е най-печеливша. Това се определя от максималната положителна стойност на оценките на обективни коефициент функция.

маса Колона симплекс с този номер в даден повторение се нарича обща колона.

Освен това, ако най-малко един елемент от общата колона aij0 строго положителен, то търси обща линия (в противен случай задачата не е оптимално решение).

За да намерите общ ред всички свободни членове (ресурси) са разделени на съответните елементи с общо колона (скорост на ресурсите потребление на единица продукт). От тези резултати се избира най-малките. Съответния ред в това повторение се нарича цяло. Тя отговаря на ресурса, което ограничава производството на дадена итерация.

Елемент маса симплекс, разположен в пресечната точка на колона и ред цяло, наречен Обща елемент.

След това, всички елементи с обща линия (включително постоянен Терминът) са разделени в общ елемент. В резултат на тази операция, на общия елемент става равен на единица. Освен това е необходимо всички други елементи с обща колоната ще стане равно на нула, т.е. Обща колона трябва да бъде уникално. Всички линии (с изключение на общо) се трансформират, както следва. Получените елементи на нови линии се умножават по съответния елемент от основната колона и продуктът се изважда от елементите на стария линия.

Новите стойности на основните променливи, за да получат съответните клетки в колона от свободни условия.

Петият етап. Полученият основен разтвор се тества за оптималност (вж. Третата стъпка). Ако е оптимално, тогава изчисленията се прекратява. В противен случай, трябва да се намери нов разтвор на основа (стъпка четири), и така нататък. Г.

Пример за решаване на проблеми оптимизация на метода линейното програмиране симплекс

Да предположим, че ние трябва да се намери най-добрия план за производство на два вида продукти (x1 и x2).