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 )


 

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

32226. Тактика предъявления обвинения и тактические основы допроса обвиняемого 40.5 KB
  Для эффективного его проведения следователю необходимо хорошо разбираться в психологии допрашиваемых уметь устанавливать с ними правильные взаимоотношения варьировать с учетом конкретной ситуации личности допрашиваемого имеющихся доказательств различные тактические приемы и методы психологического воздействия. Предметом допроса могут быть: обстоятельства входящие в предмет доказывания место время обстоятельства субъекты; обстоятельства необходимые для достижения промежуточных целей расследования; обстоятельства с помощью...
32227. Подготовка следователя к проведению следственного эксперимента 30 KB
  Подготовка следователя к проведению следственного эксперимента. При этом подготовительные действия обеспечиваемые следователем можно подразделить на два этапа: подготовка до выезда на место проведения эксперимента и непосредственно на месте до совершения самих опытных действий. На первом этапе следователь должен определить цель эксперимента т. Тщательное изучение этих материалов позволяет определить место время и условия производства эксперимента круг его участников и роль каждого из них.
32228. Составление плана расследования. Основные и вспомогательные формы планов 35 KB
  Составление плана расследования. Это приводит к необходимости планирования расследования различных дел во времени подготовка документов отчётов и т. 2 План расследования по конкретному преступлению. Составляется план расследования по версиям.
32229. Каноническое представление уравнения Эйлера 137.5 KB
  Например требуется определить закон изменения якорного тока и скорости вращения двигателя постоянного тока который поворачивает платформу экскаватора. Динамика двигателя описывается уравнением равновесия моментов момент развиваемый двигателем уравновешивается динамическим моментом и моментом сопротивления: п.1 где Мдв=Смi момент развиваемый двигателем См постоянная двигателя i якорный ток J момент инерции приведенный к валу двигателя скорость вращения...
32230. Синтез оптимального управления при ограничениях на управляющее воздействие 163 KB
  Более эффективно решение задач синтеза оптимального управления при ограничениях управляющих воздействий осуществляется путем использования принципа максимума предложенного в 1956 году академиком Л. Принцип максимума является дальнейшим развитием вариационного исчисления. Это условие положено в основу принципа максимума. Рассмотрим применение принципа максимума Понтрягина для решения задач оптимизации.
32231. Метод динамического программирования Р. Беллмана 1.14 MB
  6 величина определяется в соответствии с уравнениями 7.10 При условиях ; Оптимальное уравнение определяется в результате решения уравнения 7.10 можно заменить уравнениями в частных производных 7.4 получим Из уравнения получим П 7.
32232. Связь между принципами максимумами и динамическим программированием 359.5 KB
  17 является скалярным произведением векторов Ψ и X: Н = ψ 8. Вектор касателен к траектории t и нормален к векторам ψ и ψ что определяет оптимальный процесс перехода из в . Максимальное быстрое уменьшение J будет происходить очевидно что если вектор скорости Хточка в направлении убывании убывание J будет максимальным. Для обеспечения этого необходимо чтобы проекция вектора скорости движения изображающей точки Хточка на вектор отрицательной нормалям к поверхности J...
32233. Синтез оптимального по быстродействию программного управления 211 KB
  3 Где уравнение динамики объекта управления Поскольку то максимум функции Н реализуется одновременно с максимумом функции: 9. Решим задачу определения оптимального по быстродействию программного управления на примере объекта второго порядка: .1 То структурная схема объекта представлена на рис. Структурная схема объекта управления В соответствии со структурной схемой на рис.
32234. Синтез замкнутых систем управления, оптимальных по быстродействию 147 KB
  невозможно путём интегрирования уравнений объекта найти уравнения траекторий в nмерном пространстве.6 в этом случае можно представить относительно других координат: где i = 12n Тогда уравнения проекций фазовых траекторий на координатные плоскости при U = const будут иметь вид: Интегрируя это выражение получим: где ; координаты точек через которые проходит проекция 10.2 С помощью уравнений проекций фазовых траекторий определяем координаты точек переключений U.6 получим выражение...