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 )


 

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

80859. ФЕДЕРАЛЬНОЕ ГОСУДАРСТВО: ТИПЫ ФЕДЕРАЦИЙ, СПЕЦИФИКА РОССИИ 88.5 KB
  Распределение власти по вертикали между уровнями Федерации, Субъектов Федерации, МСУ. Верховенство Конституции РФ, Федеральных законов над Конституциями, законами субъектов Федерации (только по предметам совместного ведения РФ и ее субъектов). Разделение властей
80860. ГОСУДАРСТВЕННАЯ ПОЛИТИКА И ГОСУДАРСТВЕННОЕ УПРАВЛЕНИЕ: ОБЩЕЕ И ОСОБЕННОЕ 48.88 KB
  Гос политика это целенаправленная деятельность органов государственной власти по решению общественных проблем доступностью и реализации общезначимых целей развития общества или его отдельных сфер. Она является средством позволяющим государству достичь определенных целей в конкретной области используя правовые экономические административные методы воздействия опираясь на ресурсы которые имеются в его распоряжении. Формирование и реализация госй политики обычно имеют 4 этапа политический цикл: 1й этап – опреде общественных...
80861. Структура федеральных органов исполнительной власти (ФОИВ) и Организация их деятельности 46.19 KB
  Функции ФОИВ руководство деятельностью которого осуществляет Президент РФ определяются указом Президента РФ. Функции ФОИВ руководство деятельностью которого осуществляет Правительство РФ постановлением Правительства РФ. Функции: выработка государственной политики и нормативноправовому регулированию в установленной актами Президента РФ и Правительства РФ сфере деятельности. Возглавляет входящий в состав Правительства РФ министр РФ федеральный министр; Он не вправе осуществлять функции по контролю и надзору правоприменительные...
80862. Особенности государственного устройства и органы власти субъектов РФ 48.73 KB
  Среди субъектов РФ различают виды: республики края области автономную область города федерального значения и автономные округа. Частями субъектами российского государства являются национальные государства республики всего их 21; государственнотерриториальные образования края 6 области 49 города федерального значения 2; национальногосударственные образования 1 автономная область и 10 автономных округов. иметь свои конституции госный язык и госную символику; КРАЯ ОБЛАСТИ ГОРОДА ФЕДГО ЗНАЧЕНИЯ автономная область...
80863. Государственная служба как социально-правовой институт 48.6 KB
  Социальное понятие государственная служба очень многогранно и в широком смысле слова под государственной службой как социальным институтом понимается: исторически сложившаяся устойчивая форма организации совместной деятельности лиц находящихся на службе государства; особый вид социальной практики нацеленной в конечном итоге на реализацию функций государства на обеспечение прав и свобод граждан на создание благоприятных социальных условий для их достойной жизни; функция особого социального слоя людей государственных служащих...
80864. Критерии эффективности государственного управления. Взаимодействие общества и государства 44.77 KB
  Взаимодействие общества и государства. Государственное управление – это практическое организующее и регулирующее воздействие государства на общественную жизнедеятельность в целях ее упорядочения сохранения или преобразования которое опирается на власть. Эффективность гос управления – соотношение достигнутого результата целей управления с затраченными на это ресурсами.
80865. Особенности разрешения конфликтов в системе государственного и муниципального управления 46.19 KB
  Управление конфликтами – процесс целенаправленного воздействия на персонал с целью устранения причин породивших конфликт и перевод конфликта в рациональное русло для достижения желаемых результатов. Управление конфликтами включает в себя: прогнозирование конфликтов предупреждение одних и стимулирование других прекращение и подавление конфликтов их регулирование и разрешение. Прогнозирование конфликта – представление о будущем конфликте с определенной вероятностью указания времени и места действий. культуры нетерпимой к конфликтам в...
80866. Понятие и основные теории местного самоуправления 47.27 KB
  МСУ составляет одну из основ конституционного строя РФ. МСУ в РФ форма осуществления народом своей власти обеспечивающая в пределах установленных Конституцией РФ федеральными законами а в случаях установленных федеральными законами законами субъектов РФ самостоятельное и под свою ответственность решение населением непосредственно и или через органы МСУ вопросов местного значения исходя из интересов населения с учетом исторических и иных местных традиций ФЗ. МСУ является первичным уровнем публичной власти и системы управления в...
80867. Местные интересы, роль и функции местного самоуправления в обществе 45.02 KB
  Ориентация на учет местных интересов предопределяет роль и функции местного самоуправления в современном обществе. Политологи разделяют общество на три основных сектора каждому из которых отведены своя роль и свои функции. Если под этим углом зрения взглянуть на местное самоуправление то можно сделать вывод что в современном обществе оно выполняет все три перечисленные функции.