11765

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

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

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

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

Украинкский

2013-04-11

1.27 MB

4 чел.

Лабораторна робота № 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 )


 

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

30524. Основні культурологічні теорії 143 KB
  Історичні науки вивчають процеси становлення і розвитку конкретних народів в їх безпосередній реальності, в хронологічній послідовності подій, вказуючи на конкретні форми міжрегіональної взаємодії.
30526. Модель Белла - Ла-Падулы 97 KB
  Устная часть Основным положением политики безопасности является назначение всем участникам процесса обработки защищаемой информации и документам в которых она содержится специальной метки секретно совершенно секретно и т. Такая метка называется уровнем безопасности. Все уровни безопасности упорядочиваются с помощью установленного отношения доминирования. Контроль доступа осуществляется в зависимости от уровней безопасности взаимодействующих сторон на основании двух правил: 1.
30527. Основные положения критериев TCSEC (“Оранжевая книга”). Фундаментальные требования компьютерной безопасности. Требования классов защиты 30.54 KB
  Фундаментальные требования компьютерной безопасности. Критерии оценки безопасности компьютерных систем TCSEC получившие неформальное Оранжевая книга были разработаны и опубликованы Министерством обороны США в 1983 г. с целью определения требований безопасности предъявляемых к аппаратному программному и специальному программному и информационному обеспечению компьютерных систем и выработки методологии и технологии анализа степени поддержки политики безопасности в компьютерных системах в основном военного назначения. Усиление требований...
30529. Использование существующих нормативных актов для создания системы информационной безопасности. Основные положения руководящих правовых документов 30.27 KB
  В то же время согласно статье 55 Конституции права и свободы человека и гражданина в том числе на доступ к информации могут быть ограничены федеральным законом в той мере в какой это необходимо в целях защиты основ конституционного строя нравственности здоровья прав и законных интересов других лиц обеспечения обороны страны и безопасности государства. Наряду с другими актами законодательства регулирует вопросы использования информации содержащей сведения составляющие государственную тайну допуска организаций и должностных лиц к...
30530. Система международных и российских правовых стандартов. Стандарт ISO 27001:2005 107.5 KB
  Стандарт ISO 27001:2005. Доска Международный стандарт ISO IEC 27001:2005 Информационные технологии Методы защиты Системы менеджмента информационной безопасности Требования разработан Международной организацией по стандартизации ISO и Международной электротехнической комиссией IEC на основе британского стандарта BS 77992:2002. Стандарт ISO 27001 определяет информационную безопасность как: сохранение конфиденциальности целостности и доступности информации; кроме того могут быть включены и другие свойства такие как подлинность...
30531. Требования доктрины информационной безопасности РФ и ее реализация в существующих системах информационной безопасности 67.33 KB
  Доктрина развивает Концепцию национальной безопасности Российской Федерации применительно к информационной сфере. Доктрина информационной безопасности Российской Федерации представляет собой совокупность официальных взглядов на цели задачи принципы и основные направления обеспечения ИБ в РФ. Интересы государства в информационной сфере заключаются в создании условий для гармоничного развития российской информационной инфраструктуры суверенитета и территориальной целостности России политической экономической и социальной стабильности....
30532. Понятие и основные организационные мероприятия по обеспечению информационной безопасности 20.2 KB
  В Законе РФ Об участии в международном информационном обмене закон утратил силу в настоящее время действует Об информации информационных технологиях и о защите информации информационная безопасность определяется аналогичным образом как состояние защищенности информационной среды общества обеспечивающее ее формирование использование и развитие в интересах граждан организаций государства. Под информационной безопасностью понимается защищенность информации и поддерживающей инфраструктуры от случайных или преднамеренных воздействий...