За линейно програмиране
Доза/ден според лимит 0 x 1 4 0 x 2 3 0 x 3 2 0 x 4 8 0 x 5 2 0 x 6 2 Според дневната потребност 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 Тук вземаме предвид, че не можем да консумираме отрицателен количество или твърде много храна и ние обобщихме хранителната стойност в тях. И накрая, цената на диетата може да бъде изразена чрез въведените променливи и дадени константи: 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 След това математическото описание на диетичния проблем е както следва: min 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 x 1 4 x 2 3 x 3 2 x 4 8 x 5 2 x 6 2 x 1, x 2, x 3, x 4, x 5, x 6 0 Обикновено под линейно програмиране разбираме следните проблеми:
Разбира се, променливите x 4, x 5, x 6 могат да приемат само неотрицателна стойност, в противен случай първоначалните неравенства няма да бъдат удовлетворени. Затова опитайте да увеличите x 1, така че стойността на променливите x 4, x 5, x 6 да остане неотрицателна; така че, разбира се, има ограничения за x 1; (1) x 1 5 2 (2) x 1 11 4 (3) x 1 8 3 Тъй като (1) дава най-силното ограничение, ново решение е: x 1 = 5/2, x 2 = 0, x 3 = 0, x 4 = 0, x 5 = 1, x 6 = 1/2, z = 25/2. От (1) получаваме x 1, изразено като: x 1 = 5 2 3 2 x 2 1 2 x 3 1 2 x 4 (1) Заместете това в (2) и (3): x 5 = 11 4 (5 2 3 2 x 2 1 2 x 3 1 2 x 4) x 2 2x 3 (2) x 6 = 8 3 (5 2 3 2 x 2 1 2 x 3 1 2 x 4) 4x 2 2x 3 (3) z = 5 (5 2 3 2 x 2 1 2 x 3 1 2 x 4) + 4x 2 + 3x 3 x 1 = 5 2 3 2 x 2 1 2 x 3 1 2 x 4 (1) x 5 = 1 + 5x 2 + 2x 4 (2) x 6 = 1 2 + 1 2 x 2 1 2 x 3 + 3 2 x 4 (3) z = 25 2 7 2 x 2 + 1 2 x 3 5 2 x 4 Извикайте променливите на вляво, x 1, x 5 и x 6, основа. Неосновните променливи вземат 0. Стойността на целевата функция е константата, показана тук, така че z = 25/2. Сега не би си струвало да увеличаваме x 2 и x 4, защото това би намалило целевата функция z. Избираме x 3 и виждаме колко дълго може да се увеличи. 6
Доказателство. Видно е от казаното дотук. Определение. Два речника са еквивалентни, ако всички (произволни реални) решения на системата от уравнения, които те описват, и съответните им целеви функции са еднакви. Предложение 2 Трансформацията на речник, използван в примера, води до речник, еквивалентен на предишния. Доказателство. Очевидно е, че приложените алгебрични манипулации (пренареждане на уравнение, умножаване с ненулево число или заместване на променливи) не променят решенията на системата от уравнения. Забележка: Съществува тясна връзка между възможните решения на стандартен LP проблем и неотрицателните решения на речниците, образувани от него, тъй като неотрицателният характер на изкуствените променливи означава изпълнение на неравенствата на оригиналния LP. Ако x 1. x n е възможно решение на LP, тогава x 1. x n се допълва от разликата между лявата и дясната страна като x n + 1. Със стойностите на променливите x n + m, речникът дава неотрицателно решение. И обратно, пропускането на изкуствени променливи от неотрицателно решение в речника дава възможно решение на оригиналния LP. 9
Лекция 2 В нашия пример видяхме, че симплекс алгоритъмът може да бъде разделен на следните основни етапи: 1. Инициализация (начална точка) 2. Итерация (приближение) 3. Прекратяване (завършване) Досега умишлено игнорирахме трудностите и разклоняването възможности на алгоритъма. Проблемът с инициализацията ще бъде обсъден в следващия клас, но въпросите за итерацията и прекратяването ще бъдат изяснени сега. 1. Инициализация max cjxja ij xjb (i = 1, 2. m) xj 0 (j = 1, 2. n) x n + i = bina ij xj (i = 1, 2. m) z = cjxj Ако всички bi 0, тогава (0, 0. 0) е възможно решение. В противен случай не можем да започнем итерацията. Така че, за да започнем нашия процес, ще ни трябва речник, който дефинира възможно решение. 2. Итерация z = z + c j x j, j N, където z е моментната стойност на целевата функция; N е набор от неосновни променливи, B е набор от базови променливи. 10
Да предположим, че текущата ситуация е следната: x 2 = 5 + 2x 3 x 4 3x 1 x 5 = 7 3x 4 4x 1 z = 5 + 3x 3 x 4 x 1 Препоръчително е да увеличите стойността на x 3, така че x 2 и x 5 не трябва да бъдат отрицателни. Нито едно от горните две уравнения обаче не дава ограничение (горна граница) на x 3, целевата функция на задачата може да приеме произволно голяма стойност. По време на процеса може да се случи следното: а) В речника всички коефициенти, принадлежащи към основната променлива, са 0, тоест няма ограничение. Тогава решението не е ограничено. б) Коефициентите на променливите на целевата функция не са положителни. Тогава сме в оптимум. в) Няколко променливи могат да влязат в основата едновременно; следователно трябва да изберем един от тях. г) Стойността на входните променливи не може да бъде увеличена и целевата функция не се увеличава. Тогава казваме, че е настъпила дегенерация. Определение. нула. Пример: Речникът е дегенериран, ако съдържа стойността на основна променлива xi x 4 = 1 2x 3 x 5 = 3 2x 1 + 4x 2 6x 3 x 6 = 2 + x 1 3x 2 4x 3 z = 2x 1 x 2 + 8x 3 променливата, напускаща основата, не е ясно дефинирана, тъй като и трите уравнения дават ограничение 1/2 за стойността на променливата x 3. Дегенерация 11