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 )


 

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

78666. Научно-технический и инновационный потенциал организации :сущность, структура и основные показатели оценки 41.5 KB
  Научнотехнический потенциалстрана регион организация общественная форма совокупности живого и общественного труда обеспечивающая производство новых знаний создание освоение нововведений в т. Межотраслевые технологические прогнозы кривые появления и развития новых технологий формирование компетенций поддерживающих прогрессивные технологии на уровне фирмы. Принципы финансирования незапланированных инициатив выявление новых идей сотрудников поощрение их нововведенческого поведения. Оценивать важность новых инициатив и их...
78667. Основные направления инновационной политики государства 53.5 KB
  Одним из важнейших показателей состояния и развития научной деятельности является численность исследователей техников и вспомогательного персонала занятых в инновационной сфере. Россия направляющая в научнотехническую сферу менее 1 ВВП все больше отстает от группы промышленно развитых и некоторых развивающихся стран. Недостаток капитала выступает сегодня в России в качестве одного из основных ограничителей научнотехнического развития. Устойчивой гарантией динамичного развития научнотехнической сферы в условиях рынка является только...
78668. Инновация: сущность, источники, жизненный цикл 31.5 KB
  Эти различия затрагивают прежде всего общую продолжительность цикла продолжительность каждой стадии внутри цикла особенности развития самого цикла разное количество стадий. Виды и количество стадий жизненного цикла определяются особенностями той или иной инновации. Однако у каждой инновации можно определить стержневую то есть базовую основу жизненного цикла с четко выделенными стадиями. Схемы жизненного цикла различны у инновационного продукта и у инновационной операции процедуры.
78669. Программно-целевой метод управления 28 KB
  Программноцелевой метод управления. Программноцелевой метод научнопрограммный и временной способ увязки планируемых целей с ресурсами. Программноцелевой метод в управлении ориентирован на достижение конечного результата в логике поэтапного действия: формирование дерева целей разработка адекватной исполняющей программы реализация управляющей программы. Ключевой идеей программноцелевого метода выступает матрица цель средство иерархическая структура строго сформулированных целей программных элементов каждый из которых служит...
78670. Инновационная стратегия фирмы 33.5 KB
  Инновационная стратегия фирмы. Обычно к таким стратегиям относят. Стратегия непрерывного совершенствования кайзен продукции. Инновационная стратегия целенаправленная деятельность по определению приоритетов перспективного развития организации и их достижению в результате которой обеспечивается новое качество производства и управления.
78671. Прогрессивные формы организации инновационной деятельности :бизнес-инкубаторы, технопарки, технополисы 31 KB
  Инновационная деятельность это процесс направленный на реализацию результатов законченных научных исследований и разработку иных научно технических достижений интеллектуального продукта. Отличительные черты: комплексность по научнопроизводственному циклу научные учреждения вузы промышленные предприятия компактность расположения ограниченность площади расположение в экологически чистых районах. Технополис научнотехнический комплекс соединяющий научнотехническую деятельность с наукоемким производством с хорошо развитой...
78672. Система індукційного нагріву для нагрівання металів до температури оптимальної для пластичної деформації 1.51 MB
  В даному дипломному проекті розроблена система індукційного нагріву, яка призначений для нагрівання металів до температури оптимальної для пластичної деформації. Було визначено питому потужність системи для необхідного розміру деталі та оптимального часу нагрівання. Розглянуто аналоги та їх основні параметри. Розроблена структурна та принципова схеми системи.
78673. Предпринимательство как вид экономической деятельности. Виды предпринимательства 35 KB
  Виды предпринимательства. Рыночная экономика экономика свободного предпринимательства. В зависимости от содержания и направленности предпринимательской деятельности объекта приложения капитала и получения конкретных результатов связи предпринимательской деятельности с основными стадиями воспроизводственного процесса различают следующие виды предпринимательства. Коммерческое торговое предпринимательство Принцип организации торгового предпринимательства несколько отличается от производственного так как предприниматель выступает...
78674. Инфраструктурное обеспечение предпринимательской деятельности 25 KB
  система общих условий воспроизводства предпринимательского типа представляющая собой совокупность техникотехнологических организационноэкономических и социальных взаимосвязей тех элементов инфраструктуры которые обеспечивают обслуживание процесса предпринимательства на уровне макро мезо и микроэкономики. являются научность и системность в формировании и развитии предпринимательства и его инфраструктуры а также постепенность и многообразие моделей инфраструктурного обеспечения предпринимательства. Прежде всего нужна трансформация...