48416

Лінійне програмування

Конспект

Информатика, кибернетика и программирование

При дослідженні різноманітних економічних процесів і явищ виникають задачі знаходження таких управлінських рішень які б давали змогу оптимізувати хід процесу явищ. До задач лінійного програмування належать ті задачі в яких функція мети лінійно залежить від керованих параметрів а також співвідношення між керованими і некерованими параметрами мають лінійний вигляд. Обмеження на сировину і її витрати на виготовлення 1 плити кожного виду а також прибуток від реалізації 1 плити задані в таблиці: Тип сировини Витрати на 1 плиту Запаси сировини...

Украинкский

2013-12-10

112.29 KB

6 чел.

Лінійне програмування

  1.  Поняття про лінійне програмування. Приклади
  2.  Графічний метод розв’язування задач лінійного програмування
  3.  Постановка задач лінійного програмування
  4.  Симплекс метод розв’язування задач лінійного програмування

1. Поняття про лінійне програмування. Приклади.

При дослідженні різноманітних економічних процесів і явищ виникають задачі знаходження таких управлінських рішень, які б давали змогу оптимізувати хід процесу, явищ.

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

На хід процесу впливають певні фактори (чинники). Частина з них є незмінною протягом процесу, їх називають некерованими параметрами, інша частина задається (вибирається) в ході прийняття управлінського рішення, такі параметри називаються керованими.

В основному критерій (функція мети) залежить від керованих і некерованих параметрів. Крім того, сам процес описується у вигляді певних математичних співвідношень і зв’язує між собою керовані і некеровані параметри.

До задач лінійного програмування належать ті задачі, в яких функція мети лінійно залежить від керованих параметрів, а також співвідношення між керованими і некерованими параметрами мають лінійний вигляд.

  1.  Графічний метод розв’язування задач лінійного програмування

Завод будівельних конструкцій виготовляє бетонні плити двох видів А та Б. На виготовлення плит витрачається три типи основної сировини.

Скласти план випуску плит заводом, який забезпечує максимальний прибуток. Обмеження на сировину і її витрати на виготовлення 1 плити кожного виду, а також прибуток від реалізації 1 плити задані в таблиці:

Тип

сировини

Витрати на 1 плиту

Запаси сировини

А

Б

Цемент, ц                          

19

26

868

Гравій, ц

16

17

638

Пісок, ц

19

15

853

Прибуток від реалізації продукції

5

4

Побудуємо математичну модель задачі, тобто запишемо вихідну задачу в вигляді певних математичних співвідношень:

х1 – кількість плит виду А

х2 – кількість плит виду Б

Х (х1; х2) – план виготовлення продукції.

При плані Х завод від реалізації плит отримає прибуток

F (х1; х2) = 5 х1 + 4 х2(1)                                                                                   

При цьому плані буде витрачено сировини:

19 х1 + 26 х2 ≤ 868      

16 х1 + 17 х2 ≤ 638       (2)                                                                                    

19 х1 + 15 х2 ≤ 853

Враховуючи зміст змінних х1 та х2 отримаємо обмеження

х1; х2 ≥0  (3)

Математична модель задачі

Знайти найбільше значення функції 1, при обмеженнях 2,3

Функція Х (х1; х2) – функція мети;

х1; х2 – керовані параметри;

коефіцієнти біля х1; х2, функція мети, обмеження задачі – некеровані параметри.

Отримана задача є задачею лінійного програмування, оскільки змінні х1; х2 входять в функцію мети та в обмеження задачі в першому степені.

Алгоритм графічного методу

На площині Х1ОХ2 будуємо багатокутник розв’язків задачі, тобто множину тих точок площини координат, які задовольняють нерівності 2,3

а) будуємо прямі, рівняння яких отримуємо з обмежень 2,3 і шляхом заміни символів нерівності на символ рівність:

19 х1 + 26 х2 =868  (І)

16 х1 + 17 х2 = 638 (ІІ)

19 х1 + 15 х2 = 853 (ІІІ)

х1 = 0

х2 = 0

І. х1=0, х2 =33,4           ІІ. х1=0, х2 =35,5             ІІІ. х1=0, х2 =56,9

х1=47,7; х2 = 0  х1=39,9; х2 = 0 х1=44,9; х2 = 0

б) визначаємо ті площини, які задаються кожною із нерівностей системи обмежень 2,3. Для цього в нерівність підставляємо координати точки  0,0, якщо тримаємо нерівність, яка справджується, це означає, що нерівність визначає ту півплощину на площині, яка обмежена прямою, яка відповідає цій нерівності і містить точку 0. В противному випадку нерівність визначає півплощину, яка не містить точки 0,0.

19 ∙0+ 26 ∙0≤ 868  

0≤ 868      

в) знаходимо спільну частину знайдених півплощин – це і буде багатокутник розв’язків.

2. На площині будуємо вектор С (5;4) – градієнт функції F, який вказує напрямок найшвидшого зростання функції.

С1 = 10С = (50;40)

Будуємо на площині лінію 5х1 + 4х2 = 0 – лінію нульового рівня функції F (проходить через початок координат і перпендикулярна вектору С)

3. Лінію F=0 переміщуємо паралельно самій собі в напрямку вектора С до тих пір, поки не буде знайдена остання спільна точка з багатогранником розв’язків. В цій точці функція досягає свого найбільшого значення. Остання спільна точка К.

4. Знаходимо координати точки максимуму функції, і значення функції в цій точці.

F (D) = 5∙39,9+4∙0 = 199,5

Економічна інтерпретація розв’язку

При плані випуску х1 = 39,9 плит виду А та не випускаючи плит виду Б завод будівельних конструкцій отримає максимальний прибуток 199,5 тис. грн..

  1.  Постановка задач лінійного програмування

При n=2, обмеження задачі лінійного програмування визначається на площині багатокутник розв’язків, які є випуклою множиною (випукла множина – це множина, яка разом з будь-якими двома своїми точками містить відрізок, який їх з’єднує). Цей багатокутник розв’язків може бути точкою, відрізком, променем, багатокутником. Оскільки функція мети лінійна, то вона досягає свого найменшого (найбільшого) значення в одній з вершин цього багатокутника розв’язків (можливо і в нескінченній кількості точок).

Найбільше значення функція мети приймає в кожній точці ВС. Таких точок буде безліч.

Функція мети не досягає свого найбільшого значення на багатокутнику розв’язків .

Задачу лінійного програмування можна розв’язати графічним методом також тоді, коли n-m=2, де n – кількість невідомих, а m – кількість обмежень в задачі лінійного програмування.

Задачу лінійного програмування записану у вигляді 1,2,3 називають розгорнутою формою задачі лінійного програмування.

Запишемо задачу 1,2,3 у векторній формі.

план задачі, С=(5,4)

Задача лінійного програмування у векторній формі: знайти найбільше значення функції F(X)=CX (скалярний добуток векторів), при обмеженнях:

F(X)=CX  (4)

                                                              (5)

                                                                                   (6)

Запишемо задачу лінійного програмування в матричній формі:

C = (5, 4)

Знайти найбільше значення функції F(X)=CX                 (7)

СХ – добуток матриці

                                                                                 (8)

                                                                                      (9)                       

  1.  Симплекс метод розв’язування задач лінійного програмування

Симплекс-метод – коли не можна побудувати багатокутник розв’язків. При розв’язуванні задач лінійного програмування, в яких кількість невідомих більша за три, використовують симплекс-метод – узагальнення графічного методу, за допомогою якого з врахуванням того, що багатокутник розв’язків і в загальному випадку є випуклою множиною можна аналогічно знайти ту вершину багатокутника розв’язків, в якій функція мети досягає найбільшого значення.

Алгоритм симплекс-методу

1. Задачу лінійного програмування записуємо в основній (канонічній) формі:

F (x1; x2) = 5x1+ 4x2                                                             (10)

19x1 + 26x2 ≤868

16x1 + 17x2≤638(11)

19x1 + 15x2 ≤853                                                                                

x1, x2 ≥0                                                              (12)

Для запису задачі лінійного програмування в основній формі вводять додаткові вільні невідомі в обмеження задачі і у функцію мети з нульовими коефіцієнтами. Ці вільні невідомі дають змогу перетворити обмеження задачі з ≤на =.

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

Знайти найбільше значення функції F (x1…x5) = 5 x1+4 x2 +0x3 + 0x4 + 0x5, при обмеженнях:

19 x1 + 26 x2+ х3=868

16 x1 + 17 x2+     х4=638

19 x1 + 15 x2+          х5=853

x1, x2 , x3 , x4 , x5 ≥0

З врахуванням умов задачі вільні невідомі мають певний економічний зміст:

х3 – залишки цементу;

х4 – залишки гравію;

х5 – залишки піску, при виконаному плані випуску плит.

Запишемо задачу 10, 11,12 в векторній формі:

Х = (х1, х2, х3, х4, х5)                            С = (5, 4, 0, 0, 0)

А1А2А3А4А5

Задача 10-12 в векторній формі:

Знайти найбільше значення функції F(X) = CX,                         (13)

при обмеженнях

х1А1 + х2А23А3 + х4А4 + х5А5 = А0 (14)

х ≥0                                                                                               (15)

Рівність 14 – це розклад вектора А0 за векторами А1, А2, А3, А4, А5, або – це представлення вектора А0у вигляді лінійної комбінації А1 – А5

Вектори А3, А4, А5 мають три координати, при чому одна з них =1, а решта 0. Такі вектори утворюють базис в просторі R3.

Планом задачі 13-15 називається вектор Х з координатами  х15, координати якого задовольняють обмеження 14,15.

План задачі Х(х15) називають опорним, якщо система векторів, які входять в розклад вектора А0 із додатними коефіцієнтами є лінійно незалежною.

Оскільки кожен з векторів Аі, і = має три координати, то опорний план задачі 13-15 може містити не більше як три додатні координати.

Опорний план задачі 13-15 називається не виродженим, якщо він містить рівно три додатні координати. Якщо в опорному плані кількість додатних координат менша за 3, то такий план задачі називається виродженим.

Ідея симплекс методу

1. Із відомого (знайденого) опорного не виродженого плану за допомогою алгоритму за скінченну кількість кроків знаходять розв’язок задачі лінійного програмування або встановлюють, що задача не має розв’язку. На кожному кроці знаходять новий опорний план задачі на якому значення функції мети не менше ніж на попередньому опорному плані.

2. Знаходять початковий опорний не вироджений план задачі і значення функції мети на ньому

=(0,0,868,638,853)

F () = 5∙0+4∙0+868∙0+638∙0+853∙0=0

План Х() - опорний і не вироджений, оскільки він містить три додатних координати, при чому в розкладі 14 їм відповідають вектори А3, А4, А5, які лінійно незалежні і утворюють базис простору R3.

Перевтілюють вибраний план на оптимальний: для цього заповнюють симплекс таблицю:

Базис

С базису

А0

А1

А2

А3

А4

А5

Өij

С1 =5

С2 =4

С3=0

С4=0

С5=0

1

А3

0

868

19

29

1

0

0

45,7

2

А4

0

638

16

17

0

1

0

39,9

3

А5

0

853

19

15

0

0

1

44,9

4

0

-5

-4

0

0

0

Критерії оптимального плану

3. Вибраний план є оптимальним, якщо останній рядок таблиці не містить від’ємних чисел. План Х0 не є оптимальним, бо є -5 і -4.

4. Будуючи нову симплекс таблицю:

А) знаходять спрямовуючий стовпчик – серед елементів останнього рядка вибирають найменший і стовпчик і якому він розміщений відмічають стрілочкою.

Б) знаходять спрямовуючий рядок. Елементи стовпчика A0 ділять на відповідні додатні елементи спрямовуючого стовпчика і серед отриманих часток знаходять найменшу, рядок до якого вона відноситься відмічають стрілочкою.

В) знаходять головний елемент – елемент таблиці, який знаходиться на перетині спрямовуючого стовпчика і рядка, його беруть в рамочку.

Базис

С базису

А0

А1

А2

А3

А4

А5

Өij

С1 =5

С2 =4

С3=0

С4=0

С5=0

1

А3

0

110,38

0

5,81

1

-1,19

0

2

А1

5

39,9

1

1,06

0

0,0625

0

3

А5

0

95,38

0

-5,19

0

-1,19

1

4

199,38

0

1,31

0

0,31

0

Г) із базису виводять вектор спрямовуючого рядка, замість нього вводять вектор спрямовуючого стовпчика.

Ґ) елементи спрямовуючого рядка ділять на головний елемент і результат записують у вигляді нової симплекс таблиці.

Д) всі інші елементи в спрямовуючому стовпчику в новій таблиці замінюють нулем.

Е) решту елементів нової симплекс таблиці знаходять за правилом прямокутника.

В останньому рядку нової симплекс таблиці немає від’ємних значень, отже даний план є оптимальним.

5. Виписують новий опорний план задачі і значення функції мети на ньому:

F () = 5∙39,9=199,5

Економічна інтерпретація розв’язку

При плані випуску х1=3,91 т. карамелі сорту А та х2=1,74 т. карамелі Б, кондитерська фабрика отримає максимальний прибуток F () = 265,2 тис. грн., при цьому плані випуску карамелі залишиться невикористаними х3=3,48т. цукру, а патока і фруктове пюре будуть використані повністю, так як х4 та х5 дорівнюють 0.

Зауваження:

1. Якщо в останньому рядку таблиці є від’ємний елемент і всі інші елементи цього стовпчика не додатні – тоді задача лінійного програмування немає розв’язку, тобто функція F(Х) не приймає свого найбільшого значення.

2. Якщо в останньому рядку таблиці є декілька однакових найменших значень, тоді до спрямовуючого стовпчика вибирають той, для якого значення функції мети найбільше  .

Знайти найбільше значення функції(16)

при обмеженнях:

                                                                              (17)

- називають планом задачі (16) – (18), якщо його координати задовольняють обмеження (17) – (18).

- називають оптимальним планом, якщо для будь-якого плану Х виконується нерівність

Зауваження:

1. В обмеженнях (17) в випадку деякі з них, а можливо і всі можуть мати вигляд нерівностей.

2. В обмеженнях (18) деякі змінні можуть бути відсутні – це означає, що вони можуть приймати довільні, дійсні значення, деякі змінні можуть приймати обмеження, які мають вигляд інтервалів, тобто вказані межі зміни взаємовідповідних змінних, крім того на змінні можуть накладатися умови або їх цілочисельності, або їх натуральності.

3. Якщо потрібно знайти найменше значення функції z, то тоді можна розглянути функцію , яка дорівняє –z, знайти її найбільше значення, а найменше значення функції z знаходиться за формулою

Двоїстість в лінійному програмуванні

  1.  Постановка двоїстої задачі
  2.  Алгоритм двоїстого симплекс-методу

1. Постановка двоїстої задачі

При розв’язуванні задач іноді зручно поряд  із вихідною задачею розглядати, так звану, двоїсту до неї задачу. Умови двоїстої задачі отримують з умов вихідної задачі за певними правилами. При цьому двоїсту задачу формують так, що знайшовши її розв’язок за певними правилами, можна було б отримати розв’язок вихідної задачі. Розглянемо принцип двоїстості на прикладі задачі лінійного програмування.

Нехай маємо задачу лінійного програмування (16) - (18), двоїстою буде наступна задача лінійного програмування: знайти найменше значення функції                                        (19)

при обмеженнях:

                                                                          (20)

                                                                                                                 (21)

Задачі лінійного програмування (16) – (18) та (19) – (21) називають систематичними двоїстими (обмеження мають вигляд нерівностей).

Підтвердження: якщо задача лінійного програмування (16) – (18) має розв’язок, тоді і двоїста задача (19) – (21) також має розв’язок, причому  і навпаки.

Зауваження:

1. Записане вище твердження називають принципом двоїстості в лінійному програмуванні. На практиці знаходять розв’язок тієї задачі, яку можна розв’язати.

2. Двоїстою до задачі лінійного програмування (19) – (21) є задачі лінійного програмування (16) – (18).

  1.  Алгоритм двоїстого симплекс-методу

Сформулювати двоїсту задачу лінійного програмування, знайти найбільше значення функції F (x1; x2) = 5x1+4x2, при обмеженнях

19x1 + 26x2

16x1 + 17x2

19x1 + 15x2

Двоїстою буде наступна задача: знайти найменше значення функції

z = (y1, y2, y3) = 868 y1 +638 y2 +853 y3 (22),

при обмеженнях

19y1+ 16y2 +19y3  (23)

26y1+17y2 +15y3

y1, y2, y3       (24)

Знаходимо розв’язок двоїстої задачі ( 22) – (24). Оскільки в даній задачі потрібно знайти мінімум функції, то перейдемо до задачі лінійного програмування знаходження максимального значення функції, розглянемо функцію F1 = – zі отримаємо наступну задачу лінійного програмування: знайти найбільше значення функції F1 = -z = -868 y1 -638 y2 -853 y3 (25),                                                         

при обмеженнях

-19y1- 16y2 -19y3 (26)

-26y1-17y2 -15y3

y1, y2, y3  (27)

Будемо розв’язувати задачу (25) – (27) аналогічно, як ми розв’язували задачу лінійного програмування на знаходження максимуму функції, для цього в обмеження задачі і в функцію мети введемо вільні невідомі у4, у5, нерівності 26 перетворимо в рівності, тоді отримаємо наступну задачу: знайти найбільше значення функції

F1 =  (28),                      

при обмеженнях

-19y1- 16y2 -19y3 4    (29)

-26y1-17y2 -15y3 5

y1, y2, y3, y4, y5  (30)

Отримаємо задачу лінійного програмування (28) – (30) записану в основній (канонічній) формі.

Якщо взяти вектор , то його координати є розв’язком системи (29), але він не є оптимальним планом задачі, так як

y4, y5

Запишемо цю систему обмежень 29 в векторній формі:

,

тоді 29 матиме вигляд:

у1А1 + у2А2 3А3 + у4А4 + у5А5 = А0  (31)

Вектор Y=(у1,у2, у3, у4, у5)називають псевдо планом задачі, якщо вектори, які входять в розклад 31 і відповідають не нульовим значенням координат цього вектора є лінійно незалежними (одиничними). Кожен з векторів має дві координати, тому в псевдоплані задачі може бути не більше двох не нульових елементів. Псевдопланом задачі називають невиродженим, якщо він містить рівно дві координати.

Суть двоїстого симплекс методу: із відомого невиродженого псевдо плану задачі за скінченне число кроків, знаходимо розв’язок задачі лінійного програмування або встановлюють, що вона не має розв’язку.

Алгоритм двоїстого симплекс-методу

1. Знаходимо псевдо план задачі лінійного програмування і значення функції мети на ньому:

Вибраний псевдо план перевіряють на оптимальність. Для цього заповняють симплекс таблицю:

Базис

С базису

А0

А1

А2

А3

А4

А5

С1 =

-868

С2 =

-638

С3=

-853

С4=

0

С5=

0

1

А4

0

-5

-19

-16

-19

1

0

2

А5

0

-4

-26

-17

-15

0

1

3

0

868

638

853

0

0

2. Критерій оптимальності: якщо в стовпчику А0, за виключенням останнього елемента немає від’ємних чисел, то вибраний псевдоплан є оптимальним. Оскільки в А0 є від’ємні числа, то псевдоплан

3. Заповнюємо нову симплекс-таблицю:

а) знаходимо спрямовуючий рядок. Серед від’ємних елементів вектора А0знаходимо найменший, рядок в якому він розміщений позначаємо стрілочкою.

б) знаходимо спрямовуючий стовпчик. Елементи останнього рядка в таблиці ділимо на відповідні від’ємні елементи спрямовуючого рядка і серед оптимальних часток знаходимо найбільшу. Стовпчик до якого вона досягається відмічаємо стрілочкою.

в) знаходимо головний елемент, його відмічають рамкою

г) заповнення нової симплекс таблиці здійснюють аналогічно як в симплекс-методі.

Базис

С базису

А0

А1

А2

А3

А4

А5

С1 =

-868

С2 =

-638

С3=

-853

С4=

0

С5=

0

1

А2

-638

0,31

1,19

1

1,19

-0,06

0

2

А5

0

1,31

-5,81

0,81

5,19

-1,06

1

3

-199,38

110,38

-374,94

95,38

39,88

0,00

4. Записуємо отриманий псевдоплан задачі і значення функції мети на ньому

Оскільки стовпчик А0 не містить від’ємних чисел, то вибраний псевдо план є оптимальним. Отже, функція  досягає свого найбільшого значення на плані .

Розв’язок двоїстої задачі:

Функція z досягає свого найменшого значення на плані  при чому minz = – max = –199,38.

Найбільше значення функції мети F вихідної задачі, також рівне 199,38 і найменше значення функції z двоїстої задачі також рівне 199,38, тобто maxF=minz=199,38.

Зауваження:

Найбільше значення функції мети F – вихідної задачі функції лінійного програмування 199,38.і найменше значення функції двоїстої задачі, також рівна 199,38, тобто  = 199,38.

Економічна інтерпретація розв’язку двоїстої задачі:

1 економічна інтерпретація

Змінна у1 відповідає вартості (ціні) 1 т. цукру, у2 – вартість 1 т. патоки, у3 – вартість 1 т. фруктового пюре. Оскільки прибуток від реалізації однієї тони карамелі А і В виражається в тис. грн., величини у1, у2, у3 також вимірюються в тис. грн..

Функція z виражає вартість всієї сировини, величина 2y1+ 8y2 +5y3 означає вартість сировини, яка витрачається на виготовлення 1 т. карамелі сорту А, 5y1+5y2 +6y3 – вартість сировини, яка витрачається на виготовлення 1 т. карамелі сорту Б, величина у4 відповідає різниці між вартістю сировини, яка витрачається на випуск 1 т. карамелі виду А та прибутком від реалізації 1 т. карамелі сорту А, у5 – різниця між вартістю сировини, яка витрачається на випуск 1 т. карамелісорту Б та прибутком від реалізації 1 т. карамелі виду Б.

Вартість 1 т. цукруy1 =0 тис. грн., вартість 1 т. патокиу2 – 4,35 тис. грн., вартість 1 т. фруктового пюре у3 – 3,043 тис. грн., витрати на закупівлю сировини при оптимальному випуску будуть найменшими і становитимуть 265,1тис. грн..

При цьому вартість сировини, яка витрачається на випуск 1 т. карамелі сортів А і Б буде рівною прибутку від реалізації 1 т. карамелі кожного сорту, оскільки y4таy5дорівнюють 0.

Зауваження:

1. Якщо  – це означає, що вартість сировини, яка витрачається на випуск 1 т. карамелі сорту А більша за прибуток від реалізації, тобто оптимальний план випуску карамелі не передбачає випуск карамелі сорту А. Аналогічно і з сортом Б.

2. Оскільки y1=0, тобто вартість цукру дорівнює 0, то вважається, що цукор не є дефіцитною сировиною, тому при оптимальному плані випуску вони використовуються не повністю.

2 економічна інтерпретація

Конкурентна фабрика вирішила закупити всю сировину у кондитерської фабрики, при цьому потрібно знайти оптимальні ціни за одиницю сировини з врахуванням наступних двох умов:

  1.  Організація прагне мінімізувати загальну вартість сировини;
  2.  Кондитерська фабрика бажає отримати за сировини суму коштів, яка не менша за прибуток, який вона отримає при оптимальному випуску карамелей.

При продажі конкурентній організації кондитерською фабрикою патоки по ціні 4,35 тис. грн. за 1 т. і фруктового пюре по ціні 3,045 тис. грн.. за 1 т., кондитерська фабрика отримає 261,5 тис .грн., тобто рівно стільки, скільки б вона отримала прибутку, при оптимальному випуску карамелей, при цьому цукор вона продасть безкоштовно.

Зауваження:  із симплекс-таблиці з якої отримано оптимальний план двоїстої задачі можна отримати оптимальний план вихідної задачі. Для цього потрібно розглянути її останній рядок:

при цьому вважають, що в останньому рядку записані координати в наступному порядку х3, х4, х5, х1, х2. Із останньої симплекс-таблиці отриманої симплекс-методом, отримають оптимальний план двоїстої задачі, якщо елементи останнього рядка вважати координатами оптимального плану двоїстої задачі і записану у вигляду у4, у5, у1, у2, у3.

При розв’язуванні задач лінійного програмування двоїстим симплекс-методом мають місце ті самі зауваження, що і до симплекс-методу із врахуванням двоїстості.

Цілочисельне програмування

  1.  Постановка задачі цілочисельного програмування
  2.  Приклади задач цілочисельного програмування
  3.  Розв’язування задач цілочисельного програмування методом Гоморі

  1.  Постановка задачі цілочисельного програмування

До цілочисельного програмування належать задачі математичного програмування, в яких шукані змінні (керовані параметри) приймають тільки цілочисельні значення. Розглянемо постановку задачі цілочисельного програмування.

Знайти найбільше (найменше) значення функції F(x1xn)=c1x1+c2x2+…+cnxn                                                (1),     при обмеженнях

(2)

                                                              (3)

– один з символів

Зауваження: якщо серед змінних  тільки частина набуває значення , тоді відповідну задачу лінійного програмування називають частково цілочисельною. Серед задач цілочисельного програмування важливу роль відіграє клас задач, в яких змінні набувають лише одне з двох значень 0 або 1, такі змінні називають бінарними або булевими.

На відмінну від задач лінійного програмування в задачах цілочисельного програмування багатокутник розв’язків є дискретною (точковою) множиною. Якщо цей многокутник є обмеженою множиною, кількість планів в задачі цілочисельного програмування є скінченною. Для знаходження оптимального плану задачі потрібно серед скінченної кількості планів вибрати (знайти) той, на якому функція мети досягає свого найбільшого значення.

Графік

ОАВСD – багатокутник розв’язків задачі лінійного програмування, яка відповідає задачі цілочисельного програмування без врахування цілочисельності змінних.

Допустимими планами (розв’язками) будуть ті точки багатокутника ОАВСD, які мають цілочисельні координати.

Розв’язок задачі лінійного програмування – розв’язок функції мети в точці В. Точка В має нецілочисельні координати, тому вона не є планом задачі цілочисельного програмування. Можливими точками, в яких функція мети задачі цілочисельного програмування досягає свого найбільшого значення є одна із точок 1,2,3.  

  1.  Приклади задач цілочисельного програмування

Задача про закупівлю обладнання

Нехай для купівлі обладнання підприємство виділило 20 млн. грн.. Потрібно купити обладнання двох типів А та Б. Вартість одиниці обладнання А 5 млн. грн., площа, яку займає 8 м2, продуктивність складає 7 тис. одиниць продукції за зміну.

Вартість одиниці обладнання Б 2 млн. грн., площа, яку займає 5 м2, продуктивність складає 4 тис. одиниць продукції за зміну.

Для розміщення обладнання фірма може використати приміщення площею 40 м2. Потрібно знайти оптимальний варіант закупівлі обладнання, який забезпечує максимальну продуктивність за зміну.

Сформулюємо математичну модель задачі:

Нехай х1 – кількість одиниць обладнання А

х1 – кількість одиниць обладнання Б, які планує закупити фірма.

Тоді при плані закупівлі обладнання Х=(х1, х2) його продуктивність за зміну буде рівна F1, х2) = (7х1, 4х2)                                                         (4)

Вартість обладнання складає 5х1+2х2 , а площа, яку воно буде займати 8х1+5х2. Враховуючи обмежену кількість фінансів та площі, отримаємо обмеження

1+2х2

1+5х2                                                                                                (5)

Оскільки х1, х2 – кількість одиниць обладнання, то змінні х1, х2 задовольняють умову:

х1, х2                                                                                    (6)

Отже, математична модель задачі: знайти найбільше значення функції (4), при обмеженнях (5), (6). Отримана задача є задачею цілочисельного програмування.

Задача про розподіл (призначення)

До такого класу задач належать задачі про розподіл робітників за певними видами робіт, про розподіл екіпажів за рейсами, при призначення працівників на певні посади.

Нехай на заводі працюють n робітників, кожен з яких може виконувати n робіт, при чому використання i-го робітника на j-ій роботі приносить прибуток cij. Потрібно доручити кожному із робітників виконання однієї цілком визначеної роботи, так щоб отримати максимальний прибуток.

Побудуємо математичну модель задачі. Позначимо через хij змінну, яка означає виконані і-им робітником j-ої роботи.

Роботи

Робітники

1

2

n

1

c11

x11

c12

x12

c1n

x1n

2

c21

x21

c22

x22

c2n

x2n

n

cn1

xn1

cn2

xn2

cnn

xnn

Прибуток від виконання робіт буде рівний F= c11x11+ c12x12+…+c1nx1n+ c21x21+c22x22+…+c2nx2n+cn1xn1+cn2xn2+…+cnnxnn

Умова виконання кожним робітником однієї роботи запишеться у вигляді

                                                     (8)

Умова виконання кожної роботи одним робітником матиме вигляд

    (9)

Враховуючи зміст змінних , ,                                 (10)

Математична модель задачі: знайти найбільше значення функції (7), при обмеженнях (8), (9), (10).

Задача про туриста

Нехай маємо n місць, які пронумеровані від 1 до n. Турист виїдаючи з міста 1 повинен побувати в кожному місті один раз і повернутися назад в це місто. Відомі відстані cijміж іта j містом. Потрібно знайти найкоротший маршрут для туриста

Побудуємо математичну модель задачі:

місто

місто

1

2

n

1

0

c12

x12

c1n

x1n

2

c21

x21

0

c2n

x2n

n

cn1

xn1

cn2

xn2

0

,

– величина, яка відповідає тому, що маршрут передбачає переїзд з і в j місто. Величини  приймають значення 0, якщо вибраний маршрут не передбачає переїзд з і в j місто і дорівнюють 1 в противному випадку.

=0, тоді загальна довжина маршруту буде рівною

В кожному рядку таблиці, всі елементи, крім одного дорівнюють 0, а один елемент дорівнює 1. Аналогічно і для кожного стовпчика.

Умова виїзду з кожного міста запишеться у вигляді:

Умова в’їзду в кожне місто має вигляд:

Змінні

Отже математична модель задачі про туриста: знайти найменше значення функції F, при записаних вище обмеженнях.

Зауваження: до обмежень задачі про туриста можуть додаватися різні додаткові умови, наприклад, умова про існування нерозривних маршрутів, умови відвідування міст в певній послідовності ті інші.       

3. Розв’язування задач цілочисельного програмування методом Гоморі

При розв’язуванні задач цілочисельного програмування, використовують спеціальні методи, які враховують цілочисельність змінних. Ці методи можна розбити на два напрями:

  1.  Метод відтинаючих площин (метод Гоморі)
  2.  Комбінаторні методи

Суть методів відтинаючих площин полягає в наступному. Спочатку знаходять оптимальний план задачі без врахування цілочисельності змінних. Потім записують додаткові обмеження для нецілочисельних координат оптимального плану. Отримують нову задачу лінійного програмування, розв’язок якої знаходять двоїстим симплекс-методом.

Суть комбінаторних методів полягає в переборі всіх допустимих цілочисельних планів задачі, однак цей перебір здійснюють ціле направлено тільки для невеликої частини таких планів.

Основними комбінаторними методами є методи гілок та меж.

Розглянемо метод Гоморі.

Алгоритм методу Гоморі

1. Симплекс-методом знаходимо оптимальний план задачі. Якщо він містить дробові компоненти переходимо до наступного кроку.

Базис

Сбазису

А0

А1

А2

А3

А4

А5

С1=5

С2=4

С3=0

С4=0

С5=0

1

А3

0

110,375

0,000

8,813

1,000

-1,188

0,000

2

А1

5

39,875

1,000

1,063

0,000

0,063

0,000

3

А5

0

95,375

0,000

-5,188

0,000

-1,188

1,000

4

199,375

0,000

1,313

0,000

0,313

0,000

2. Серед дробових компонентів знаходять компоненту з найбільшою дробовою частиною:

=0,375

=0,875

=0,375

3. На базі останньої симплекс-таблиці для знайденої компоненти по елементах відповідного рядку в таблиці будують додаткове обмеження у вигляді:

4. Додаткове обмеження шляхом введення довільної змінної перетворює нерівність в рівність

5. Додаткове обмеження вводять в симплекс-таблицю і шляхом доповнення її одним рядком і стовпчиком.

Базис

Сбазису

А0

А1

А2

А3

А4

А5

А6

С1=5

С2=4

С3=0

С4=0

С5=0

С6=0

1

А3

0

110 3/8

0

8 4/5

1

-1 1/5

0

0

2

А1

5

39 7/8

1

1

0

0

0

0

3

А5

0

95 3/8

0

-5 1/5

0

-1 1/5

1

0

4

А6

0

- 7/8

0

-0

0

-0

0

1

5

199 3/8

0

1 1/3

0

1/3

0

0

6. Отриману задачу розв’язуємо двоїстим симплекс-методом.

Базис

Сбазису

А0

А1

А2

А3

А4

А5

А6

С1=5

С2=4

С3=0

С4=0

С5=0

С6=0

1

А3

0

126 7/8

0

10

1

0

0

-18 6/7

2

А1

5

39

1

1

0

0

0

1

3

А5

0

111 7/8

0

-4

0

0

1

-18 6/7

4

А4

0

13 8/9

0

1

0

1

0

15 7/8

5

195,028

0

1

0

0

0

5

7. Повертаємось до пункту 2.

8. Додаткове обмеження шляхом введення довільної змінної перетворюють нерівність в рівність

Базис

Сбазису

А0

А1

А2

А3

А4

А5

А6

А7

С1=5

С2=4

С3=0

С4=0

С5=0

С6=0

С7=0

1

А3

0

126 7/8

0

10

1

0

0

-18 6/7

126 7/8

2

А1

5

39

1

1

0

0

0

1

39

3

А5

0

111 7/8

0

-4

0

0

1

-18 6/7

111 7/8

4

А4

0

13 8/9

0

1

0

1

0

-15 7/8

13 8/9

5

А7

0

- 8/9

0

0

0

0

0

- 7/8

1

6

195,028

195

0

1

0

0

0   

5

  1.  Отриману задачу розв’язуємо двоїстим симплекс-методом.

Базис

Сбазису

А0

А1

А2

А3

А4

А5

А6

А7

С1=5

С2=4

С3=0

С4=0

С5=0

С6=0

С7=0

1

А3

0

146

0

10

1

0

0

0

105 2/7

2

А1

5

38

1

1

0

0

0

0

40 1/7

3

А5

0

131

0

-4

0

0

1

0

90 2/7

4

А4

0

30

0

1

0

1

0

0

-4 2/7

5

А7

0

1

0

0

0

0

0

1

-1 1/7

6

190

0

1

0

0

0

0

200 5/7

Економічна інтерпретація розв’язку

При плані випуску х1 = з8 плин виду А та не випускаючи плит виду В, так як х2 = 0, завод отримає максимальний прибуток F=190 тис. рн...

Зауваження: методом Гоморі виконують тільки два кроки.

Транспортна задача

1. Постановка транспортної задачі. Приклад

2. Методи вибору (знаходження) опорних планів транспортної задачі:

а) метод північно-західного кута

б) метод мінімальної вартості

в) метод подвійної переваги

3. Розв’язування транспортної задачі методом потенціалів

1. Постановка транспортної задачі. Приклад

В загальному транспортна задача полягає в знаходженні оптимального плану перевезення (доставки) продукції від постачальників (виробників) до споживачів.

Критерій оптимальності в таких задачах може бути: мінімальна вартість перевезення, мінімальний маршрут доставки, мінімальний час доставки та інше.

Загальна постановка транспортної задачі: нехай деяка однорідна продукція знаходиться в m пунктах постачання Аів кількості аі одиниць в кожному. Потреби в цій продукції n споживачів Bjскладають відповідно bjодиниць кожного. Відомі вартості перевезення cijодиниці продукції від і-го постачальника до j-го споживача. Потрібно скласти план доставки продукції від постачальників до споживачів, який дозволяє вивести всю продукцію від постачальників, задовольнити повністю потреби всіх споживачів і який має найменшу вартість.

Побудуємо математичну модель задачі:

Постачальники

Споживачі

Запаси

c11

x11

c12

x12

c1n

x1n

c21

x21

c22

x22

c2n

x2n

cm1

xm1

cm2

xm2

cmn

xmn

Потреби

Позначимо через  кількість одиниць продукції, які планується перевозити від і-го постачальника до j-го споживача. Тоді вартість доставки (перевезення) продукції буде рівна:                                                                  (1)

Умови вивезення продукції від постачальників матимуть вигляд:

                                            (2)

Умови задоволення потреб всіх споживачів мають вигляд:

                                             (3)

Враховуючи зміст змінних , дістанемо обмеження:

,                                                                  (4)

Математична модель задачі: знайти найменше значення функції (1), при обмеженнях (2), (3), (4).

Зауваження: задача 1-4 є задачею лінійного програмування, оскільки змінні  у функцію мети та в обмеження задачі входять у першому степені.

Будемо вважати, що сумарні запаси співпадають із загальними потребами в ній, тобто має місце рівність:                                                                      (5)

Отримана транспортна задача 1-5 називається закритою транспортною задачею. Якщо умова задачі 1-5 не виконується, тобто сумарні запаси не співпадають з загальними потребами продукції, то така транспортна задача називається відкритою.

Твердження: кожна закрита транспортна задача має розв’язок.

Якщо сумарні запаси більші від загальних потреб, тобто:

Тоді відкриту транспортну задачу зводять до закритої наступним чином, вводять фіктивного споживача , вважаючи, що його потреби в продукції складають

а вартості перевезення одиниці продукції від постачальників будуть рівними 0. Тобто,

Якщо загальні потреби більші від сумарних запасів продукції, тобто

Тоді вводять фіктивного постачальника , вважають запаси продукції в нього складають

одиниць продукції від нього до споживачів будуть рівними 0.

Тобто,

Планом транспортної задачі є матриця:

Якщо транспортна задача закрита, то з врахуванням умови (5) ми отримаємо, що кількість лінійно незалежних рівнянь в умовах (2), (3) буде рівна m+n–1, тому опорний план транспортної задачі може містити не більше ніж m+n–1відмінних від 0 елементів.

Опорний не вироджений план транспортної задачі містить рівно m+n–1 відмінних від 0 елементів.

Якщо m=n=10 план задачі містить 100 елементів, а в опорному плані відмінних від 0 не більше 19, опорний не вироджений план містить рівно 19 відмінних від 0, а всі інші 81 елемент дорівнюють 0.

Приклад

Нехай умова задачі задана у вигляді таблиці:

Постачаль-ники

Споживачі

Запаси

17

4

18

6

0

11

11

12

6

11

0

41

8

3

5

7

0

96

Потреби

58

30

46

13

1

148

Перевіримо задача ну закритість:

Транспортна задача відкрита. Вводимо фіктивного споживача, із потребами продукції 148-147=1, вартості перевезення одиниці продукції вважаємо рівними 0.

Побудуємо математичну модель задачі. Позначимо через  – кількість одиниць продукції, які планується перевозити від постачальника до споживача. При такому плані перевезення її вартість становитиме:

(6)

Умови вивезення продукції постачальникам мають вигляд:

                           (7)

Умови задоволення потреб споживачів мають вигляд:

                                                         (8)

Дістанемо обмеження, враховуючи зміст змінних

                                                       (9)

Математична модель задачі: знайти найменше значення функції 6, при обмеженнях 7,8,9.

План задачі – матриця розміру 3 на 5, який містить 15 елементів. В опорному плані задачі може бути не більше 3+5-1=7, відмінних від 0 елементів. Опорний не вироджений план задачі містить рівно 7 відмінних від 0 елементів, а решта вісім дорівнюють 0.

Метод північно-західного кута

Ідея методу: на кожному кроці заповнюють верхню ліву клітинку таблиці із врахуванням наявних запасів продукції у постачальників і потреб в ній у споживача. Якщо запаси постачальника використані повністю, то у наступному кроці відповідний рядок таблиці виключаємо з розгляду. Аналогічно, якщо потреби споживача задоволені повністю, то виключаємо на наступному кроці відповідний стовпчик. Виключені з розгляду рядки і стовпчики відмічаємо.

Постачаль-ники

Споживачі

Запаси

11

0

0

0

0

11

41

0

0

0

0

41

6

30

46

13

1

96

Потреби

58

30

46

13

1

148

План, отриманий методом північно-західного кута:

Оскільки в плані  7 не нульових координат, то він є опорним не виродженим планом задачі. Вартість перевезення продукції при цьому плані:

F (

Метод мінімальної вартості

Суть методу: на кожному кроці заповнюємо клітинку таблиці з найменшою вартістю перевезення одиниці продукції із врахуванням наявних запасів і потреб.

Якщо клітинок з найменшою вартістю кілька, то заповнюють ту клітинку таблиці, яку можна записати найбільшу поставку продукції:

Постачаль-ники

Споживачі

Запаси

0

0

0

11

0

11

41

0

0

0

0

41

17

30

46

2

1

96

Потреби

58

30

46

13

1

148

Оскільки в плані  7 не нульових координат, то він є опорним не виродженим планом задачі. Вартість перевезення продукції при цьому плані:

F (

Метод подвійної переваги

Ідея методу: в кожному рядку таблиці знаходять клітинку (клітинки) з найменшою вартістю перевезення і відмічаємо її *. Аналогічно робимо в кожному стовпчику таблички. Спочатку заповнюємо клітинки, які відмічені двома символами, потім одним, потім з найменшими вартостями перевезення. Якщо декілька клітинок відмічені двома символами, то заповнюємо ту з них, в яку можна записати максимальну кількість продукції.

Постачаль-ники

Споживачі

Запаси

0

0*

0

11*

0

11

0

0

41*

0

0

41

58*

30**

5*

2

1

96

Потреби

58

30

46

13

1

148

Оскільки в плані  7 не нульових координат, то він є опорним не виродженим планом задачі. Вартість перевезення продукції при цьому плані:

F (

Для перевірки на оптимальність знайденого опорного плану використовують різні методи, розглянемо метод потенціалів.

Метод потенціалів

1. Вибираємо опорний не вироджений план задачі, знайдений одним із методів і значення функції F на ньому. Вибираємо .

2. Перевіряємо вибраний план на оптимальність:

а) Обираємо для постачальників потенціал , а для споживачів . Потенціалам можна надати наступний зміст: – вартість одиниці продукції в -го постачальника, а  - вартість поставленої одиниці продукції в -го споживача.

Постачаль-ники

Споживачі

Запаси

0

0

0

11

0

11

41-

0

0+

0

0

41

17+

30

46-

2

1

96

Потреби

58

30

46

13

1

148

б) Записуємо систему рівнянь для знаходження невідомих потенціалів. Кожна рівняння системи має вигляд: , при чому ці рівняння записують тільки для заповнених клітинок таблиці.

в) Знаходимо із системи рівнянь значення потенціалів. Система містить 7 рівнянь і 8 невідомих, тобто має безліч розв’язків. Для знаходження одного з них вибираємо потенціал, який найбільш часто зустрічається і прирівнюємо його до 0. .

г) перевіряємо умову оптимальності плану: план є оптимальним, якщо для незаповнених клітинок таблиці виконується нерівність:  

3. Вибираємо клітинку для перерозподілу продукції – клітинку, для якої досягається найменше значення , її відмічають +.

4. Будуємо цикл перерозподілу продукції. Цикл перерозподілу – замкнута ламана, яка задовольняє умовам. Одна з вершин ламаної знаходиться в клітинці зі знаком +, а всі інші вершини знаходяться в заповнених клітинках. В кожному рядку і стовпчику таблиці міститься або дві або жодної вершини ламаної.

5. Знаходимо кількість одиниць продукції для перерозподілу – вершини ламаної почергово відмічаємо символами + та – і серед чисел зі знаком – вибираємо найменше.

6. Здійснюємо перерозподіл продукції – від чисел зі знаком мінус віднімаємо, до чисел зі знаком плюс додають кількість одиниць продукції для перерозподілу.

Постачаль-ники

Споживачі

Запаси

0

0

0

11

0

11

41-

0

0+

0

0

41

17+

30

46-

2

1

96

Потреби

58

30

46

13

1

148

Постачаль-ники

Споживачі

Запаси

0

0

0

11

0

11

0

0

41

0

0

41

58

30

5

2

1

96

Потреби

58

30

46

13

1

148

7. Записуємо отриманий план, і знаходимо значення функції F на ньому.

 

F() = 910

Економічна інтерпретація розв’язку

При перевезенні 58 одиниці продукції від 3 постачальника до 1 споживача, 41 одиницю продукції від 2 постачальника до 3 споживача, 11 одиниці від 1 постачальника до 4 споживача та 30, 5, 2 одиниці продукції від 3 постачальника відповідно до 2,3,4 споживачів вартість перевезення буде найменшою і становитиме 905 грн. При цьому у 3 постачальника залишиться 1 одиниця продукції.


 

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

32155. Переход от стратегического планирования к стратегическому менеджменту 36.5 KB
  Переход от стратегического планирования к стратегическому менеджменту Предшественником стратегического планирования была система долгосрочного планирования longrnge plnning. В арсенал новых методов используемых стратегическим планированием входят: модели анализа инвестиционных портфелей компаний разработка ситуационных планов развития применение сценарного планирования использование систем экспертных оценок применение различных аналитических матриц для исследования альтернатив возможного стратегического развития и т. Некоторые...
32156. Модели стратегического менеджмента 27 KB
  Модели стратегического менеджмента Одно из классических образных представлений о стратегическом мышлении в отличие от других видов мышления сделано К. В соответствии с моделью укрупненными являются следующие три этапа или фазы стратегического цикла организации: 1 стратегический анализ; 2 разработка стратегии стратегический синтезразвитие; 3 реализация стратегии. Отметим что рассматриваемая модель характеризует стратегическое управление организации и как органичную систему. В рамках предлагаемой модели стратегический...
32157. Анализ внешней среды организации. SWOT-анализ и PEST 38 KB
  Анализ внешней среды организации. К особенностям целевого SWOТ анализа при исследовании внешней среды организации относятся следующие. Вовторых анализ сильных и слабых сторон организации на втором этапе желательно увязывать с соответствующими результатами которые были выявлены и зафиксированы на первом этапе. Но и ценность любого тщательно просчитанного оптимального решения если оно появляется слишком поздно становится равной нулю На основании последовательного рассмотрения этих факторов принимаются решения по корректировке целей и...
32158. Анализ внутренней среды организации. SNW-анализ 26.5 KB
  Анализ внутренней среды организации. SNWанализ Исследование внутренней среды организации как части стратегического анализа представляет отдельный блок. Анализ внутренней среды организации осуществляемый во имя ее стратегических целей так же как и стратегический анализ внешней среды должен быть системным и многофакторным. При стратегическом анализе вся внутренняя среда организации и ее отдельные подсистемы и компоненты рассматриваются как стратегический ресурс развития организации.
32159. Стратегические беседы. Первичный формат сценарного планирования 27 KB
  Стратегические беседы Особую роль в становлении высокой стратегической культуры организации может сыграть система так называемых стратегических бесед strtegic converstions. Один из результативных способов построения системы стратегических бесед это проведение в организации серии беседдиалогов между соответствующими менеджерами и специалистами в процессе освоения и или развития метода сценарного планирования. Сценарный метод был разработан для того чтобы в коммерческой организации сформировать некоторое общее понимание...
32160. Восемь шагов методики сценарного планирования по П. Шварцу 30.5 KB
  Первый критерий это важность каждого фактора для принятия стратегических решений уровня шага 1. Второй критерий степень неопределенности по факторам уровней шага 3 и шага 2 для решения стратегических вопросов уровня шага 1. 5Выявление логики каждого сценария Результатом данного шага должны стать так называемые логические стержни т. суть в том чтобы выйти на относительно небольшое число сценариев которые являются действительно существенно разными по критерию содержания решений принимаемых по стратегическим вопросам уровня шага 1.
32161. Министратегии организации 26.5 KB
  Министратегии организации Министратегия организации состоит из трех элементов: миссии целей и стратегических приоритетов. Миссия это главная цель организации которая может быть сформулирована в относительно общем виде но при этом обязана достаточно четко выражать основную причину существования именно данной организации. Цели должны полностью раскрывать целевой аспект всей деятельности организации. В результате своеобразного синтеза стратегических целей организации и системы приоритетов по ее ресурсам получается система стратегических...
32162. Определение миссии, цели, стр. приоритетов организации 28.5 KB
  приоритетов организации С помощью министратегии выстраивается простейший так называемый управленческий мост от стратегии организации к ее тактической деятельности. Миссия это главная цель организации которая может быть сформулирована в относительно общем виде но при этом обязана достаточно четко выражать основную причину существования именно данной организации. Миссия стратегического управления организации это ее наиболее общая цель. Конкретная формулировка миссии утверждается руководством организации.
32163. Понятие о продуктово-маркетинговой стратегии организации 25 KB
  Понятие о продуктовомаркетинговой стратегии организации Продуктовомаркетинговая стратегия это подсистема стратегии организации которая нацелена на анализ разработку и принятие стратегических решений по номенклатуре ассортименту качеству и объему производства продуктов а также реализации продуктов на соответствующих рынках. Продуктовомаркетинговая стратегия представляет собой ключевую стратегию выживания спокойного существования экономического роста крупного успеха организации. 2 Классификатора: Классификатор по продукту1 ...