ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Побудова двоїстих задач та їх економічний зміст” (2 години)

 

 

Зміст завдання:Побудувати двоїсті задачі лінійного програмування,

 

дати їм економічну інтерпретацію та знайти їх розв’язок.

 

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

 

 

Порядок виконання:

 

Для кожної задачі з лабораторних робіт №3 виконати такі дії:

 

1. Виписати економіко-математичну модель задачі, останню симплексну таблицю.

2. Побудувати двоїсту задачу.

 

3. Виписати розв’язок двоїстої задачі.

 

4. Дати економічну інтерпретацію двоїстої задачі.

 

Теоретичні відомості

 

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

 

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

 

У лабораторній роботі 1 приведена задача про використання ресурсів

 

(економіко-математична модель і змістовна інтерпретація цієї задачі І

 


представлені в лівій частині табл. 1). У приведеній моделі


bi (i


1, 2,..., m)


 


позначає запас ресурсу


Si ,a ij


– число одиниць ресурсу


Si , споживаного при


 


виробництві одиниці продукції Pj


( j 1, 2,..., n); c j


– прибуток (виторг) від


 

 

реалізації одиниці продукції


 

 

Pj (або ціна продукції


 

Pj ).


 


Допустимо, що деяка організація вирішила закупити ресурси


S1 ,S2 ,...,Sm


 

підприємства і необхідно установити оптимальні ціни на ці ресурси

 

y1 , y2 ,..., ym .

 

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

 


ресурси Z у кількостях

 

мінімальні, тобто


b1 , b 2 ,..., bm


за цінами відповідно


y1 , y2 ,..., ym


були


 


Z b1 y1


b2 y2


...


bm ym


min .


 

З іншого боку, підприємство, що продає ресурси, зацікавлене в тім, щоб отриманий виторг був не менший тієї суми, що підприємство може одержати

при переробці ресурсів у готову продукцію. На виготовлення одиниці продукції

 


P1 витрачається


a11


одиниць ресурсу


S1 ,


a21


одиниць ресурсу


S2 ,...,ai1


одиниць


 


ресурсу S1 ,...,am1 одиниць ресурсу Sm


за ціною відповідно


y1 ,y2 ,...,yi ...,ym .


 

Тому для задоволення вимог продавця витрати на ресурси, які

 


споживаються при виготовленні одиниці продукції

 

ціни c1 , тобто


P1 , повинні бути не менші її


 


a11 y1


a21 y2


...


am1 ym


c1.


 

Аналогічно можна скласти обмеження у виді нерівностей по кожнім виді

 


продукції


P1 ,P2 ,...,Pn . Економіко-математична модель і змістовна інтерпретація


 

отриманої в такий спосіб двоїстої задачі II приведені в правій частині табл. 1.

 

Таблиця 1

 

Задача I (вихідна) Задача II (двоїста)
F c1 x1 c2 x2 ... cn xn max (5.1) при обмеженнях: Z b1 y1 b2 y2 ... bm ym min (5.4) при обмеженнях:

Продовження таблиці 5.1

Задача I (вихідна) Задача II (двоїста)


 

ìa11x1

ï

ïa21x1

í

ï

ïîam1x1


 

a12 x2

a22 x2

 

am 2 x2


 

...

 

...

 

...


 

a1n xn

a2 n xn

 

amn xn


 

b1 ,

b2 ,

 

bm


 

(5.2)


 

ìa11 y1

ï

ïa12 y1

í

ï

ïîa1n y1


 

a21 y2

a22 y2

 

a2 n y2


 

...

 

...

 

...


 

am1 ym

am 2 ym

 

amn ym


 

c1 ,

c2 ,

 

cn


 

 

(5.5)


і умові невід’ємності


і умові невід’ємності


x1 0, x2


0, ..., xn 0.


 

(5.3)


y1 0, y2


0, ..., ym 0.


 

(5.6)


Скласти такий план випуску продукції


Знайти такий набір цін (оцінок) ресурсів


X (x1 ,x2 ,...,xn ), при якому прибуток Y


(y1 ,y2 ,...,ym ), при якому загальні


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


витрати на ресурси будуть мінімальними за умови, що витрати на ресурси при виробництві кожного виду продукції будуть не менші прибутку (виторгу) від реалізації цієї продукції.


 

 


Ціни ресурсів


y1 , y2 ,..., ym


в економічній літературі одержали різні назви:


 

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

 


«несправжні» ціни. На відміну від «зовнішніх» цін


c1 , c2 ,..., cn


на продукцію, які


 


відомі як правило до початку виробництва; ціни ресурсів


y1 , y2 ,..., ym є


 

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

 

 

2. Взаємно двоїсті задачі лінійного програмування і їхні властивості

 

Розглянемо формально дві задачі I і II лінійного програмування, які представлені в табл. 1, абстрагуючи від змістовної інтерпретації параметрів, що входять у їхні економіко-математичні моделі. Обидві задачі мають наступні властивості:

1. В одній задачі шукають максимум лінійної функції, в інший мінімум.

 

2. Коефіцієнти при змінних у лінійній функції однієї задачі є вільними членами системи обмежень в іншій.

3. Кожна з задач задана в стандартній формі, причому в задачі максимізації всі нерівності виду « ≤», а в задачі мінімізації – усі нерівності виду

«≥».


4. Матриці коефіцієнтів при змінних у системах обмежень обох задач є транспонованими одна по відношенню до іншої:

 


æa

ç11

ça


a12

a


...

 

...


a1n ö

÷

ø
,
a ÷


äëÿ


çàäà÷è I


A ç21 22 2 n ÷


ç....


....


....


.... ÷


a
ç

èm1


am 2


...


amn ÷


 


æa

ç11


a21


...


am1 ÷


 

äëÿ çàäà÷è II


ça12

A' ç


a22


...


am 2 ÷

ö
ø
÷.


ç....


....


.... .... ÷


a
ç

è1n


a2 n


...


amn ÷


 

5. Число нерівностей у системі обмежень однієї задачі збігається з числом змінних в іншій задачі.

6. Умови невід’ємності змінних є в обох задачах.

 

Дві задачі I і II лінійного програмування, що володіють зазначеними властивостями, називаються симетричними взаємно двоїстими задачами. Надалі для простоти будемо називати їх просто двоїстими задачами.

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

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

– до виду «≥». Для цього нерівності, у яких дана вимога не виконується,

 

помножити на ( -1).

 

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

3. Знайти матрицю А 1, яка є транспонована до матриці А1.

 

4. Сформулювати двоїсту задачу на підставі отриманої матриці А 1 і умови невід’ємності змінних.

Приклад 1.1.Скласти задачу, яка буде двоїста такій вихідній задачі:


 

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


 

 

F 3x1


 

 

2x 2


 

max


 


ï
ìx1

ï2x1


2x 2 6,

x 2 8,


í x1 x2 1,

ï x 2, ï 2 îïx1 , x 2 0.

 

Розв’язання. 1. Складемо розширену матрицю системи

 

  æ ç ç 6ö ÷ 8 ÷ 1 ÷. ÷
A ç ç
  ç 2 ÷

 

F
ç ÷

è ø

 

2. Знайдемо матрицю А/1, яка транспонована до А

 


 

æ1

ç

A/ ç2

ç è


÷

2÷.

Z
÷

ø


3. Сформулюємо двоїсту задачу:

 


 

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


Z 6y1

 

 

ì y1

ï

í 2y1

ï


8y2

 

 

2 y2

y2


y3 2y4

 

 

y3

y3 y4


min

 

 

3,

 

2,


î y1,


y2 ,


y3 , y4 0.


 

Приклад 1.2. Скласти задачу, яка буде двоїста такій вихідній задачі:

 


 

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


F x1


2 x2


max


 

ï
ì 2 x1

ï x1

í

ï x1

îï x1


 

x2

4 x2

x2

x2


 

1,

 

24,

 

3,

 

5,


x1 0, x2 0.

 

Розв’язання. 1. Тому що вихідна задача є задачею максимізації, то приведемо всі нерівності системи обмежень до виду «≤», для чого праву і ліву частини першої і четвертої нерівностей помножимо на (-1). В результаті

виконаних дій отримаємо:

 


ï
ì 2 x1

ï x1

í


x2

4 x2


1,

 

24,


ï x1

îï x1


x2 3,

x2 5,


 

2. Складемо розширену матрицю системи

 

 

æ 2 1 1 öç ÷


ç 1

A ç1

1 ç


4 24 ÷

1 3 ÷.

÷


ç 1 1 5÷

F
ç ÷

è ø

 

3. Знайдемо матрицю А/1, яка транспонована до А

 

 

æ ö ç ÷

 

A' ç ÷

1 .

Z
è
÷
ç 24 3 5 ø

 

4. Сформулюємо двоїсту задачу:

 


 

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


Z y1

 

 

ì 2 y1

í


24 y2

 

 

y2


3 y3

 

 

y3


5 y4

 

 

y4


min

 

 

1,


îy1


4y2


y3 y4 2,


y1 0, y2


0, ..., y4 0.


 

3. Перша теорема двоїстості

 

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

Основна нерівність теорії двоїстості. Нехай є пара двоїстих задач I і II.

 


Покажемо, що для будь-яких допустимих розв’язків X


x1 ,x2 ,...,xn і


 


Y (y1 ,y2 ,...,ym )


вихідної і двоїстої задач справедлива нерівність


 


 

F ( X )


 

Z (Y )


 

Або


n

å cj xj

j 1


m

å bi yi . (7)

i 1


 

Помноживши нерівності системи обмежень (2) вихідної задачі

 


n

å aij xj

j 1


 

bi (i


 

1, 2, ..., m).


 

 

відповідно на змінні y1 , y2


 

 

,..., yi ,..., ym


 

 

і склавши


 

праві і ліві частини отриманих нерівностей, маємо

 

m n m


åyi åaij xj


åbi yi .


 

(8)


i 1 j 1 i 1

 

Аналогічно перетворивши систему обмежень (5) двоїстої задачі

 


m

å aij yj

i 1


 

c j ( j


 

1, 2, ..., n)


 

 

шляхом множення обох частин її нерівності на


 


змінні


x1 ,x2 ,...,xj ,...,xn


і наступного їхнього додавання, одержимо


 

N m n


åxj åaij yj


åcj xj .


 

(9)


j 1 i 1 j 1

 

Тому що ліві частини нерівності (8) і (9) представляють той самий вираз

 


m n

å å aij xj yi ,

i 1 j 1


 

 

то в силу властивості транзитивності нерівностей одержимо


 

доказ нерівності (7).

 

Тепер можна перейти до ознак оптимальності розв’язків.

 

Достатня ознака оптимальності. Сформулюємо теорему.

 


Теорема. Якщо X


(x1 , x 2 ,..., x n ) i Y


(y1 , y2 ,..., ym )


– допустимі


 

розв’язки взаємно двоїстих задач, для яких виконується рівність


 

F ( X * )


 

Z (Y * ),


 

(10)


 

то X - оптимальний розв’язок вихідної задачі I, а Y - двоїстої задачі II.

 


Нехай


X1 – будь-який допустимий розв’язок вихідної задачі I. Тоді на


 


підставі основної нерівності (5.7) одержимо


F X1


Z(Y


) . Однак


X1 –


 

довільний розв’язок задачі I, звідси випливає в силу рівності (5.10), що

 


F X1


F(X


) , тобто X - оптимальний розв’язок задачі I. Аналогічно


 

доводиться, що розв’язок оптимальний для задачі II. :

 

Крім достатньої ознаки оптимальності взаємно двоїстих задач існують і інші співвідношення між їх розв’язками. Насамперед виникають питання: чи завжди для кожної пари двоїстих задач є одночасно оптимальні розв’язки; чи можлива ситуація, коли одна з двоїстих задач має розв’язок, а інша немає. Відповідь на ці питання дає наступна теорема.

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

значення їхніх лінійних функцій рівні:

 


Fmax


Zmin


або


F(X )


Z(Y


) . (11)


 

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

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

Твердження другої частини легко доводиться методом від противного.

 


Допустимо, що у вихідній задачі лінійна функція не обмежена, тобто


Fmax , а


 

умови двоїстої задачі не є суперечливими, тобто існує хоча б один допустимий

 


розв’язок Y


(y1 , y 2 ,..., ym ) . Тоді в силу основної нерівності теорії двоїстості


 


(5.7)


F(X)


Z(Y), що суперечить умові необмеженості


F(X). Отже при


 


Fmax


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

 

Розглянемо приклади, що підтверджують справедливість першої теореми


 

двоїстості.

 

Приклад .2.Дані дві взаємно двоїсті задачі:

 


I. F


2 x1


3x2


max


II. Z


18 y1


16 y2


5 y3


21y4


min


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


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


ï
ìx1

ï2 x1

í


3x2

x2


18,

 

16,


ìy1

í

î3y1


2 y2

y2


3 y4 2,

y3 3,


 

ï ïî3x1

x1


x2

 

0, x2


5,

 

21,

 

0.


yi 0 (i


1, 2, 3, 4).


Задача I про використання ресурсів і двоїста їй задача II після

 


розв’язання отримали оптимуми лінійних функцій


Fmax


24 для задачі I, і


 


Zmin


24 для задачі II (обидві задачі приведені в розділі 4), тобто висновок


 

першої частини основної теореми двоїстості (11) вірний.

 

Економічний зміст першої (основний) теореми двоїстості. План

 


виробництва X1


(x1 , x 2 ,..., x n )


і набір цін (оцінок) ресурсів Y


(y1 ,y2 ,...,ym )


 

виявляється оптимальними тоді і тільки тоді, коли прибуток (виторг) від продукції, який знайдений при «зовнішніх» (відомі заздалегідь) цінах

c1 ,c2 ,...,cn , дорівнює витратам по «внутрішніх» (обумовлених тільки з розв’язку

 


задачі) цінах


y1 ,y2 ,...,ym . Для всіх же інших планів X і Y обох задач відповідно


 

до основної нерівності (7) теорії двоїстості прибуток (виторг) від продукції

 

завжди менше (або дорівнює) витрат на ресурси.

 


Так, у задачі 2 оптимуми прибутку від продукції


Fmax і витрат на ресурси


 


Zmin


дорівнюють 24 грош. од., а для всіх інших планів


F(X)


24, Z(Y)


24 .


 

Економічний зміст першої теореми двоїстості можна інтерпретувати і так:

 

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

 


X (x1 ,x2 ,...,xn )


і дістати максимальний прибуток (виторг)


Fmax


або продавати


 


ресурси за оптимальними цінами Y


(y1 ,y2 ,...,ym )


і відшкодувати від


 


продажу рівні їй мінімальні витрати на ресурси


Zmin .


 

Приклад 3. Дані дві взаємно двоїсті задачі:


 

I. Z


 

8 y1


 

2 y2


 

min


 

II. F


 

x1 x2


 

max


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


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


ì y1

í

î 2y1


2 y2 1,

y2 1,


ìx1

í

î2x1


2 x2 8,

x2 2,


y1 0, y2 0.


x1 0, x2 0.


Пропонуємо читачеві самостійно переконатися (симплексним методом

 

або геометрично) у тім, що у вихідній задачі I лінійна функція не обмежена

 


(Zmin


) , а в двоїстій задачі умови суперечливі, тобто висновок другої


 

частини основної теореми подвійності виконується.

 

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

Приклад 4.Дані дві взаємно двоїсті задачі:

 


I. F


3x1


5x2


max


II. Z


5 y1


7 y2


min


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


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


ì3x1

í


4 x2 5,


ì3 y1

í


2 y2 3,


î 2x1 7,


î 4y1 5,


x1 0, x2 0.


yi 0, y2 0.


 

 

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

 

 

4. Друга теорема двоїстості

 

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

Нехай дані дві взаємно двоїсті задачі I – (1) – (3) і задачі II – (4) – (6). Якщо кожну з цих задач вирішувати симплексним методом, то необхідно привести їх до канонічного виду, для чого в систему обмежень (2) задачі I (у


 


n

короткому записі å aji xj

j 1


 

bi , i


 

1, 2, ..., m)


 

 

варто ввести т ненегативних


 


змінних


xn 1 ,xn 2 ,...,xn 1 ,...,xn m


а в систему обмежень (5) задачі II


 


m

aji yi

i 1


 

c j , j


 

1, 2, ..., n)


 

 

- n ненегативних змінних


 

 

ym 1


 

 

, y m 2


 

 

,..., ym


 

 

j ,..., y n m ,


 


де i(j) – номер нерівності, у яку введена додаткова змінна


xn 1


0(ym j


0) .


 

Системи обмежень кожної з взаємно двоїстих задач приймуть вид:

 


n

å aij xj

j 1


 

Xn i


 

bi , i


 

1, 2, ..., m.


 

 

(12)


 


m

å aij yi

i 1


 

Ym j


 

c j , j


 

1, 2, ..., n.


 

 

(13)


 

Установимо відповідність між первинними змінними однієї з двоїстих

 

задач і додатковими змінними іншої задачі (табл. 2).

 

Таблиця 2

 

Змінні вихідної задачі I
Первинні Додаткові
x1 x2 ... x j ... xn   b b b b   ym 1 ym 2 ... ym j ... ym n xn 1 xn 2 ... xn i ... xn m b b b b (5.14) y1 y2 ... y j ... ym
Додаткові Первинні
Змінні вихідної задачі II

Теорема. Позитивним (нульовим) компонентам оптимального розв’язку

 

однієї з взаємно двоїстих задач відповідають нульові компоненти оптимального

 


розв’язок іншої задачі, тобто для будь-яких i


1,2,...,m i j


1,2,...,n: якщо


 


xj 0, то


ym j


0 ; якщо


x n 1


0 , то yi


0 і аналогічно, якщо yi


0 , то


 


x n 1


0 ; якщо


ym j


0 , то x j 0 .


 

Виразимо додаткові змінні із систем обмежень (12) вихідної задачі I і (12)

 

двоїстої задачі II, які представлені у канонічному виді

 


 

xn i


n

bi å aij xj ,i

j 1


 

1, 2, ..., m,


 

 

(15)


 


 

ym j


m

å aij yi

i 1


 

c j , j


 

1, 2, ..., n.


 

 

(16)


 

Множачи кожну рівність системи (15) на відповідні змінні yi 0 і

 

додаючи отримані рівності, знайдемо

 


m

å xn

i 1


 

j yi


m

å bi yi

i 1


m n

å å aij xj yi . (17)

i 1 j 1


 

Аналогічно, множачи кожну рівність системи (16) на відповідні змінні

 


xj 0


і додаючи отримані рівності знайдемо


 


n

å xj ym j

j 1


m n

å å aij xj yi

i 1 j 1


n

å cj xj .

j 1


 

 

(18)


 

Рівності (17) і (18) будуть справедливі для будь-яких допустимих значень

 


змінних, у тому числі і для оптимальних значень


xj ,xn i , yi ,ym


j . У силу першої


 


 

 

теореми двоїстості (11)


 

 

F(X )


 

 

Z(Y )


n

*

c x
å
або j j

j 1


m

i i
å b y* ,

i 1


 

 

тому з запису


 

правих частин рівностей (17) і (18) випливає, що вони повинні відрізнятися

 


m

тільки знаком. З іншого боку, з невід’ємності виразів å xn 1 yi

j 1


n

і å xj ym

j 1


 

j , які


 

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

Ці умови можуть виконуватися одночасно тільки при рівності цих правих

 

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

 

ìm * *

ïåxn 1 yi i 0,

ïi 1

ín (19)

ïåxj ym j 0.

* *

 

j 1

 

У силу умови невід’ємності змінних кожен з доданків у рівностях (19)

 

повинен дорівнювати нулеві:


 

x
y
*
*
ìïn i i

í


 

0, i


 

1, 2,..., m,


x* y*


0, j


1,2,...,n,


J m j

 

відкіля випливає висновок теореми.

 

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

Розглянута теорема є наслідком наступної теореми.

 

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

Приклад 5.Переконатися в справедливості другої теореми двоїстості для взаємно двоїстих задач I і II, які приведені у задачі 2.

Розв’язання. На підставі виразу (14) установимо наступну відповідність

 

між змінними:

 


x1 x2

b b

 

y5 y6


x3 x4 x5 x6

b b b b .

y1 y2 y3 y4


 

У лабораторній роботі 3 обидві задачі були розв’язані симплексним

 

методом. На останньому кроці розв’язання кожної задачі отримано:

 


у вихідній задачі I


у двоїстій задачі II


 


 

F 24


5 x3


5 x4 .


 

(20)


Z 24


y3 3 y4


6 y5


4 y6 .


(21)


 

F(X )


 

Fmax


 

24 при


Z(Y )


Zmin


24 при оптимальному


базисному розв’язку


оптимальному базисному розв’язку


 

Y* (4 ; 3;0;0;0;0).

5 5


 

X* (6;4;0;0;1;3).

 

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

 


y
y
* 4, *

1 5 2


3 * 0, *

y
y
,
5 3 4


 

0, y*


 

0, y*


 

0 рівні (по абсолютній величині)


 

коефіцієнтам при відповідних змінних лінійної функції (5.20), яку можна

 


F 24 4 x 3 x


 

x x x x


представити у виді


 

5 3 5 4


0 5 0


6 0 1 0 2 , а


 

компоненти оптимального розв’язку вихідної задачі

 


x
* 6, x*


4, x*


0, x*


0, x*


1, x* 3


 

дорівнюють коефіцієнтам при


 

відповідних змінних лінійної функції (5.21), яку можна представити у виді

 


Z 24


6 y5


4 y6


0 y1


0 y2


1 y3


3 y4 .


 

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

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

Приклад 6. Вирішити симплексним методом задачу

 


 

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


F x1

 

ì 2x1

ï


2 x2

 

x2


max

 

 

1,


ïx1

í ïx1

ïî x1

x1


4x2

x2

x2

0, x2


24,

 

3,

 

5,

 


 

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

Р о з в’я з а н н я. Розв’язуючи задачу симплексним методом, одержимо

 

на останньому кроці розв’язок (рекомендуємо читачеві переконатися в цьому

 


 

самостійно): F

 

 

розв’язку


10 2 x

7 3


x4 ,


 

тобто


 

Fmax


 

10 при оптимальному базисному


 

X 4; 7; 0; 0; 6; 6 .

 

У даній задачі відповідність (5.14) між змінними прийме вид:

 


x1 x2

b b

 

y5 y6


x3 x4

b b

 

y1 y2


x5 x6

b b

 

y3 y4


 


На підставі першої теореми двоїстості


Zmin


Fmax


10 . На підставі другої


 

теореми двоїстості оптимальний розв’язок двоїстої задачі

 


Y (2 / 7; 3 / 7; 0; 0; 0; 0) , тому що y1


2 / 7 , тобто коефіцієнтові при відповідній


 


змінній


x 3 у виразі лінійної функції мети


F x , y 2


3 / 7 , тобто коефіцієнтові


 


при змінній


x 4 , y3 y 4


y5 y6


0 (через відсутність відповідних змінних


 


x 5 , x 6 , x1 , x 2


у виразі


F(x) ; їхні коефіцієнти дорівнюють нулю). Отже, у


 


двоїстій задачі


Zmin


10 при Y


(2 / 7; 3 / 7; 0; 0; 0; 0) .


 

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

останню симплекс – таблицю.

 

Таблиця 1

 

       
Б b Ax1 Ax2 Ax3 Ax4 Ax5 Ax6  
x2 4/3 2/3 -1/3  
x1 10/3 -1/3 2/3  
x5 -1  
x6 2/3 -2/3 1/3  
  “ ” 38/3 1/3 4/3  
      y5 y6 y1 y2 y3 y4  

 

Співвідношення між змінними має вид:

 


x1 x2

b b

 

y5 y6


x3 x4

b b

 

y1 y2


x5 x6

b b

 

y3 y4


 

Із “ ” рядка ми знаходимо значення

 


y1 1/ 3, y2


4/ 3, y3 y4


y5 y6


0 , використовуючи приведене вище


 

співвідношення між змінними. Аналогічно знаходиться розв’язок вихідної задачі, якщо табличним симплекс – методом розв’язана двоїста задача.

Метод, при якому спочатку симплексним методом розв’язується двоїста задача, а потім за допомогою теорем двоїстості знаходяться оптимум і оптимальний розв’язок вихідної задачі, називається двоїстим симплексним методом. Цей метод буває вигідно застосовувати, коли перший базисний розв’язок вихідної задачі недопустимий або, наприклад, коли число її обмежень m більше числа змінних n.

 

 

5. Об'єктивно обумовлені оцінки і їхня суть

 

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

Для з’ясування суті цих оцінок повернемося до задачі I про використання ресурсів і двоїстої їй задачі ІІ (задача 2). Компоненти оптимального розв’язку

цих задач, які приведені в задачі 5, дані в табл. 3.

 

Таблиця 3

 

 


Компоненти оптимального розв’язоку двоїстої задачі I
Число одиниць продукції   Залишки ресурсів, одиниць
Р1 Р2 x* 6 x* 4   b b   y * 0 y * 0 S1 S2 S3 S4 x* 0 x* 0 x* 1 x* 3   b b b b   y * 4 / 5 y * 3 / 5 y * 0 y * 0

 

1 2 3


4 5 6


 

 


5 6 1


2 3 4


 

 

Перевищення витрат на ресурси над ціною реалізації


 

Об'єктивно обумовлені оцінки ресурсів (умовні ціни ресурсів)


Компоненти оптимального розв’язку двоїстої задачі II

 

 


У табл. 3 додаткові змінні вихідної задачі I


x3 ,x4 ,x5 ,x6 , які


 


представляють відповідно до виразу (15) різницю між запасами bi


ресурсів


 


S1 ,S2 ,S3 ,S4


і їхнім споживанням, виражають залишки ресурсів, а додаткові


 


змінні двоїстої задач II


y5 ,y6 , що представляють відповідно до виразу (16)


 

різницю між витратами на ресурси для виробництва з них одиниці продукції і

 


цінами ci


продукції


P1 ,P2 , виражають перевищення витрат над ціною.


 


Ресурси


S1 ,S2


за оптимальним планом повністю використані


 


(x 3

 

 

(y*


0, x 4

 

4; y*<

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти