11765

Задачі лінійного цілочислового програмування

Лабораторная работа

Математика и математический анализ

Лабораторна робота № 6 Задачі лінійного цілочислового програмування Короткі теоретичні відомості 21. МЕТОД ГОМОРІ РОЗВЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ЦІЛОЧИСЛОВОГО ПРОГРАМУВАННЯ Розглянемо задачу лінійного цілочислового програ

Украинкский

2013-04-11

1.27 MB

3 чел.

Лабораторна робота № 6

«Задачі лінійного цілочислового програмування»

  1.  Короткі теоретичні відомості
    1.  § 21.   МЕТОД ГОМОРІ РОЗВ'ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ЦІЛОЧИСЛОВОГО ПРОГРАМУВАННЯ

Розглянемо   задачу   лінійного   цілочислового   програмування (2.40)-(2.43) (або просто - цілочислову задачу).

Суть методу Гоморі її розв'язання полягає в тому, що спочатку знаходять оптимальний розв'язок * задачі (2.40)-(2.42), не вимагаючи щоб він був цілочисловим. Цей розв'язок є крайньою точкою області обмежень М, що задається обмеженнями (2.41), (2.42). Якщо його компоненти - цілі числа, то  *   водночас є розв'язком цілочислової задачі. Інакше в опуклій множині М виділяють опуклу підмножину M1 М яка містить всі ті точки з цілочисловими координатами, що й множина М, але не містить розв'язку * задачі (2.40)-(2.42) (тобто відтинають деяку “малу” частину від множини М). Далі для множини М1 проводять аналогічні міркування, що й для множини М. Тобто знаходять оптимальний розв'язок *  задачі (2.40) для множини обмежень М1, і тоді або *  є оптимальним розв'язком цілочислової задачі (якщо всі компоненти *  - цілі числа), або інакше знову доводиться звужувати множину  М1 до опуклої підмножини М2  М1  і т.д. У результаті такого кількаразового звуження множини M або дістанемо цілочисловий розв'язок опт  задачі (2.40) для деякої опуклої множини N  М і тоді опт  буде розв'язком початкової задачі, або виявиться, що ця задача не має розв'язку. Кожен крок переходу від множини М до множини М1,  від М1, до М2 і т.д. здійснюють долучаючи до обмежень (2.41), (2.42) додаткове обмеження (правильне обмеження або відтинання), що рівносильно відтинанню від множини М такої її частини, в якій є оптимальний розв'язок задачі (2.40) для однієї з допустимих множин М, або M1, або М2 і т.д. але немає жодного допустимого цілочислового розв'язку задачі (2.40)-(2.43).

Нам будуть потрібні додаткові поняття. Цілою частиною числа х, яка позначається [х], називається найбільше ціле число, яке не від числа х, отже, [х] ≤ х . Дробовою частиною числа х називається

число {х} = х - [х]; очевидно, що х = [х] +{х) і 0  {х} < 1.

Наприклад:    [2,14] = 2,    [-2,14] =-3,    {2,14} = 0,14,    {-2,14} =2,14-(-3) = 0,86.

Перейдемо до побудови правильного обмеження. Нехай задача лінійного програмування (2.40)-(2.42) має розв'язок і він знайдений симплекс   методом.   Припустимо,   що   останній   симплексній   таблиці розв’язування задачі (2.40)-(2.42) відповідає система рівнянь

         (2.47)

Тоді її базисний розв'язок *  =(b1;….;bm;0;…..;0) є оптимальним опорним планом задачі (2.40)-(2.42).

Якщо всі числа bi,i= , цілі, то *  - шуканий цілочисловий розв'язок задачі (2.40)-(2.43).

Якщо серед  чисел b1є дробові, то виберемо одне з них, наприклад bi0; воно розташоване в В-стовпці та i0 -му рядку останньої симплексної таблиці для розв'язування задачі (2.40)-(2.42). Якщо в i0 -му рядку цієї таблиці справа від числа bi0, записані лише цілі числа ai0j, j= , то i0 - те рівняння системи (2.47)

(2-48)

Не має  цілочислового розв'язку, а тому цілочислова задача також не має  розв’язку. Отже, припустимо, що серед чисел aioj є  дробові. Підставимо вирази

bi0=[ bi0]+{ bi0},aioj=[ aioj]+{ aioj }

в рівняння (2.48)

[bi0]+ { bi0} = xio+[aioj]+{aioj})xj

і залишимо його  у вигляді

Xio=([bio]-aioj]xj)+( bi0- aioj}xj         (2.49)

Остання рівність справджується для всіх планів задачі (2.40)-(2.42), причому оскільки {bi0}<І ,то

{bi0}  aioj }xj<1       (2.50)

Припустимо тепер, що рівність (2.49) записано для цілочислового плану. Оскільки xio i   ([bio]- aioj]xj)  - цілі числа, то з (2.49) випливає, що ({bio}- aioj}xj)- також ціле число, а з (2.50) - що виконується нерівність

{bio}- aioj}xj ≤0.           (2.51)

Отже, компоненти кожного цілочислового плану задачі (2.40)-(2.42) задовольняють нерівність (2.51). Однак компоненти оптимального плану *  =(b1;….;bm;0;…..;0) цю нерівність не задовольняють (бо ліва частина нерівності дорівнюватиме {bio} > 0).

Означення.     Нерівність (2.51) називається правильним обмеженням або обмеженням Гоморі.

Долучаючи правильне обмеження (2.51) до системи (2.41), (2.42), ми звужуємо область обмежень, відтинаючи від неї деяку частину разом з оптимальним планом  *  , але так, щоб при цьому звужена і початкова множини мали ті самі цілочислові плани.

Продовжимо розв'язання цілочислової задачі (2.40)-(2.43) . Введемо додаткову  невідому   xn+1 ≥ 0   в  правильне  обмеження  (2.51) і перетворимо його на рівняння

- aioj} xj+xn+1=-{ bio }(2 52)

яке також   називають   правильним   обмеженням.   Далі   знаходимо розв’язок задачі (2-40)-(2.42), (2.52), хт+1 ≥0 (тобто задачі для звуженої множини обмежень) і побудову нових правильних обмежень продовжуємо доти, доки не знайдемо цілочисловий розв'язок або не виявимо, що задача не має розв'язку.

Практично розв'язування задачі (2.40)-(2.42), (2.52), хт+1 ≥0, можна виконувати, скориставшись останньою симплексною таблицею для зв'язування задачі (2.40)-(2.42). Для цього останню таблицю доповнюють ще одним рядком, який відповідає обмеженню (2.52), і новим стовпцем, який відповідає додатковій невідомій хт+1 ≥0 (всі елементи в новому стовпці дорівнюють 0, за винятком останнього, який дорівнює 1). Тепер у розширеній таблиці елементи в В-стовпці визначають базисний розв'язок системи (2.41), (2.52), для якого виконуються умови оптимальності (у dj -рядку всі оцінки     dj ≥ 0), хоча він сам не є ні допустимим, ні оптимальним (бо в В-стовпці останній елемент                          - (-{bio })).Далі задачу розв'язують, користуючись двоїстим симплексним методом (див. § 19).

Алгоритм розв'язування цілочислової задачі.

1.Розв'язати задачу (2.40)-(2.42) симплексним методом і записати останню симплексну таблицю, яка відображає хід розв'язання. Якщо задача (2.40)-(2.42) не має розв'язку, то і цілочислова задача (2.40)-(2.43) також не має розв'язку.

2.Якщо в останній симплексній таблиці всі елементи в B - стовпці є цілими числами, то задачу (2.40)-(2.43) розв'язано і її розв'язок такий самий, як і задачі (2.40)-(2.42).

3.Якщо в В-стовпці є таке дробове число, нехай bio, справа від якого в тому самому рядку записані лише цілі числа aioj, то задача(2.40)-(2.43) не має розв'язку (бо не має цілочислових планів).

4.Побудова правильного обмеження. Якщо не виконуються умови п.п. 2 і 3, то треба вибрати в В-стовпці останньої симплексної таблиці одне з дробових чисел, нехай bio , і скласти для нього правильне обмеження (2.52). На практиці правильне обмеження складають для того числа в bio , яке має найбільшу дробову частину серед усіх чисел В- стовпця.

5.Доповнити останню симплексну таблицю розв'язування задачі (2.40)-(2.42) додатковими рядком для обмеження (2.52) і стовпцем для невідомої xn+1; у результаті буде отримано симплексну таблицю для базисного розв'язку системи рівнянь (2.41), (2.52), який задовольняє умови оптимальності (всі dj≥ 0).

6.Застосувати двоїстий симплексний метод (див. § 19) і отримати оптимальний план для звуженої області обмежень (2.41), (2.42), (2.51).

Далі повернутися до виконання п.п. 2-6, але стосовно нових оптимального плану і області обмежень. Застосування алгоритму припиняється, якщо буде знайдено цілочисловий розв'язок (п. 2) або виявлено, що задача не має розв'язку (п. 3).

Приклад  1.

Знайти розв'язок задачі

F=-3x1+5x2+4x3=>max  (а)

за обмежень

 (b)

Х123≥0 і цілі.              (С)

Р о з в ' я з а н н я. Введемо в систему обмежень додаткові невідомі х4, х5, х6

(d)

                Х1,...,х6≥О                      (e)

Хід розв'язування задачі відображено в табл. 20.

Таблиця 20

№ з\п

Базис

     С1

Сб

B

C1=-3

C2=5

C3=4

C4=0

C5=0

C6=0

C7=0

C8=0

X1

X2

X3

X4

X5

X6

X7

X8

1

X4

0

13

5

0

3

1

0

0

2

X5

0

7

4

-2

1

0

1

0

3

X6

0

15

6

4

0

0

0

1

4

dj

0

3

-5

-4

0

0

0

5

X4

0

13

5

0

3

1

0

0

6

X5

0

7

0

1

0

1

7

X2

5

1

0

0

0

8

dj=d1=z1-c1

0

-4

0

0

9

X3

4

0

1

0

0

0

10

X5

0

0

0

1

0

11

X2

5

1

0

0

0

0

12

dj=d2=z2-c1

0

0

0

0

13

X7

0

0

0

0

0

1

14

5

min

15

X3

4

0

1

0

0

0

0

16

X5

0

0

0

1

0

2

0

17

X2

5

3

1

1

0

0

0

0

1

0

18

X6

0

3

2

0

0

0

0

1

-4

0

19

dj=d3=z3-c1

0

0

0

0

5

0

20

X8

0

0

0

0

0

0

1

21

16

4

min

22

X3

4

4

1

0

1

0

0

0

0

1

23

X5

0

9

5

0

0

0

1

0

2

-1

24

X2

5

3

1

1

0

0

0

0

1

0

25

X6

0

3

2

0

0

0

0

1

-4

0

26

X4

0

1

2

0

0

1

0

0

0

-3

27

dj=d4=z4-c1

31

12

0

0

0

0

0

5

4

У рядках 1-12 табл. 20 (але поки-що без урахування стовпців для х7 та х8) подано розв'язування задачі (а), (d), (e) симплексним методом, а саме:  здійснено два симплексні перетворення з розв’язувальними елементами 4 і 3 (вони виділені в таблиці). У результаті перетворень отримано не цілочисловий оптимальний план *=(0;3; 4;0; 10;0), F(*)=36.

Оскільки для плану * не виконуються п.п. 2 і 3 алгоритму, то переходимо до п. 4 – побудови правильного обмеження. Знайдемо дробові частини чисел, які розташовані в В – стовпці в рядках 9 -11 :, ,  Для побудови правильного обмеження виберемо число  , у якого дробова частина найбільша (хоча вибір чисел  або  також не був би помилкою) і запишемо дробові частини коефіцієнтів рівняння, розташованих у рядку 11: ,. Згідно з  формулою (2-51) отримуємо правильне обмеження як нерівність

а, ввівши додаткову невідому х7, - як рівняння

Долучаємо це рівняння до системи обмежень (d).

Далі згідно з п. 5 алгоритму розширюємо симплексну таблицю, записавши в додатковому рядку 13 коефіцієнти рівняння (f), а в додатковому стовпці (у рядках 9, 10, 11, 13) - компоненти вектора 7=(0;0;0;1)T , який відповідає невідомій х7; у запис лінійної цільової функції F аргумент х7 входитиме з коефіцієнтом c7=0.

Зауваження. На практиці п.п. 4 і 5 алгоритму можна не розділяти, а виконувати одночасно. Ми, наприклад, могли ,не складати додаткового обмеження (f), а відразу доповнити таблицю рядком 13 і стовпцем для x7. У рядку 13 записати спочатку x7, коефіцієнт с7 = 0, а далі - від 'ємні дробові частини вільного члена і коефіцієнтів рівняння, розташованих у рядку 11, а в стовпці для x7- компоненти вектора

7=(0;0;0;1)T.

І, нарешті, за п. 6 алгоритму до розв'язування застосовуємо двоїстий симплексний метод. Спочатку доповнюємо таблицю рядком 14, за допомогою якого визначаємо в рядку 13 розв'язувальний елемент () (він виділений); далі в рядках 15-19 записуємо результат відповідного симплексного   перетворення   і   знаходимо   новий   оптимальний   план

*1=(0;3;;0;;3)T , F(*1)=.

Оскільки план *1 не цілочисловий, то алгоритм пошуку цілочислового розв'язку потрібно застосувати повторно. Для побудови правильного обмеження вибираємо компоненту x3= плану *1, яка знаходься в В-стовпці в рядку 15. Коефіцієнти відповідного правильного обмеження на підставі зауваження відразу запишемо в додатковому рядку 20 (як від'ємні дробові частини чисел, що розташовані в рядку 15),а компоненти додаткового вектора  8 =(0;0;0;0;1)T  - в додатковому стовпці для невідомої x8. Далі вводимо рядок 21, за допомогою якого у рядку 20 виділяємо розв'язувальний елемент . Результат відповідного симплексного перетворення записуємо в рядках 22-27. З них отримуємо оптимальний цілочисловий розв'язок початкової задачі

0=(0;3;4),Fmax=31.

Приклад 2.

На складі знаходяться дошки завдовжки 4м і 3м. З них потрібно нарізати 90 дощок завдовжки по 2м, 205 - завдовжки по 1.5м і 310 - завдовжки по 0.8м. Як спланувати  розрізання чотириметрових дощок, щоб сумарна величина відходів була найменшою? (задачі 2 про розкрій матеріалу з § 20)

Р о з в ' я з а н н я. Математична модель задачі задана умовами (2.44)-(2.46). Щоб застосувати симплексний метод, перетворимо систему обмежень (2.45), а саме: поділимо обидві частини першого рівняння на 2, третього - на 5, а в друге введемо штучну невідому x7. Тоді отримаємо задачу

F=0.5x2+0.4x3+0.2x4+0.1x5+Mx7=>min,    (а)

                     (b)

xj≥0 і цілі, j= (c)

Розв'язок задачі подано в табл. 21. У частинах Т1 і T2 табл. 21 (не беручи до уваги стовпця для x8) знайдено оптимальний не цілочисловий план задачі *  =(45;0;0;102,5;0;41.5)T.

У частині T3 відображено пошук цілочислового розв'язку. Ця частина отримана на основі долучення до системи (b) правильного обмеження

-0.5 = -0.5x2 -0.5x5+x8,

складеного за  елементами  рядка,  в  якому розташована  компонента x4 = 102.5    оптимального   плану    *.   У   рядку   для   x8   виділено розв'язувальний елемент -0.5 (за правилами двоїстого симплексного  методу на основі зауваження з § 19), а далі наведено результат  відповідного симплексного перетворення. Останній симплексній таблиці відповідає оптимальний цілочисловий план 0=(45;0;0;102;1;41)T і значення цільової функції Fmin= 20.5 .

Отже, щоб із чотириметрових дощок отримати вказані кількості дощок різної довжини, потрібно порізати першим способом - 45 дощок четвертим - 102, п'ятим - 1 і шостим - 41. За такого плану розрізання відходи матеріалу будуть найменшими і становитимуть 20.5 м.

Таблиця 21

Базис

Сб

B

0

0.5

0.4

0.2

0.1

0

M

0

X1

X2

X3

X4

X5

X6

X7

X8

T1

X1

0

45

1

0.5

0.5

0

0

0

0

X7

M

205

0

1

0

2

1

0

1

X6

0

62

0

0

0.4

0.2

0.6

1

0

dj

205 M

0

M-5

-0.4

2M-0.2

M-0.1

0

0

T2

X1

0

45

1

0.5

0.5

0

0

0

0

X4

0.2

102.5

0

0.5

0

1

0.5

0

0

X6

0

41.5

0

-0.1

0.4

0

0.5

1

0

dj

20.5

0

-0.4

-0.4

0

0

0

0

T3

X8

0

-0.5

0

-0.5

0

0

-0.5

0

1

0.8

0

X1

0

45

1

0.5

0.5

0

0

0

0

X4

0.2

102

0

0

0

1

0

0

1

X6

0

41

0

-0.6

0.4

0

0

1

1

X5

0.1

1

0

1

0

0

1

0

-2

dj

20.5

0

-0.4

-0.4

0

0

0

0

Задачі для   самостійного  розв'язування

1-6.        Знайти розв'язки задач лінійного програмування за умов, що змінні - невід'ємні цілі числа.

  1.  Хід виконання лабораторної роботи.
    1.  Індивідуальне завдання.
    2.  Графічний метод рішення задачі                                                                                                (ОДЗ з позначенням цілочислових точок, градієнт, мах(х1,х2), мін(х1,х2) без врахування цілочислового рішення, мах(х1,х2), мін(х1,х2) з врахуванням цілочислового рішення)
    3.  Симплекс-метод рішення задачі без врахування цілочислового рішення                (пакет SimplexWin) 
    4.  Симплекс-метод рішення задачі з врахуванням цілочислового рішення

                    (пакет …., http://math-ua.semestr.ru/simplex/integer.php )


 

А также другие работы, которые могут Вас заинтересовать

52913. Sport. Конспект урока по английскому языку 7 класс 65.5 KB
  One group told us about how to prepare to a football competition. Now we will listen another group with its project how to organize basketball game. Let’s start.
52914. Людина – частина Всесвіту. Етика, 6 клас 34 KB
  Визначте які риси і життєві правила притаманні людині яка живе в гармонії з природою. На великому аркуші паперу намалюйте її портрет на якому зобразіть визначені вами риси. Визначте які риси й життєві правила притаманні людині яка дбає про своє здоров’я. На великому аркуші паперу намалюйте її портрет на якому зобразіть визначені вами риси.
52915. Використання ігрового матеріалу при вивченні і засвоєнні нових термінів на уроках етики 55 KB
  Використання у педагогічній практиці ігрових моментів – це лише один з можливих шляхів отримання учнями знань з предмета реалізації своїх можливостей здобуття не тільки гарних оцінок але і задоволення від уроку гра допомагає дітям повірити в себе викликає натхнення і захоплення. Гра дає надзвичайно багаті можливості бо дозволяє кожній дитині відчути себе суб’єктом життєдіяльності виявляти і розвивати свою особистість. Але слід зазначити що гра – це не самоціль а лише один із засобів у системі формування творчої допитливості. Гра –...
52916. У чому полягає етика відносин між народами в демократичному суспільстві. Урок 106 KB
  Мета уроку: збагатити знання учнів про багатокультурну державу та поліетнічне суспільство, на практичних прикладах розкрити зміст понять «патріотизм», «шовінізм»; продовжити вчити учнів працювати з текстом, виділяти головне, находити відповіді на питання, вдосконалювати вміння висловлювати свою думку та поважати інші думки;
52917. Людина починається з добра 40 KB
  Розширити уявлення дітей про доброту вдосконалювати вміння аналізувати вчинки людей робити висновки; виховувати такі моральні якості: доброту милосердя взаємодопомогу повагу до старших. Плакат Добрі й погані вчинки людей образ Божої Матері сигнальні картки свічка плакат з островами Здоров’я МилосердяКоштовності Допомога Доброта. Раз добром зігріте...
52918. МИЛОСЕРДЯ І БЕЗКОРИСЛИВІСТЬ 694.5 KB
  Милосердя. Ісус Христос у Нагірній Проповіді пояснив що таке милосердя і безкорисливість. Прочитати про милосердя і безкорисливість на сторінці: перший варіант ; другий варіант
52919. Що таке етикет особливих випадків 115.5 KB
  Визначити основні етикетні вимоги до поведінки під час урочистостей а також якою має бути пове дінка в музеї магазині та бібліотеці. Діти в нашому з вами житті дуже часто виникають ситуації які вимагають від людини знання особливих доцільних саме в цьому випадку правил поведінки. Якою має бути поведінка під час урочистостей. Якою повинна бути поведінка під час вечору – відпочинку.