1. лінійне програмування icon

1. лінійне програмування



Название1. лінійне програмування
страница3/5
Дата конвертации12.12.2012
Размер0.67 Mb.
ТипДокументы
1   2   3   4   5
1. /Оптимизация 1.DOC1. лінійне програмування
Загальний випадок двоїстості

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

Нехай пряма задача ЛП задана у вигляді

максимізувати (1.4.14)

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

(1.4.15)

; (1.4.16)

xj  0 , j = 1, 2, …, n1  n. (1.4.17)

Тоді двоїста задача стосовно задачі (1.4.14) - (1.4.17) записується так:

мінімізувати (1.4.18)

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

(1.4.19)

(1.4.20)

yi  0; i=1, 2, …, m1  m. (1.4.21)

Приклад 1.4.2.

Записати двоїсту задачу :

максимізувати (x1+x2)

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

2 x1 - x2 = 6,

-x1 + x22,

x1 + x2 10,

x1 0,

Двоїста задача записується так:

мінімізувати 6y1 + 2y2 + 10y3

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

2y1 - y2 + y3  1

-y1 + y2 + y3 = 1

y2 , y3  0

1.5. Двоїстий симплекс-метод


Задача ЛП в канонічній формі має вигляд

максимізувати L(x) = (1.5.1.)

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

() (1.5.2)

або



Припустимо, що nm і ранг матриці А дорівнює m.

Двоїста задача до задачі (1.5.1), (1.5.2) записується так:

мінімізувати (1.5.3)

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

, , (1.5.4)

Назвемо спряженим базисом або базисом двоїстої задачі таку систему з m лінійно–незалежних векторів матриці обмежень прямої задачі , для якої базисний розв’язок y відповідної системи лінійних рівнянь вигляду

, i є (1.5.5)

задовольняє всім обмеженням (1.5.4).

Розкладемо вектор b за спряженим базисом

(1.5.6)

Розв’язавши систему (1.5.6), знайдемо деякий її базисний розв’язок {} i є, який зветься псевдопланом прямої задачі, оскільки для нього може виконуватися умова невід’ємності змінних .

Опис алгоритму. Задача ЛП має бути задана в канонічній формі (1.5.1), (1.5.2) бо зведена до неї. Відшукують спряжений базис двоїстої задачі й позначають його {Ai}, iIб . Розкладемо А0 за векторами базису Аі1, … , Аіm й знайдемо псевдоплан {}, iIб прямої задачі.

Дослідимо знаки {хi0}. Якщо має місце випадок хi00, iIб , то початковий псевдоплан є оптимальним планом прямої задачі. При наявності від’ємних компонент {хi0} обчислюємо коефіцієнти розкладання векторів Aj за векторами спряженого базису {хij} .

Якщо для деякого r такого, що хr0<0, всі хrj0 то задача не розв‘язна, і на цьому процес обчисленнь закінчується.

Якщо має місце випадок - для кожного r такого, що хr0<0, хоча б одна компонента хrj<0 переходимо до другого етапу. З цією метою складають таблицю k-і - ітерації ( аналогічну симплекс-таблиці ), яка містить (m + 2) рядків і (n + 1) стовпців (табл. 1.5.1).

Стовпець Вх таблиці, як і звичайно, містить вектори {Ai} базису псевдоплану хК, а стовпець А0 – базисні компоненти псевдоплану { хi0(К) }. Рядок (m + 1)-індексний, його заповнюють параметрами , що є оцінками векторів Аj:



величина - значення цільової функції при псевдоплані

Ітерація k закінчиться заповненням головної частини таблиці ( від першого до (m + 1)-го рядків).

Таблиця 1.5.1.

cі







c1

C2



cj



cn




Bx

A0

A1

A2



Aj



An

c1

x1

x10

x11

x11



x1j



x1n

c2

x2

x20

x21

x22



x2j



x2n



















ci

xi

xi0

xi1

xi2



xij



xin



















cm

xm

xm0

xm1

Xm2



xmj



xmn






0

1

2



j



n









1

2



j






На першому етапі (k + 1)-і ітерації з’ясовують, чи має місце перший, другий або третій випадок.

У третьому випадку переходимо до другого етапу. Спочатку визначають вектор Аr, який треба вивести з базису. Його індекс r визначають із умови

хr0=. (1.5.7)

Тобто за максимальною за модулем від’ємною компонентою базисного розв’язку.

Далі заповнюють елементи {} (m + 2)-го рядка, які обчислюють за формулою

={}. (1.5.8)

У рядку заповнюють лише ті позиції, для яких xrj<0. Вектор Аі , який треба звести до базису, знаходять із умови

.

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



де - напрямний елемент перетворення.

Приклад 1.5.1.. Розв’язати задачу лінійного програмування двоїстим симплекс-методом.

максимізувати (x1+4x2)

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

2 x1 - x26,

-x1 + x22,

x1 + x2 10,

x1, x2 0,

або в розширеній формі

2 x1 - x2 + x3 + 0 x4 + 0 x5 = 6,

- x1 + x2 + 0 x3 + x4 + 0 x5 = 2,

x1 + x2 + 0 x3 + 0 x4 + x5 = 10,

x1, … , x5 0.

Двоїста задача записується так:

мінімізувати 6y1 + 2y2 + 10y3

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

2y1 - y2 + y3  1 {A1}

-y1 + y2 + y3  4 {A2}

y1 , y2 , y3  0 {A3} {A4} {A5}

Виберемо за спряжений базис вектори {A2, A3, A4}.

Тоді розв’язком системи лінійних рівнянь є

y1 =0

y2 =0

y3 =4

Підставивши цей розв’язок в обмеження {A1} і {A5}, бачимо, що вони також виконується, а тому {A2, A3, A4} – спряжений базис двоїстої задачі.

Знайдемо псевдоплан X0 прямої задачі. Для цього розв’яжемо систему рівнянь A0 = A2х20 + A3х30 + A4х40. Звідси х20 = 10; х30 = 16; х40 = -8.

Обчислюємо коефіцієнт рокладання { хij }

A1 = A2х21 + A3х31 + A4х41

і знаходимо

х21 = 1; х31 = 3; х41 = -2.

Аналогічно маємо

A5 = A2х25 + A3х35 + A4х45

Розв’язок цієї системи рівнянь: х25 = 1; х35 = 1; х45 = -1.

Таблиця. 1.5.2.

Cj







1

4

0

0

0




Bx

A0

A1

A2

A3

A4

A5

4

X2

10

1

1

0

0

1

0

X3

16

3

0

1

0

1

0

X4

-8

-2

0

0

1

-1






40

3

0

0

0

4









3/2










4


Перша ітерація.

Визначимо напрямний рядок. Це рядок X4 оскільки X40 = -8 < 0. Знаходимо напрямний стовпець, для цього заповнимо рядок . Напрямний стовпець А1, тому що

1=3/2 <  5=4/2

Отже, напрямний елемент Х41 = -2. Виконавши першу ітерацію симплекс-методу, одержимо таблицю 1.5.3

Таблиця 1.5.3.

Сj







1

4

0

0

0




Bx

A0

A1

A2

A3

A4

A5

4

X2

6

0

1

0

1/2

1/2

0

X3

4

0

0

1

3/2

-1/2

1

X1

4

1

0

0

-1/2

1/2






28

0

0

0

3/2

5/2

Оскільки всі елементи стовпця А0 , то знайдено оптимальний план, причому

x1опт=4 x2опт= 6.

Цільова функція Lmax =28

Розв’язати задачi лінійного програмування двоїстим симплекс-методом.

1.5.2.

F=x1+2x2max;

2x1+3x28,

2x1+x26,

x1+x21;

x1, x2 0.

1.5.3.

F=-2x1+x2min;

2x1+x28,

x1+3x26,

3x1+x23;

x1, x20.

1.5.4.

F=x1-2x2max;

5x1-2x23,

x1+x21,

-3x1+x23;

x1, x20.

1.5.5.

F=8x1+2x2max;

x1-4x24,

-4x1+x24,

x1+x26;

x1, x20.

1.5.6.

F=7x1-2x2max;

X1+x25,

2x1-3x26,

3x1+x2-3;

x1, x20.

1.5.7.

F=2x1+x2-3x3max;

x1+3x2-2x34,

-5x1+x3-12,

2x1+x2-3x3-4,

x1, x2, x30.

1.5.8.

F=6x1+4x2min;

2x1+x23,

x1-2x22,

3x1+2x21;

x1, x20.



1.5.9.

F=-x1-2x2min;

5x1-2x24,

-x1+2x24,

x1+x24;

x1, x20.

1.5.10.

F=x1+2x2min;

5x1-2x220,

x1-2x2-20,

x1+x216;

x1, x20.

1.5.11.

F=x1+x2max;

2x1+x218,

x1+2x216;

x1, x20.

1.5.12.

F=x1+x2min;

2x1+x28,

x1+3x26,

x1, x20.

1.5.13.

F=2x1-3x2min;

5x1+2x210,

x1+3x212;

x1, x20.



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


Теорія двоїстості дає змогу аналізувати моделі ЛП на чутливість.

Розглянемо звичайну задач ЛП вигляді

максимізувати (1.6.1)

при обмеженнях (1.6.2)

xj 0. (1.6.3)

Нагадаємо її економічну інтерпретацію. Цільова функція L(x) - це дохід від реалізації плану виробництва x; aij - інтенсивність використання i-го ресурсу при j-му способі виробництва; bi-наявний рівень i-го ресурсу.

1. Варіювання обмежених ресурсів. Припустимо, що значення ресурсів b=|| bi || варіюються. Тоді виникають питання: при яких варіаціях правих частин обмежень знайдений оптимальний план x0 не змінюється; як ці варіації впливають на функцію максимального доходу Lmax? Відповідь на ці питання дає аналіз відповідної задачі ЛП на чутливість.

Нехай обмеження bi одержують деякі варіації bi, що приводять до варіації плану x0, x0= x0(b+b) і функції Lmax (x0(b0+b)).

Позначимо через Ax матрицю оптимального базису задачі ЛП при векторі ресурсів b. Очевидно відповідний оптимальний розв‘язок

xопт= A-1x b. (1.6.4)

xн = А-1хbн = А-1х(b+b). (1.6.5)

Якщо всі компоненти xiн 0, то цей розв‘язок xн =[ xiн] оптимальний (тобто оптимальний базис не змінився). У противному разі треба реалізувати пошук нового розв‘язку, для цього можна застосувати двоїстий симплекс-метод, починаючи з поточного базисного розв‘язку xн.

2. Варіювання цільової функції. Тепер розглянемо випадок, коли варіюються коефіцієнти {cj}, j= 1.2…..n. Спробуємо визначити умови, за яких знайдений раніше оптимальний план лишається оптимальним при таких варіаціях.

Нехай варіація стосується коефіцієнта . Позначимо через Jб, Jнеб множину індексів базисних та небазисних векторів в оптимальному плані x0 відповідно.

Знайдемо значення оцінок після варіації cr для двох випадків:

1) r Jнеб , тоді для усіх jr;

для j=r ; (1.6.6)

2) r Jб,

j Jнеб (1.6.7)

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

3. Варіювання елементів матриці обмежень A. Розглянемо лише випадок варіації компонентів небазисних векторів Aj=[aij], i=1.2…..m, оскільки дослідження варіацій компонент базисних векторів Ai досить складне, легше заново розв‘язати задачу з новими умовами.

Отже, припустимо, що небазисний вектор Aj=[amj] змінився. Треба з‘ясувати, чи залишиться оптимальним поточний базис. Для цього корисно застосувати теорію двоїстості. Нехай оптимальний базис прямої задачі Ax, а відповідні оптимальні значення двоїстих змінних . Як відомо, умова оптимальності 0,  j Jнеб Водночас, . Отже якщо , то попередній базис лишається оптимальним.

4. Додавання ще одного способу виробництва. Припустимо, що додається ще один (n+1)-й спосіб виробництва, якому відповідає вектор технологічних витрат An+1=[ai n+1] і коефіцієнт ц.ф. функції cn+1.

Треба визначити, чи зміниться при цьому попередній оптимальний розв‘язок і при якому значенні коефіцієнта cn+1 випуск (n+1)-го продукту буде рентабельним (тобто ).

Щоб оптимальний розв‘язок після введення вектора An+1 не змінився, необхідно, щоб вектор An+1 і змінна xn+1 лишалися небазисними, тобто, щоб n+10. На основі теорії двоїстості одержимо .

Якщо , то попередній оптимальний план не зміниться після включення випуску (n+1)-го виду продукції.

Якщо ж , то випуск (n+1)-го виду продукції стає рентабельним, і попередній оптимальний план змінюється.

Приклад 1.6.1. Підприємство випускає вироби двох видів, для виготовлення яких використовуються ресурси двох типів. Нехай прибуток від продажу виробів становить відповідно c1=2 та c2=1, обсяг ресурсів дорівнюють b1=40, b2=56 відповідно. Норми витрат ресурсів на одиницю випуску задаються такою матрицею:



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

  2. Нехай перший ресурс b1 зменшився до 36, а другий збільшився до 60. Як зміниться при цьому оптимальний розв‘язок, чи залишиться оптимальним попередній базис?

  3. Нехай вводиться додаткове обмеження на випуск першого продукту x1 9. Визначити новий оптимальний план.

  4. Нехай підприємство може додатково випускати третій вид продукції, для якого c3=2, а норми витрат ресурсів дорівнюють a13=2; a23=4. Знайти оптимальний план за цієї умови і визначити, при якому значенні c3 виробництво третього виду виробів буде рентабельним.

Розв‘язання . Математична модель задачі:

max (2 x1+ x2)

при обмеженнях 4 x1+ x2  40;

2 x1+5 x2  56;

x10, x20.

Розв‘яжемо цю задачу симплекс-методом і через дві ітерації знайдемо оптимальний план (таблиця 1.6.1).

Таблиця 1.6.1

cj







2

1

0

0




Bx

A0

A1

A2

A4

A5

2

х1

8

1

0



-

3

х2

8

0

1

-








24

0

0





Одержимо =8; =8; max (2 x1+ x2)=24.

Матриця утворена небазисними векторами A4, A5 в табл.1.6.1



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

Нехай перший ресурс зменшився до 36 одиниць, а другий збільшено до 60 одиниць, тоді новий вектор =[ 36; 60 ]T. Знайдемо новий базисний розв‘язок для цього вектора:



Оскільки , то цей розв‘язок буде оптимальним (бо не змінилися оцінки 4 та 5 для небазисних векторів).

Нехай введено додаткове обмеження x19. Зведемо його до стандартного вигляду:

x1 - x6 = 9  -x1 + x6 = - 9.

Допишемо цей рядок до симплекс-таблиці 1.6.1, і одночасно праворуч до неї стовпець A6. Одержимо головну частину табл. 1,6.2.

Таблиця 1.6.2.

ci







2

3













Bx

A0

A1

A2

A4

A5

A6

2

x1

8

1

0



-

0

3

x2

8

0

1

-



0




x6

-9

-1

0

0

0

1






-1

0

0



-

1


Аналізуючи її бачимо, що базисний стовпець A1 не є одиничним, і треба виключити змінну x1 в рядку x6. Для цього додамо до рядка x6 рядок x1, в результаті одержимо новий рядок , який дописуємо до табл.1.6.2. знизу, а рядок x6 можна викреслити.

Оскільки компонента = -1<0, то базисний розв‘язок { x1 , x6 , } -це псевдоплан: і далі для продовження ітерацій застосуємо двоїстий симплекс-метод.

Напрямний рядок , напрямний стовпець A5. Виконавши одну ітерацію двоїстого симплекс-методу, отримаємо симплекс-таблицю 1.6.3.


Таблиця 1.6.3.

ci










Bx

A0

2

x1

9

1

x2

4

0

x5

18






33


Оскільки =9>0,=4>0, то цей новий розв‘язок оптимальний. При цьому Lmax=22.

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

Згідно з теорією двоїстості . Оскільки 3<0 , то стовпець A3 доцільно ввести до базису. Згідно з методом оберненої матриці обчислюємо його вигляд , в якому можна дописати до таблиці 1.6.1:



Дописавши стовпець A3 до симплекс-таблиці оптимального розв‘язку вихідної задачі (табл.1.6.1), одержимо таблицю 1.6.4.

Таблиця 1.6.4.

ci







2

3







2




Bx

A0

A1

A2

A4

A5

A3

2

x1

8

1

0



-



1

x2

8

0

1

-










24

0

0





-


При цьому .

Виконавши першу ітерацію симплекс-методу, одержимо симплекс-таблицю 1.6.5.


Таблиця 1.6.5..

ci







2

1







4




Bx

A0

A1

A2

A4

A5

A3

2

x1

4

1

-



-

0

2

x3

12

0



-



1






32

0

1





0

Оскільки всі елементи її індексного рядка j  0, то цей розв‘язок оптимальний: =4; =12. При цьому значення ц.ф. збільшилося до 32 одиниць.


1.7. Транспортна задача лінійного програмування


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


Постановка Т-задачі. Нехай в пунктах А1, …. , Am випускають деякий однорідний продукт, причому обсяг виробництва в пункті Ai становить ai одиниць, i = 1,m. Припустимо, що цей продукт споживають в пунктах B1, … , Bn , a обсяг споживання в пункті Вj становить bj одиниць j = 1,n. Припустимо, що з кожного пункту виробництва можливе перевезення продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукту з пункту Ai в пункт Вj дорівнюють Cij (i = 1,m j = 1,n ). Задача полягає у визначенні такого плану перевезень, при якому попит всіх споживачів Вj повністю задовольняється, увесь продукт з пунктів виробництва вивезений і сумарні транспортні витрати мінімальні.

Треба визначити множину змінних , i = 1,m , j = 1,n , що задовольняють умови

(1.7.1)

(1.7.2)

і таких, що цільова функція

(1.7.3)

досягає мінімального значення.

Умова (1.7.1) гарантує повний вивіз продукту з усіх пунктів виробництва, а (1.7.2) означає повне задоволення попиту в усіх пунктах споживання.

Таким чином, Т-задача являє собою задачу ЛП з числом змінних, та ( m + n ) обмеженнями рівностями.

Змінні зручно задавати у вигляді матриці

(1.7.4)

Матрицю X, що задовольняє умови Т-задачі (1.7.1) і (1.7.2) називають планом перевезень, а змінні - перевезеннями. План , при якому цільова функція мінімальна, зветься оптимальним, а матриця С= - матрицею транспортних витрат.

Властивості транспортної задачі

1. Для розв’язання Т-задачі необхідно і достатньо, щоб задовольнялась умова балансу

(1.7.5)

тобто, щоб сумарний обсяг виробництва дорівнював обсягу споживання.

2. Ранг системи обмежень (1.7.1), (1.7.2) дорівнює

Двоїста транспортна задача (-задача). Для Т-задачі, як і для довільної задачі ЛП, існує двоїста задача до неї -задача.

Змінні -задачі позначимо V1, V2, …, Vn, -U1, -U2, …,-Um

Теорема . Для оптимальності плану Х0 Т-задачі необхідне і достатнє існування таких чисел V1, V2, …, Vn, -U1, -U2, …,-Um , що

Vj – Ui Cij , i = 1,m; j = 1,n; (1.7.6)

При цьому, якщо

то Vj – Ui = Cij

Опорні плани Т-задачі

Опорним (базисним) планом Т-задачі зветься будь-який її допустимий, базисний розв’язок. и довільного плану на опорність.

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




Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы