ТЕМА: ЛИНЕЙНО ПРОГРАМИРАНЕ

ЗАДАЧА 2.А. Решаване на задача от линейно програмиране графичен метод

внимание!

Това е ПРОБНА ВЕРСИЯ на работа № 2073, цената на оригинала е 200 рубли. Проектиран в Програма на MicrosoftСлово.

Плащане. Контакти.

Вариант 7. Намерете максималната и минималната стойностлинейна функцияФ = 2x 1 - 2 x 2с ограничения: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1,2.

Решение:

Като условно заменим знаците за неравенство със знаци за равенство, получаваме система от уравнения x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Нека построим прави с помощта на тези уравнения, след което в съответствие със знаците на неравенствата избираме полуравнините и получаваме тяхната обща част - областта на допустимите решения на ODR - четириъгълника MNPQ.

Минимална стойност на функцията

ции - в точка М(2; 2)

Ф min = 2·2 - 2·2 = 0.

Максималната стойност се достига в точка N (10; 0),

Ф max = 2·10 - 2·0 = 20.

Вариант 8. Намерете максималната и минималната стойност

линейна функция Ф = x 1 + x 2

с ограничения: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1,2.

Решение:

Като условно заменим знаците за неравенство със знаци за равенство, получаваме система от уравнения x1 - 4 x2 = 4 ;

3 x1 - x2 = 0;

Нека построим прави с помощта на тези уравнения, след което в съответствие със знаците на неравенствата избираме полуравнините и получаваме тяхната обща част - областта на допустимите решения на ODR - неограничения многоъгълник MNPQ.

Минимална стойност на функцията

ции – на директен НП, например

в точка P(4; 0)

Ф min = 4 + 0 = 4.

ODR не е ограничен отгоре, следователно Ф max = + ∞.

Вариант 10. Намерете максималната и минималната стойност

линейна функция Ф = 2 x 1 - 3 x 2

с ограничения: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1,2.

Като условно заменим знаците за неравенство със знаци за равенство, получаваме система от уравнения

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Нека да построим прави с помощта на тези уравнения, след което в съответствие със знаците на неравенствата да изберем полуравнините и да получим тяхната обща част - областта на допустимите решения на ODR - многоъгълника MNPQRS.

Да построим вектора Г(2; -3) и да прекараме началото на координатите линия на ниво- прав.

Преместваме линията на нивото в посока, стойността на Ф се увеличава. В точка S(7; 0) целевата функция достига максимум Ф max =2·7–3·0= = 14. Преместваме линията на нивото в посока, стойността на Ф намалява. Минималната стойност на функцията е в точка N(0; 5)

Ф min = 2·0 – 3·5 = –15.

ЗАДАЧА 2.Б. Решаване на задача от линейно програмиране

аналитичен симплекс метод

Вариант 7. Минимизиране на целевата функция Ф = x 1 - x 2 + x 3 + x 4 + x 5 - x 6

с ограничения: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 – 4 x 3 + 2 x 6 = 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Решение:

Брой неизвестни n=6, брой уравнения m=3. Следователно r = n-m = 3 неизвестни могат да се приемат за свободни. Нека изберем x 1, x 3 и x 6.

Изразяваме основните променливи x 2 , x 4 и x 5 по отношение на свободните и свеждаме системата до единица

x 2 = 2 – 3 x 1 + 4 x 3 – 2 x 6

x 4 = 9 – x 1 – 6 x 6 (*)

x 5 = 6 – x 1 – 2 x 3 – 2 x 6

Целевата функция ще изглежда така:

Ф = x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 – x 1 – 6 x 6 +6 – x 1 – 2 x 3 – 2 x 6 – x 6 =

13 + 2 x 1 – 5 x 3 – 7 x 6

Нека поставим x 1 = x 3 = x 6 = 0, а основните променливи ще приемат стойностите x 2 = 2; х 4 = 9; x 5 = 6, т.е. първото допустимо решение (0; 2; 0; 9; 6; 0), целева функция Ф 1 = 13.

Променливите x 3 и x 6 са включени в целевата функция с отрицателни коефициенти, следователно, когато техните стойности се увеличават, стойността на Ф ще намалява. Да вземем х 6 например. От първото уравнение на системата (*) става ясно, че е възможно увеличение на стойността на x 6 до x 6 = 1 (докато x 2 ³ 0). В този случай x 1 и x 3 остават равни на нула. Сега вземаме x 4, x 5, x 6 като основни променливи и x 1, x 2, x 3 като свободни променливи. Нека изразим новите основни променливи чрез новите свободни. Получаваме

x 6 = 1 – 3/2 x 1 – 1/2 x 2 + 2 x 3

x 4 = 3 + 8 x 1 + 3 x 2 – 12 x 3

x 5 = 4 + 2 x 1 + x 2 – 6 x 3

Ф = 6 + 25/2 x 1 + 7/2 x 2 – 19 x 3

Нека присвоим нулеви стойности на свободните променливи, тоест x 1 = x 2 = x 3 = 0, докато x 6 = 1, x 4 = 3, x 5 = 4, тоест третото възможно решение (0 0; 4; В този случай Ф 3 = 6.

Променливата x 3 е включена в целевата функция с отрицателен коефициент, следователно увеличението на x 3 спрямо нулевата стойност ще доведе до намаляване на F. От второто уравнение е ясно, че x 3 може да се увеличи до 1/4 , от 3-то уравнение - на 2/3 . Второто уравнение е по-критично. Нека преобразуваме променливата x 3 в броя на основните, а x 4 в броя на свободните.

Сега вземаме x 1, x 2 и x 4 като нови свободни променливи. Нека изразим чрез тях новите базисни променливи x 3, x 5, x 6. Да вземем системата

x 3 = 1/4 + 2/3 x 1 + 1/4 x 2 – 1/12 x 4

x 5 = 5/2 – 2 x 1 – 1/2 x 2 + 1/2 x 4

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Целевата функция ще приеме формата

Ф = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Променливите x 1 и x 2 са включени в целевата функция с отрицателни коефициенти, следователно, когато техните стойности се увеличават, стойността на Ф ще намалява. Да вземем х 2 например. От второто уравнение на системата става ясно, че е възможно увеличение на стойността на x 2 до x 2 = 5 (докато x 5 ³ 0). В този случай x 1 и x 4 остават нула, стойностите на другите променливи са равни на x 3 = 3/2; x 5 = 0, x 6 = 3/2, т.е. четвъртото възможно решение (0; 5; 3/2; 0; 0; 3/2). В този случай Ф 4 = 5/4.

Сега вземаме x 1, x 4 и x 5 като нови свободни променливи. Нека изразим чрез тях новите базисни променливи x 2, x 3, x 6. Да вземем системата

x 2 = 5 – 4 x 1 + x 4 – 2 x 5

x 3 = 3/2 – 1/3 x 1 + 1/6 x 4 – 1/2 x 5

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Целевата функция ще приеме формата

Ф = - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Коефициентите и за двете променливи в израза за Ф са положителни, следователно по-нататъшно намаляване на стойността на Ф е невъзможно.

Тоест минималната стойност на Ф min = - 5, последното възможно решение (0; 5; 3/2; 0; 0; 3/2) е оптимално.

Вариант 8. Максимизиране на целевата функция Ф = 4 x 5 + 2 x 6

с ограничения: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 = 30;

x 3 + x 5 - 2 x 6 = 6;

2 x 4 + 3 x 5 - 2 x 6 = 18;

Решение:

Броят на уравненията е 4, броят на неизвестните е 6. Следователно r = n – m = 6 – 4 = 2 променливи могат да бъдат избрани като свободни променливи, 4 променливи като основни. Избираме x 5 и x 6 като свободни, а x 1 , x 2 , x 3 , x 4 като основни. Нека изразим основните променливи чрез свободни и редуцираме системата от уравнения до единица

x 1 = 12 - x 5 - x 6;

x 2 = 30 - 5 x 5 + x 6;

x 3 = 6 - x 5 + 2 x 6;

x 4 = 9 - 3/2 x 5 + x 6;

Записваме целевата функция във формата Ф = 4 x 5 + 2 x 6. Нека присвоим нулеви стойности на свободните променливи x 5 = x 6 = 0. В този случай основните променливи ще приемат стойностите x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , тоест получаваме първото допустимо решение (12, 30 , 6, 9, 0,) и Ф 1 = 0.

И двете свободни променливи влизат в целевата функция с положителни коефициенти, т.е. възможно е по-нататъшно увеличение на F, да преобразуваме например x 6 в броя на основните. От уравнение (1) става ясно, че x 1 = 0 при x 5 = 12, в (2) ÷ (4) x 6 е включено с положителни коефициенти. Нека преминем към нова основа: основни променливи - x 6, x 2, x 3, x 4, свободни - x 1, x 5. Нека изразим новите основни променливи чрез нови свободни

x 6 = 12 - x 1 - x 5;

x 2 = 42 - x 1 - 6 x 5;

x 3 = 30 - 2 x 1 - 3 x 5;

x 4 = 21 - x 1 - 5/2 x 5;

Целевата функция ще приеме формата Ф = 24 - 2 x 1 + 2 x 5 ;

Нека присвоим нулеви стойности на свободните променливи x 1 = x 5 = 0. В този случай основните променливи ще приемат стойностите x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , тоест получаваме второто допустимо решение (0, 42 , 30, 21, 0, 12) и Ф 2 = 24.

Целевата функция x 5 е включена с положителен коефициент, т.е. възможно е по-нататъшно увеличение на F, да преминем към нова основа: основни променливи - x 6, x 5, x 3, x 4, свободни - x 1. , x 2. Нека изразим новите основни променливи чрез new free

x 6 = 5 - 5/6 x 1 + 1/6 x 2;

x 5 = 7 - 1/6 x 1 - 1/6 x 2;

x 3 = 9 - 3/2 x 1 + 1/2 x 2;

x 4 = 7/2 - 7/12 x 1 + 5/12 x 5;

Целевата функция ще приеме формата Ф = 38 – 7/2 x 1 – 1/3 x 2 ;

Нека присвоим нулеви стойности на свободните променливи x 1 = x 2 = 0. В този случай основните променливи ще приемат стойностите x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7 /2, тоест получаваме третото допустимо решение X 3 = (0, 0, 9, 7/2, 7, 5) и Ф 3 = 38.

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

Следователно последното възможно решение е оптимално, т.е. X opt = (0, 0, 9, 7/2, 7, 5) и Ф max = 38.

Вариант 10. Максимизиране на целевата функция Ф = x 2 + x 3

с ограничения: x 1 - x 2 + x 3 = 1,

x 2 - 2 x 3 + x 4 = 2.

Решение:

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

Нека вземем x 2 и x 3 като свободни променливи. Тогава основните променливи ще бъдат x 1 и x 2, които ще изразим чрез свободни

x 1 = 1 + x 2 - x 3; (*)

x 4 = 2 - x 2 + 2 x 3;

Целевата функция вече е изразена чрез x 2 и x 3, т.е. Ф = x 2 + x 3.

За x 2 =0 и x 3 =0 основните променливи ще бъдат равни на x 1 = 1, x 4 = 2.

Имаме първото възможно решение X 1 = (1, 0, 0, 2), с Ф 1 = 0.

Увеличаването на Ф е възможно чрез увеличаване например на стойността на x 3, която се включва в израза за Ф с положителен коефициент (x 2 остава равен на нула). Първото уравнение на системата (*) показва, че x 3 може да се увеличи до 1 (от условието x 1 ³0), тоест това уравнение налага ограничение върху увеличаването на стойността на x 3. Първото уравнение на системата (*) е разрешаващо. Въз основа на това уравнение преминаваме към нова основа, разменяйки x 1 и x 3. Сега основните променливи ще бъдат x 3 и x 4, а свободните променливи ще бъдат x 1 и x 2. Нека сега изразим x 3 и x 4 чрез x 1 и x 2.

Получаваме: x 3 = 1 - x 1 + x 2 ; (**)

x 4 = 4 - 2 x 1 + x 2 ;

Ф = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2

Приравнявайки свободните променливи на нула, получаваме второто допустимо базисно решение X 2 = (0; 0; 1; 4), за което Ф 2 = 1.

Увеличаване на Ф е възможно с увеличение на х2. Увеличението на x 2, съдейки по последната система от уравнения (**), не е ограничено. Следователно Ф ще приема все по-големи положителни стойности, т.е. Ф max = + ¥.

Така че целевата функция Ф не е ограничена отгоре, следователно няма оптимално решение.

ЗАДАЧА 2.Г. Съставете задача, двойна на дадената

оригиналната задача.

Вариант 7. Максимизиране на целевата функция Ф = 2× x 1 - x 4

с ограничения: x 1 + x 2 = 20,

х 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Решение:

Нека приведем системата от ограничения в единична, например канонична форма, като въведем допълнителни променливи във 2-ро и 3-то уравнения

x 1 + x 2 = 20,

х 2 + 2 × x 4 – x 5 = 5,

- x 1 + x 2 + x 3 + x 6 = 8.

Получихме асиметрична задача от тип 2. Двойният проблем ще изглежда така:

Минимизирайте целевата функция F = 20 × y 1 + 5 × у2+8 × y 3

на y 1 - y 3 ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

y 3 ≥ 0,

2× y 2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Вариант 8. Максимизиране на целевата функция Ф = x 2 - x 4 - 3× х 5

с ограничения: x 1 + 2× x 2 - x 4 + x 5 = 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (аз = 1, 6)

Решение:

Имаме начален проблем за максимизиране със система от ограничения под формата на уравнения, тоест двойка двойни проблеми има асиметричен тип 2, чийто математически модел в матрична форма има формата:

Първоначален проблем: Двоен проблем:

F = C × X max F = B T × Имин

при А × X = B при A T × Y ≥ C T

В оригиналната задача матрицата-ред от коефициенти за променливи в целевата функция има формата C = (0; 1; 0; -1; -3; 0),

матрицата-колона от свободни членове и матрицата от коефициенти за променливи в системата от ограничения имат формата

B = 2, A = 0 - 4 1 2 -1 0

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

0 1 0 0 V T = (1; 2; 5)

A T = -1 2 0 C T = -1

Двойният проблем ще бъде написан в следната форма:

намерете минималната стойност на целевата функция F = y 1 + 2 × у2+5 × y 3

при ограничения y 1 ≥ 0,

2× y 1 - 4 × у2+3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Вариант 10. Минимизирайте функцията Ф = x 1 + x 2 + x 3

с ограничения: 3× х 1 + 9× х 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Решение:

Имаме начален проблем за минимизиране със система от ограничения под формата на неравенства, тоест двойка двойни проблеми има симетрична форма от 3-ти тип, чийто математически модел в матрична форма има формата:

Първоначален проблем Двойна задача

F = C × X min F = B T × Ymax

при А × х ≥ B в A T × Y ≤ С Т

X ≥ 0 Y ≥ 0

В оригиналната задача матрицата-ред от коефициенти за променливи в целевата функция, матрицата-колона от свободни членове и матрицата от коефициенти за променливи в системата от ограничения имат формата

C = (1; 1; 1), B = 3, A = 6 4 5

Нека намерим матриците на двойствената задача

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Двойният проблем се формулира така:

Максимизирайте целевата функция F = 2y 1 + 3y 2 + 4y 3

под ограничения 3 × y 1 + 6 × у2+8 × y 3 ≤ 1,

9× y 1 + 4 × у2+2 × y 3 ≤ 1,

7× y 1 + 5 × у2+4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

ЗАДАЧА 2.В. Решаване на задача за линейно програмиране с помощта на симплексни таблици.

Вариант 7. Максимизиране на целевата функция Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

с ограничения: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Решение:

Нека доведем системата от ограничения до каноничната форма

2 x 1 + 3 x 2 – x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Имаме система от 3 уравнения със 7 неизвестни. Нека да изберем 3 променливи x 1 , z 1 , z 3 като основни, x 2 , x 3 , x 4 , z 2 като свободни и да изразим основните променливи чрез тях.

От (2) имаме x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Заместваме в (1) и (3), получаваме

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 = 2.

Нека създадем симплексна таблица

I итерация Таблица 1

Основен AC	Свободата. AC
х 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z 1	2	0	7	-11		1	2	0	1/ 4	1/8
z 3	4	0	18	-17	13	0	4	1	4/13	13/8
Е	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1; 0; 0; 0; 2; 0; 4) Ф 1 = 2.

II итерация Таблица 2

х 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
х 4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
Е	4	0	4	— 4	0	1	0	0		32/7

X 2 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 = 4.

III итерация Таблица 3

х 1	1	1	— 6	0	0		-1	— 1		1/2
х 4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
х 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
Е	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 = (1; 0; 6/7; 10/7; 0; 0; 0) F 3 = 52/7.

IV итерация Таблица 4

z 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
х 4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
х 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
Е	149/14	45/14	15	0	0	0	3/14	19/14

X 4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 = 149/14.

Няма последна таблица в индексния ред отрицателни числа, тоест в израза за целевата функция всички Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Отговор: Ф m ax = 149/14,

оптимално решение (0; 0; 25/14; 37/14; 1/2; 0; 0)

Вариант 8. Минимизиране на целевата функция Ф = 5 x 1 - x 3

при ограничения: x 1 + x 2 + 2 x 3 - x 4 = 3,

x 2 + 2 x 4 =1,

Решение:

Броят на променливите е 4, рангът на матрицата е 2, следователно броят на свободните променливи е r = 4 - 2 = 2, броят на основните променливи също е 2. Нека вземем x 3, x 4 като свободни променливи, изразете основните променливи x 1, x 2 по отношение на свободните и Нека редуцираме системата до единица:

x 2 = 1 - 2 x 4,

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

Ф = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Нека напишем системата от уравнения и целевата функция във форма, удобна за симплексната таблица, т.е. x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

F + 11 x 3 - 15 x 4 = 10

Да направим маса

I итерация Таблица 1

Основен AC	Свободата. AC
X 1	2	1	0		— 3		1/2
X 2	1	0	1	0	2
Е	10	0	0	11	— 15		— 11/2

X 1 = (2; 1; 0; 0) Ф 1 = 10.

II итерация Таблица 2

X 3	1	1/2	0	1	-3/2		3/4
X 2	1	0	1	0			1/2
Е	— 1	— 11/2	0	0	3/2		— 3/4

X 2 = (0; 1; 1; 0) Ф 2 = -1.

III итерация Таблица 3

X 3	7/4	1/2	3/4	1	0
X 4	1/2	0	1/2	0	1
Е	— 7/4	— 11/2	— 3/4	0	0

X 3 = (0; 0; 7/4; 1/2) F 3 = -7/4.

В индексния ред на последната таблица няма положителни числа, т.е. в израза за целевата функция всички Г i > 0. Имаме случай I, следователно последното основно решение е оптимално.

Отговор: Ф min = -7/4, оптимално решение (0; 0; 7/4; 1/2)

********************

Вариант 10. Минимизиране на целевата функция Ф = x 1 + x 2,

при ограничения: x 1 –2 x 3 + x 4 = 2,

x 2 – x 3 + 2 x 4 = 1,

Решение:

Броят на променливите е 5, рангът на матрицата е 3, следователно броят на свободните променливи е r = 6-3 = 2. Нека вземем x 3 и x 4 като свободни променливи и x 1 , x 2 , х 5 като основни. Всички уравнения на системата вече са сведени до единица (основните променливи са изразени чрез свободни), но са написани във форма, която не е удобна за използване на симплексни таблици. Нека запишем системата от уравнения във формата

x 1 - 2 x 3 + x 4 = 2

x 2 - x 3 +2 x 4 = 1

x 5 + x 3 – x 4 . = 5

Изразяваме целевата функция чрез свободни променливи и я записваме във формата Ф - 3 x 3 +3 x 4 = 3

Да направим маса

I итерация Таблица 1

Основен AC	Свободата. AC
х 1	2	1	0	-2	1	0	2	-1/2
х 2	1	0	1	-1		0	1/2	1/2
х 5	5	0	0	1	-1	1		1/2
Е	3	0	0	-3	3	0		-3/2

X 1 = (2; 3; 0; 0; 5) F 1 = 3.

таблица 2

х 1	3/2	1	-1/2	-3/2	0	0
х 4	1/2	0	1/2	-1/2	1	0
х 5	11/2	0	1/2	1/2	0	1
Е	3/2	0	-3/2	-3/2	0	0

X 2 = (3/2; 0; 0; 1/2; 11/2) F 2 = 3/2.

В индексния ред на последната таблица няма положителни числа, тоест в израза за целевата функция всички Gi > 0. Имаме случай 1, следователно последното основно решение е оптимално.

Отговор: Ф min = 3/2, оптимално решение (3/2; 0; 0; 1/2; 11/2).

Федерална агенция за образование

Държавен бюджет образователна институция

по-висок професионално образование

"Омски държавен технически университет"

ИЗЧИСЛИТЕЛНО-ГРАФИЧНА РАБОТА

по дисциплина"ТЕОРИЯ ЗА ОПТИМАЛНО УПРАВЛЕНИЕ »

по темата "МЕТОДИ ЗА ОПТИМИЗАЦИЯ И ИЗСЛЕДВАНЕ НА ОПЕРАЦИИ »

вариант 7

Завършено:

задочно студент

4-та година група ZA-419

Пълно име: Кужелев С. А.

Проверено:

Девятерикова М. В.

Омск – 2012г
^

Задача 1. Графичен метод за решаване на задачи от линейно програмиране.

7) 7х 1 + 6х 2 → макс 20х 1 + 6х 2 ≤ 15 16х 1 − 2х 2 ≤ 18 8х 1 + 4х 2 ≤ 20 13х 1 + 3х 2 ≤ 4 х 1 , х 2 ≥ 0.

Стъпка 1: Конструиране на осъществимия регион

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

Първото ограничение на модела има формата . Заменяйки знака ≤ в него със знака =, получаваме уравнението . На фиг. 1.1 определя права линия (1), която разделя равнината на две полуравнини, в в такъв случайнад и под линията. Да се ​​избере кой удовлетворява неравенството , заменете в него координатите на всяка точка, която не лежи на дадена права (например началото х 1 = 0, х 2 = 0). Тъй като получаваме правилния израз (20 0 + 6 0 = 0 ≤15), тогава полуравнината, съдържаща началото на координатите (маркирана със стрелка), удовлетворява неравенството. Иначе друга полуравнина.

Продължаваме по подобен начин с останалите ограничения на проблема. Пресечната точка на всички построени полуравнини се образува с първия квадрант ABCD(виж фиг. 1). Това е възможната област на проблема.

Стъпка 2. Начертаване на линия на ниво Линия на ниво Целевата функция е набор от точки в равнината, в които целевата функция приема постоянна стойност. Такъв набор е даден от уравнението f ( х) = конст. Да сложим например конст = 0 и начертайте линия на нивото f ( х) = 0, т.е. в нашия случай права линия 7 х 1 + 6х 2 = 0.

Тази права минава през началото и е перпендикулярна на вектора. Този вектор е градиентът на целевата функция в точката (0,0). Градиентът на функция е вектор от стойности на частните производни на дадена функция във въпросната точка. В случая на задачата LP частните производни на целевата функция са равни на коефициентите ° Саз, й = 1 , ..., н.

Градиентът показва посоката на най-бързия растеж на функцията. Преместване на линията на ниво функция на целта f ( х) = конст. перпендикулярно на посоката на градиента, намираме последната точка, в която той се пресича с региона. В нашия случай това е точка D, която ще бъде максималната точка на целевата функция (виж Фиг. 2)

Той се намира в пресечната точка на линии (2) и (3) (виж фиг. 1) и определя оптималното решение.

^ Имайте предвид, че ако искате да намерите минималната стойност на целевата функция, линията на нивото се премества в посока, обратна на посоката на градиента.

^ Стъпка 3. Определяне на координатите на максималната (минималната) точка и оптималната стойност на целевата функция

За да се намерят координатите на точка C, е необходимо да се реши система, състояща се от уравнения, съответстващи на прави линии (в този случай уравнения 2 и 3):

16х 1 − 2х 2 ≤ 18

8х 1 + 4х 2 ≤ 20

Получаваме оптималното решение = 1,33.

^ Оптимална стойностцелева функция f * = f (Х*) = 7 * 0 + 6 * 1,33 = 7,8

КОНТРОЛНА РАБОТА ПО ДИСЦИПЛИНА:

„МЕТОДИ ЗА ОПТИМАЛНИ РЕШЕНИЯ“

Вариант No8

1. Решете графично задача от линейното програмиране. Намерете максимума и минимума на функцията с дадените ограничения:

,

.

Решение

Необходимо е да се намери минималната стойност на целевата функция и максималната, съгласно системата от ограничения:

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Нека изградим област от възможни решения, т.е. Нека да решим графично системата от неравенства. За да направим това, ние конструираме всяка права линия и дефинираме полуравнините, дефинирани от неравенствата (полуравнините са обозначени с просто).

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

Нека построим права линия, съответстваща на стойността на функцията F = 0: F = 2x 1 +3x 2 = 0. Градиентният вектор, съставен от коефициентите на целевата функция, показва посоката на минимизиране на F(X). Началото на вектора е точка (0; 0), краят е точка (2; 3). Ще преместим тази права линия успоредно. Тъй като се интересуваме от минималното решение, ние преместваме правата линия, докато тя първо докосне обозначената област. На графиката тази права линия е обозначена с пунктирана линия.

Направо
пресича областта в точка C. Тъй като точка C се получава в резултат на пресичането на линиите (4) и (1), нейните координати удовлетворяват уравненията на тези линии:
.

След като решихме системата от уравнения, получаваме: x 1 = 3.3333, x 2 = 0.

Как можем да намерим минималната стойност на целевата функция: .

Нека разгледаме целевата функция на проблема.

Нека построим права линия, съответстваща на стойността на функцията F = 0: F = 2x 1 +3x 2 = 0. Градиентният вектор, съставен от коефициентите на целевата функция, показва посоката на максимизиране на F(X). Началото на вектора е точка (0; 0), краят е точка (2; 3). Ще преместим тази права линия успоредно. Тъй като се интересуваме от максималното решение, ние преместваме правата линия до последното докосване на обозначената зона. На графиката тази права линия е обозначена с пунктирана линия.

Направо
пресича областта в точка B. Тъй като точка B се получава в резултат на пресичането на линиите (2) и (3), нейните координати удовлетворяват уравненията на тези линии:

.

Как можем да намерим максималната стойност на целевата функция: .

Отговор:
И
.

2 . Решете задача от линейното програмиране, като използвате симплексния метод:

.

Решение

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

Да определим минималната стойност на целевата функция
при следните условия-ограничения:
.

За да конструираме първия референтен план, редуцираме системата от неравенства до система от уравнения, като въвеждаме допълнителни променливи.

В първото смислово неравенство (≥) въвеждаме основната променлива х 3 със знак минус. Във второто смислово неравенство (≤) въвеждаме основната променлива х 4 . В 3-то смислово неравенство (≤) въвеждаме основната променлива x 5 .

Нека въведем изкуствени променливи : в първото равенство въвеждаме променлива х 6 ;

За да сведем проблема до минимум, записваме целевата функция, както следва: .

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

Получената основа се нарича изкуствена, а методът на решение се нарича метод на изкуствена основа.

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

От уравненията изразяваме изкуствени променливи: x 6 = 4-x 1 -x 2 +x 3, които заместваме в целевата функция: или.

Матрица на коефициента
тази система от уравнения има формата:
.

Нека решим системата от уравнения за основните променливи: х 6 , х 4 , х 5.

Ако приемем, че свободните променливи са равни на 0, получаваме първата референтен план:

X1 = (0,0,0,2,10,4)

Базисното решение се нарича допустимо, ако е неотрицателно.

		х 1	х 2	х 3	х 4	х 5	х 6
х 6
х 4
х 5

Текущият референтен план не е оптимален, тъй като има положителни коефициенти в линията на индекса. Като водеща колона ще изберем колоната, съответстваща на променливата x 2, тъй като това е най-големият коефициент. Нека изчислим стойностите д аз и от тях избираме най-малкото: min(4:1, 2:2, 10:2) = 1.

Следователно вторият ред е водещият.

Разрешаващият елемент е равен на (2) и се намира в пресечната точка на водещата колона и водещия ред.

		х 1	х 2	х 3	х 4	х 5	х 6
х 6
х 4
х 5

Формираме следващата част от симплексната таблица. Вместо променливата x 4, план 1 ще включва променливата x 2.

Редът, съответстващ на променливата x 2 в план 1, се получава чрез разделяне на всички елементи от реда x 4 от план 0 на разделящия елемент RE = 2. На мястото на разрешаващия елемент получаваме 1. В останалите клетки на колоната x 2 записваме нули.

Така в новия план 1 се попълват ред х 2 и колона х 2. Всички останали елементи на новия план 1, включително елементите на индексния ред, се определят от правилото на правоъгълника.

		х 1	х 2	х 3	х 4	х 5	х 6
х 6
х 2
х 5
		1 1/2 +1 1/2 M

Текущият референтен план не е оптимален, тъй като в индексния ред има положителни коефициенти. Като водеща колона ще изберем колоната, съответстваща на променливата x 1, тъй като това е най-големият коефициент. Нека изчислим стойностите д азпо ред като частно от деленето: и от тях избираме най-малкото: min (3: 1 1 / 2, -, 8: 2) = 2.

Следователно 1-вият ред е водещият.

Разрешаващият елемент е равен на (1 1/2) и се намира в пресечната точка на водещата колона и водещия ред.

		х 1	х 2	х 3	х 4	х 5	х 6
х 6		1 1 / 2
х 2
х 5
		-1 1 / 2 +1 1 / 2 М

Формираме следващата част от симплексната таблица. Вместо променливата x 6, план 2 ще включва променливата x 1.

Получаваме нова симплексна таблица:

		х 1	х 2	х 3	х 4	х 5	х 6
х 1
х 2
х 5

Няма положителни стойности сред стойностите на индексния низ. Следователно тази таблица определя оптималния план за проблема.

Крайната версия на симплексната таблица:

		х 1	х 2	х 3	х 4	х 5	х 6
х 1
х 2
х 5

Тъй като в оптималното решение няма изкуствени променливи (те са равни на нула), това решение е допустимо.

Оптималният план може да се запише по следния начин: x 1 = 2, x 2 = 2:.

Отговор:
,
.

3. Фирма "Тримата дебелани" доставя месни консерви от три склада, разположени в различни части на града, до три магазина. Запасите от налични консерви в складовете, както и обемите на поръчките в магазина и тарифите за доставка (в условни парични единици) са представени в транспортната таблица.

Намерете транспортен план, който осигурява най-ниските парични разходи (изпълнете първоначалния транспортен план, като използвате метода „северозападен ъгъл“).

Решение

Нека проверим необходимото и достатъчно условие за разрешимостта на задачата:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Условието за баланс е изпълнено. Задоволява равни нужди. Следователно моделът на транспортния проблем е затворен.

Нека въведем първоначалните данни в таблицата за разпределение.

потребности

Използвайки метода на северозападния ъгъл, ще изградим първия референтен план на транспортния проблем.

Планът започва да се попълва от горния ляв ъгъл.

Необходимият елемент е 4. За този елемент запасите са 300, изискванията са 250. Тъй като минимумът е 250, ние го изваждаме: .

			300 - 250 = 50
250 - 250 = 0

Необходимият елемент е равен на 2. За този елемент запасите са 50, изискванията са 400. Тъй като минимумът е 50, ние го изваждаме: .

			50 - 50 = 0
	400 - 50 = 350

Необходимият елемент е 5. За този елемент запасите са 300, изискванията са 350. Тъй като минимумът е 300, ние го изваждаме:

			300 - 300 = 0
	350 - 300 = 50

Необходимият елемент е 3. За този елемент запасите са 200, изискванията са 50. Тъй като минимумът е 50, ние го изваждаме:

			200 - 50 = 150
	50 - 50 = 0

Необходимият елемент е 6. За този елемент запасите са 150, изискванията са 150. Тъй като минимумът е 150, ние го изваждаме:

			150 - 150 = 0
		150 - 150 = 0

потребности

Въведение

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

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

1. Постановка на проблема

минимална целева функция

Решете задачата за намиране на минимума на целевата функция за системата от ограничения, зададена от многоъгълника на решение в съответствие с опция № 16 на задачата. Многоъгълникът на решението е показан на фигура 1:

Фигура 1 - Многоъгълник на решенията на проблема

Системата от ограничения и целевата функция на проблема са представени по-долу:

Необходимо е да се реши проблемът, като се използват следните методи:

Графичен метод за решаване на задачи на ЛП;

Алгебричен метод за решаване на задачи на ЛП;

Симплексен метод за решаване на задачи на ЛП;

Метод за намиране на допустимо решение на задачи на ЛП;

Решение на двойствената LP задача;

Метод на разклонения и граници за решаване на цели задачи на ЛП;

Метод на Gomori за решаване на задачи с целочислена LP;

Метод на Балаш за решаване на булеви LP задачи.

Сравнете резултатите от решението различни методинаправи подходящи изводи от работата.

2. Графично решение на задачата за линейно програмиране

Графичният метод за решаване на проблеми с линейно програмиране се използва в случаите, когато броят на неизвестните не надвишава три. Удобен за качествено изследване на свойствата на разтворите и се използва заедно с други методи (алгебрични, клонове и граници и др.). Идеята на метода се основава на графичното решение на система от линейни неравенства.

Ориз. 2 Графично решение на задачата LP

Минимална точка

Уравнение на права, минаваща през две точки A1 и A2:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

с ограничения:

Решаване на задача от линейно програмиране чрез алгебричен симплекс метод

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

Преобразувайте неравенствата така, че отляво да има променливи и свободни членове, а отдясно 0, т.е. да се лява странабеше по-голямо или равно на нула;

Въведете допълнителни променливи, чийто брой е равен на броя на неравенствата в системата от ограничения;

Чрез въвеждане на допълнителни ограничения върху неотрицателността на добавените променливи, заменете знаците за неравенство със строги знаци за равенство.

При решаване на задача на LP с помощта на алгебричния метод се добавя условие: целевата функция трябва да клони към минимум. Ако това състояниене е изпълнено, е необходимо целевата функция да се трансформира съответно (умножете по -1) и да се реши задачата за минимизиране. След като бъде намерено решението, заменете стойностите на променливите в оригиналната функция и изчислете нейната стойност.

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

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

Свободни променливи

св. платно - допълнителен комплект

Условията за неотрицателност са изпълнени, следователно е намерено оптималното решение.

3. Решаване на задача за линейно програмиране с помощта на симплексна таблица

Решение: Нека приведем проблема в стандартна форма за решение, използвайки симплексна таблица.

Нека сведем всички уравнения на системата до формата:

Изграждаме симплексна таблица:

В горния ъгъл на всяка клетка от таблицата въвеждаме коефициентите от системата уравнения;

Избираме максималния положителен елемент в ред F, с изключение на това, че това ще бъде общата колона;

За да намерим общия елемент, изграждаме връзка за всички положителни. 3/3; 9/1;- минимално съотношение в ред x3. Следователно – генералният низ и =3 – генералният елемент.

Намираме =1/=1/3. Вкарваме го в долния ъгъл на клетката, където се намира общият елемент;

Във всички празни долни ъгли на общата линия въвеждаме произведението на стойността в горния ъгъл на клетката с;

Изберете горните ъгли на общата линия;

Във всички долни ъгли на общата колона въвеждаме произведението на стойността в горния ъгъл по - и избираме получените стойности;

Останалите клетки от таблицата се попълват като произведение на съответните избрани елементи;

След това изграждаме нова таблица, в която се разменят обозначенията на клетките на елементите на общата колона и ред (x2 и x3);

Стойностите, които преди това са били в долния ъгъл, се записват в горния ъгъл на предишния общ ред и колона;

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

4. Решаване на задача от линейно програмиране чрез намиране на допустимо решение

Нека е дадена система от линейни алгебрични уравнения:

Можем да приемем, че всичко е така, в противен случай умножаваме съответното уравнение по -1.

Въвеждаме спомагателни променливи:

Въвеждаме и спомагателна функция

Ние ще минимизираме системата при ограничения (2) и условия.

ПРАВИЛО ЗА НАМИРАНЕ НА ДОПУСТИМО РЕШЕНИЕ: За да намерим допустимо решение на система (1), минимизираме формата (3) при ограничения (2), като xj приемаме за свободни неизвестни и вземаме xj за базисни.

При решаване на проблем чрез симплексния метод могат да възникнат два случая:

min f=0, тогава всички i трябва да са равни на нула. И получените стойности на xj ще представляват допустимо решение на система (1).

min f>0, т.е. оригиналната система няма осъществимо решение.

Изходна система:

Използва се условието на задачата от предната тема.

Нека въведем допълнителни променливи:

Намерено е допустимо решение на първоначалната задача: x1 = 3, x2 = 3, F = -12. Въз основа на полученото допустимо решение ще намерим оптималното решение на първоначалния проблем, използвайки симплексния метод. За да направим това, ще изградим нова симплексна таблица от таблицата, получена по-горе, като премахнем реда и реда с целевата функция на спомагателния проблем:

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

6. Проблем с двойно линейно програмиране

Оригиналната система от ограничения и целевата функция на проблема са показани на фигурата по-долу.

с ограничения:

Решение: Нека приведем системата от ограничения в стандартна форма:

Проблемът, двоен на този, ще има формата:

Решението на двойния проблем ще бъде извършено с помощта на прост симплексен метод.

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

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

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

Втора стъпка на симплексния метод

И така, на третата стъпка на симплексния метод беше намерено оптимално решение на задачата за минимизиране със следните резултати: y2 = -7 /8, y1 = -11/8, Ф = 12. За да се намери стойността на целевата функция на двойния проблем, ние заместваме намерените стойности на основните и свободните променливи във функцията за максимизиране:

Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Тъй като стойността на целевата функция на пряката и двойната задачи съвпада, решението на пряката задача е намерено и е равно на 12.

Fmin = Фmax = -12

7. Решаване на целочислена задача за линейно програмиране с помощта на метода разклоняване и обвързване

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

Начален многоъгълник от решения на целочислена програмна задача.

За трансформирания многоъгълник от решения, които конструираме нова системаограничения.

Нека запишем системата от ограничения под формата на равенства, които трябва да се решат с помощта на алгебричния метод.

В резултат на решението беше намерен оптималният план за задачата: x1 = 9/4, x2 = 5/2, F = -41/4. Това решение не отговаря на условието за цяло число, зададено в проблема. Нека разделим полигона на първоначалното решение на две области, като изключим област 3 от него

Модифициран полигон за решение на задача

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

Ограничителна система за лявата зона

Дясната област представлява точка С.

Системата от ограничения за района на правилното решение е представена по-долу.

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

В резултат на решението беше намерен оптималният план за задачата: x1 = 3, x2 = 3, F = -12. Този план отговаря на условието, че променливите в проблема са цели числа и може да се приеме като оптимален референтен план за първоначалния проблем с целочислено линейно програмиране. Няма смисъл да търсите правилния регион на решение. Фигурата по-долу показва напредъка на решаването на задача за целочислено линейно програмиране под формата на дърво.

Напредък на решаването на задача с целочислено линейно програмиране с помощта на метода Gomori.

В много практически приложения проблем с целочислено програмиране, в който е дадена система от линейни неравенства и линейна форма, представлява голям интерес

Необходимо е да се намери целочислено решение на система (1), което минимизира целевата функция F, като всички коефициенти са цели числа.

Един от методите за решаване на проблема с целочисленото програмиране е предложен от Гомори. Идеята на метода е да се използват непрекъснати методи за линейно програмиране, по-специално симплексния метод.

1) Чрез симплексния метод се определя решението на задача (1), (2), за което отпада изискването за целочислено решение; ако решението се окаже цяло число, тогава ще бъде намерено и желаното решение на целочислената задача;

2) В противен случай, ако дадена координата не е цяло число, полученото решение на задачата се проверява за възможността за съществуване на цяло число (наличие на цели точки в допустим полиедър):

ако в който и да е ред с дробен свободен член всички други коефициенти се окажат цели числа, тогава в допустимия многостен няма цели числа или точки и задачата за целочислено програмиране няма решение;

В противен случай се въвежда допълнително линейно ограничение, което отрязва част от допустимия полиедър, неперспективна за намиране на решение на задачата за целочислено програмиране;

3) За да конструирате допълнително линейно ограничение, изберете l-тия ред с дробен свободен член и напишете допълнителното ограничение

където и са съответно дробни части от коефициентите и свободни

член. Нека въведем спомагателна променлива в ограничението (3):

Нека определим коефициентите и включени в ограничението (4):

където и са най-близките цели числа отдолу за и съответно.

Гомори доказа, че краен брой подобни стъпки води до проблем с линейно програмиране, чието решение е цяло число и следователно желаното.

Решение: Нека приведем системата от линейни ограничения и целевата функция в каноничната форма:

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

Решаване на булеви LP задачи по метода на Balazs.

Създайте своя собствена версия за задача за целочислено линейно програмиране с булеви променливи, като вземете предвид следните правила: задачата използва поне 5 променливи, поне 4 ограничения, коефициентите на ограниченията и целевата функция се избират произволно, но в такива начин, по който системата от ограничения е съвместима. Задачата е да се реши LCLP с булеви променливи с помощта на алгоритъма на Balazs и да се определи намаляването на сложността на изчисленията във връзка с решаването на проблема с помощта на метода на изчерпателно търсене.

Изпълнение на ограниченията

F стойност

Ограничение за филтриране:

Определяне на намаляването на изчислителните усилия

Решението на проблема с помощта на метода за изчерпателно търсене е 6*25=192 изчислени израза. Решението на задачата с помощта на метода на Балаш е 3*6+(25-3)=47 изчислени израза. Общото намаление на сложността на изчисленията във връзка с решаването на проблема чрез метода на изчерпателно търсене е:

Заключение

Процесът на проектиране на информационни системи, които прилагат нови информационни технологии, непрекъснато се подобрява. Фокусът на системните инженери е все повече върху сложни системи, което затруднява използването на физически модели и увеличава значението на математическите модели и машинната симулация на системи. Машинната симулация се превърна в ефективен инструмент за изучаване и проектиране на сложни системи. Уместността на математическите модели непрекъснато нараства поради тяхната гъвкавост, адекватност към реални процеси и ниска цена на внедряване на базата на съвременни персонални компютри. Все повече и повече възможности се предоставят на потребителя, т.е. специалиста по моделиране на системи с помощта на компютърни технологии. Използването на моделиране е особено ефективно в ранните етапи на проектиране на автоматизирани системи, когато цената на грешните решения е най-значителна.

Съвременните изчислителни средства позволиха значително да се усложнят моделите, използвани при изследването на системите; стана възможно изграждането на комбинирани, аналитични и симулационни модели, които отчитат цялото разнообразие от фактори, които се срещат в реалните системи, т.е. , използването на модели, които са по-адекватни на изследваните явления.

Литература:

1. Ляшченко И.Н. Линейно и нелинейно програмиране / I.N Lyashchenko, E.A Karagodova, N.V. Chernikova, N.Z. - К.: “Висше училище”, 1975, 372 с.

2. Методически указания за изпълнение на курсов проект по дисциплината „Приложна математика” за студенти от специалност „Компютърни системи и мрежи” на редовна и задочна форма на обучение / Съставител: И.А.Балакирева, А.В.Скатков - Севастопол: Издателство SevNTU, 2003. - 15 с.

3. Ръководство за изучаване на дисциплината „Приложна математика”, раздел „Методи за глобално търсене и едномерна минимизация” / Comp. А. В. Скатков, И. А. Балакирева, Л. А. Литвинова - Севастопол: Издателство СевГТУ, 2000 г. - 31 с.

4. Ръководство за изучаване на дисциплината „Приложна математика” за студенти от специалност „Компютърни системи и мрежи” Секция „Решаване на задачи от целочислено линейно програмиране” за редовна и задочна форма на обучение / Съставители: И. А. Балакирева, А. В. Скатков : Издателство на SevNTU, 2000. - 13 с.

5. Акулич И.Л. Математическо програмиране в примери и задачи:

6. Учебник помощ за студенти по икономика. специалист. университети.-М.: Висш. училище, 1986.- 319 с., ил.

7. Андронов С.А. Оптимални методи за проектиране: Текстове на лекции / SPbSUAP. СПб., 2001. 169 с.: ил.

Подобни документи

Алгоритъм за решаване на задачи от линейното програмиране по симплексния метод. Построяване на математически модел на задача от линейно програмиране. Решаване на задача от линейно програмиране в Excel. Намиране на печалба и оптимален производствен план.

курсова работа, добавена на 21.03.2012 г


Графично решаване на проблеми. Изготвяне на математически модел. Определяне на максималната стойност на целевата функция. Решение по симплексния метод с изкуствена основа на задачата за канонично линейно програмиране. Проверка на оптималността на решението.

тест, добавен на 05.04.2016 г


Теоретични основи на линейното програмиране. Задачи на линейно програмиране, методи за решаване. Анализ на оптималното решение. Решение на едноиндексна задача за линейно програмиране. Постановка на проблема и въвеждане на данни. Изграждане на модел и етапи на решение.

курсова работа, добавена на 12/09/2008


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

курсова работа, добавена на 31.10.2014 г


Изграждане на математически модел с цел получаване на максимална печалба за предприятието, графично решение на проблема. Решаване на проблема с помощта на добавката SOLVER. Анализ на промените в ресурсните запаси. Определяне на границите за изменение на коефициентите на целевата функция.

курсова работа, добавена на 17.12.2014 г


Математическо програмиране. Линейно програмиране. Проблеми с линейно програмиране. Графичен метод за решаване на задачи по линейно програмиране. Икономическа постановка на задачата за линейно програмиране. Изграждане на математически модел.

курсова работа, добавена на 13.10.2008 г


Решаване на задача от линейно програмиране по графичен метод, проверка в MS Excel. Анализ на вътрешната структура на решаване на проблем в програма. Оптимизиране на производствения план. Решаване на задачата чрез симплексния метод. Многоканална система за масово обслужване.

тест, добавен на 05/02/2012


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

тест, добавен на 04/11/2012


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

курсова работа, добавена на 17.12.2012 г


Анализ на решението на задача от линейното програмиране. Симплексен метод с използване на симплексни таблици. Моделиране и решаване на LP задачи на компютър. Икономическа интерпретация на оптималното решение на проблема. Математическа постановка на транспортната задача.