Постановка на задачата и начално попълване на таблицата
Трябва да се намери максимума на линейната целева функция
при зададени ограничения
Първо грябва да попълним симплекс – таблицата.
Нанасяме коефициентите пред неизвестните, така както при метода на Гаус за решаване на системи.
Разбира се, коефициентите на неучастващите неизвестни в дадено уравнение са нули.
( От мързеливи съображения индексите не са написани по-долу и не са по-малки, както се прави обикновено )
За разлика от метода на Гаус, свободните членове се нанасят отляво на матрицата.
Нанасяме неизвестните над съответните стълбове а над тях коефициентите им от целевата функция.
Базисно незвестно за определен ред се нарича такова неизвестно, което участва в него ( реда) с коефециент 1 и не участва в
останалите редове (коефициентите пред него са нули).
В неговия стълб трябва има една единица в съответния ред и нули на останалите редове.
В този пример, за i – тия ред базисната променлива е xj .
Базисните проминливи са нанасят отлаво на стълба "В" а отдясно на тях - коефициентите им от целевата функция Z.
Тези два нови стълба се означават съответно с Б и С.
Ето един пример:
За първия ред базисната променлива е x5.
Коефициента пред нея в целевата функция е -1.
За втория ред базисната променлива е x2.
Коефициента пред нея в целевата функция е 2.
За третия ред базисната променлива е x3.
Коефициента пред нея в целевата функция е 3.
В последния ред се изчисляват оценките D0 , D1 , D2 , . . ., Dn.
Оценката D0 се записва под стълба Б,
D1 под x1 , D2 под x2 и т.н.
Но как се изчисляват ?!
Произведение на два стълба с еднакъв брой елемента ще наричаме сумата от произведенията на съответните им елементи.
Стълбовете от таблицата ще означаваме с буквите над тях.
Тези изчисления се извършват на ум или на отделен лист.
Окончателно получаваме таблицата:
На тази таблица съответства един опорен план.
На базисните променливи от стълба Б съответстват стойностие от стълба В.
Останалите (не базисни ) промепливи са нули.
Опорния план е:
(0, 4, 3, 0, 1).
Стойността на целевата функция при този опорен план е 0 = 16.
Ако при търсене на максимум всички оценки 1, 2 , 3, . . . , n са по-големи или равни на нула полученият опорен план е оптимален и задачата е приключила.
Ако при търсене на максимум има отрицателени оценки, както е в случая, планът не е оптимален и трябва са се премине към друг, по-добър.
Как става това ни предстои да разберем.
Ето няколко примера за начално попълване на таблицата на симплекс-метода, определяне на базисните променливи и оценките.
Задача 1
Задача 2
Задача 3
Попълваме таблицата и със съжаление установяваме, че липсват базисни променливи,както за първото, така и за второто уравнение.
За да създадем такава за парвото уравнение го умножаваме с -1 и го прибавяме към второто.
Получаваме:
За да създадем такава и за второто уравнение го умножаваме по -2 и го прибавяме към първото.
Така, както при метода на Гаус.
Получаваме:
Сега вече имаме всичко, което ни трябва!
За съжаление, планът не е оптимален и трябва да се подобри.
Как става това ще научим след малко.
Подобряване на опорния план.
