Двоїстість в оптимізаційних задачах

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

ЛЬВІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ІВАНА ФРАНКА

ЕКОНОМІЧНИЙ ФАКУЛЬТЕТ

Кафедра економічної кібернетики

КУРСОВА РОБОТА

з дисципліни “Дослідження операцій”

на тему:

“Двоїстість в оптимізаційних задачах”

Львів-2012

АНОТАЦІЯ

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

“ДВОЇСТІСТЬ В ОПТИМІЗАЦІЙНИХ ЗАДАЧАХ”

Вихопень О.І.

ДВОЇСТА ЗАДАЧА, ДВОЇСТІ ОЦІНКИ, ДОПОВНЯЛЬНА НЕЖОРСТКІСТЬ, ЕКОНОМІЧНА ІНТЕРПРЕТАЦІЯ, ПРЯМА ЗАДАЧА, ТЕОРЕМА ДВОЇСТОСТІ.

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

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

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

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

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

Курсова робота: загальний обсяг роботи - 63 сторінки , 4 таблиці, 2 додатки на 19 сторінках, 16 джерел літератури.



ЗМІСТ

Вступ

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

1.1 Поняття двоїстості та її економічна інтерпретація для ЗЛП

1.2 Правила побудови двоїстої задачі

1.3 Основні теореми двоїстості та їх економічний зміст

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

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

1.3.3 Третя теорема двоїстості

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

3. Симплексний метод, як метод отримання розв'язку прямої та двоїстої задачі

3.1 Початковий опорний план

3.2 Перевірка плану на оптимальність за допомогою оцінок

3.3 Алгоритм розв'язування ЗЛП за допомогою симплекс-методу

4. Постановка економіко-математичної задачі із застосуванням теорії двоїстості

Висновки

Список використаних джерел

Додаток А. Спрощена блок-схема алгоритму

Додаток Б. Лістинг програми



ВСТУП

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

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

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

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

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

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

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

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



РОЗДІЛ 1. ЗАСТОСУВАННЯ ТЕОРІЇ ДВОЇСТОСТІ ДЛЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

1.1 Поняття двоїстості та її економічна інтерпретація для ЗЛП

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

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

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

Складемо економіко-математичну модель задачі.

Нехай

n - кількість видів продукції, що виготовляються на підприємстві;

m - кількість видів ресурсів, що використовуються для виробництва продукції;

- кількість одиниць продукції і -го виду, що використовуються для виготовлення одиниці продукції j -го виду;

- запас ресурсу і -го виду; - прибуток від реалізації одиниці продукції j -го;

- кількість одиниць продукції j -го виду, що буде вигототовлятися підприємством.

Отже, математична модель задачі матиме такий вигляд:

;(1.1)

;(1.2)

.(1.3)

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

,

який дає найбільший дохід.

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

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

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

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

(1.4)

; (1.5)

. (1.6)

В результаті ми отримуємо нову задачу (1.4) - (1.6) і вона називається двоїстою до задачі (1.1) - (1.3). Ці задачі записані у матричній формі виглядатимуть так:

(1.7)

(1.8)

1.2 Правила побудови двоїстої задачі

Порівнюючи між собою задачі (1.7) та (1.8) можна записати такі правила побудови двоїстої задачі:

1. Цільові функції пари двоїстих задач мають різні напрями оптимізації.

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

3. Матриця умов двоїстої задачі отримується шляхом транспонування матриці умов прямої задачі.

4. Кожному функціональному обмеженню прямої задачі відповідає прямої задачі відповідає змінна двоїстої задачі.

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

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

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

· Якщо деяке функціональне обмеження прямої задачі виконується як строга рівність то на відповідну змінну двоїстої задачі не накладається умова невід'ємності

;

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

.

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

У симетричних задачах обмеження прямої та двоїстої задач є нерівностями, а змінні обох задач можуть набувати лише невід'ємних значень.

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

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

Пряма задача	Двоїста задача
Симетричні

Несиметричні

Розглянемо властивості пари двоїстих задач:

1. Двоїста задача до двоїстої задачі завжди дасть пряму;

2. Основна нерівність теорії двоїстості.

Лема 1.1 (основна нерівність теорії двоїстості). Якщо

Та

-- допустимі розв'язки відповідно прямої та двоїстої задач, то виконується нерівність:

. (1.9)

Доведення. Помножимо кожне рівняння системи (1.2) на відповідну змінну двоїстої задачі:

. (1.10)

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

(1.11)

Ліві частини нерівностей (1.10) та (1.11) збігаються, отже:

.

Нерівність (1.9) доведено.

1.3 Основні теореми двоїстості та їх економічний зміст

Зв'язок між оптимальними розв'язками прямої та двоїстої задач встановлюють леми та теореми двоїстості. Розглянемо задачі (1.1)--(1.3) та (1.4)--(1.6) з економічною інтерпретацією, наведеною в § 1.1.

Теорема Канторовича. Якщо для допустимих планів

Та

пари двоїстих задач виконується умова

, (1.12)

то ці плани є оптимальними планами пари двоїстих задач.

Доведення. Згідно з основною нерівністю теорії двоїстості

Однак

(умова (1.12)).

Тому

.

Це означає, що

- оптимальний план прямої задачі.

Аналогічно справедливо

Оскільки

,

То

- оптимальний план двоїстої задачі. Теорема Канторовича доведена.

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

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

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

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



Таблиця 1.1 Остання симплексна таблиця

і	Базис	Сб	План	с1	с2	...	сm	cm + 1	...	cn
				x1	x2	...	xm	xm + 1	...	xn
1	x1			1	0	...	0		...
2	x2			0	1	...	0		...
m	xm			0	0	...	1		...
m + 1		F0	0	0	...	0		...

Позначимо через D матрицю, що утворена з компонент векторів А₁, А₂,…, А_m останнього базису в першій симплексній таблиці.

Для оптимального плану отримаємо:

(1.13)

де В -- вектор, що складається з вільних членів системи обмежень;

.

Звідси:

(1.14)

Симплексна таблиця 1.1 містить коефіцієнти розкладу векторів початкової системи обмежень задачі за векторами базису, тобто кожному вектору з системи обмежень задачі (1.1)--(1.3) А_j відповідає в симплексній таблиці вектор , такий що

(1.15)

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

,

звідки

.(1.16)

Враховуючи (1.14), значення оптимального плану даної задачі знаходиться у вигляді:

Де

,

причому

,

тобто всі компоненти вектора є оцінками оптимального плану задачі (1.1) -(1.3), а тому

. (1.17)

Оскільки оптимальний план початкової задачі подано у вигляді

,

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

. (1.18)

Доведемо, що

дійсно є оптимальним планом двоїстої задачі.

Система обмежень двоїстої задачі у векторно-матричній формі матиме вигляд:

.

Підставимо в цю нерівність значення . Тоді, враховуючи (1.16), (1.17) та (1.1), отримаємо:

.

Звідки:

.

Отже, задовольняє систему обмежень (1.5) двоїстої задачі, тому є допустимим планом задачі (1.4)--(1.6).

Для даного плану значення функціонала дорівнюватиме:

,(1.19)

Де

.

Підставимо в (1.19) значення з (1.18) та, враховуючи (1.14), матимемо:

.(1.20)

Доведено, що збігається зі значенням оптимального плану початкової задачі.

Отже, за теоремою Канторовича (достатня умова оптимальності плану задачі лінійного програмування) план є оптимальним планом двоїстої задачі (1.4)--(1.6).

Аналогічно доводиться, що коли двоїста задача має розв'язок, то початкова також має розв'язок і виконується рівність:

.

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

Доведена теорема дає змогу в процесі розв'язування однієї задачі водночас знаходити план другої.

Економічний зміст першої теореми двоїстості. Максимальний прибуток (F_max) підприємство отримує за умови виробництва продукції згідно з оптимальним планом

,

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

.

За умов використання інших планів

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

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

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

Пряма задача:

(1.21)

.

Двоїста задача:

(1.22)

Для розв'язування задач симплексним методом необхідно звести їх до канонічної форми, для чого в системи обмежень задач (1.21) і (1.22) необхідно ввести відповідно m та n невід'ємних змінних. Поставимо обмеженням кожної задачі у відповідність змінні її двоїстої задачі.

Аналогічно:

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

Таблиця 1.2 Відповідність між змінними спряжених задач

Основні змінні прямої задачі

Додаткові змінні прямої задачі

х1

х2

хk

xn

xn + 1

xn + 2

xn + l

xn + m

¦

¦

…

¦

…

¦

¦

¦

…

¦

…

¦

ym + 1

ym + 2

ym + k

ym + n

y1

y2

yl

ym

Наступна теорема в літературі, як правило, має назву теореми про доповнюючу нежорсткість.

Друга теорема двоїстості для симетричних задач. Для того, щоб плани X^* та U^* відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості:

(1.23)

.(1.24)

Доведення. Необхідність. Нехай X^* та Y^* -- оптимальні плани відповідно прямої та двоїстої задач (1.21) i (1.22). З першої теореми двоїстості відомо, що

,

а також компоненти векторів X^* та U^* задовольняють системи обмежень задач (1.21) та (1.22), тобто:

,(1.25)

.(1.26)

Помножимо (1.25) на , а (1.26) -- на і підсумуємо праві та ліві частини. Отримаємо:

;

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

;

Виконаємо перетворення для кожного рівняння:

;(1.27)

.(1.28)

Оскільки

,

то в рівнянні (1.27) кожна з компонент

, а ,

тому виконання рівняння (1.27) можливе лише у тому разі, коли кожний доданок виду

.

Аналогічне міркування проведемо для (1.28), після чого можна висновувати, що

.

Отже, необхідність умов додаткової нежорсткості доведено.

Достатність. За умовою виконуються рівняння

,

, .

Необхідно довести, що X^* та U^* -- оптимальні плани відповідно прямої (1.21) та двоїстої (1.22) задач.

У кожному рівнянні розкриємо дужки та підсумуємо перше рівняння по , а друге -- по . Отримаємо:

;

.

Ліві частини цих рівнянь однакові, отже,

.

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

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

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

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

Економічний зміст другої теореми двоїстості стосовно оптимального плану Х^* прямої задачі. Якщо для виготовлення всієї продукції в обсязі, що визначається оптимальним планом Х^*, витрати одного і-го ресурсу строго менші, ніж його загальний обсяг , то відповідна оцінка такого ресурсу (компонента оптимального плану двоїстої задачі) буде дорівнювати нулю, тобто такий ресурс за даних умов для виробництва не є «цінним».

Якщо ж витрати ресурсу дорівнюють його наявному обсягові , тобто його використано повністю, то він є «цінним» для виробництва, і його оцінка буде строго більшою від нуля.

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

Економічне тлумачення другої теореми двоїстості щодо оптимального плану U^* двоїстої задачі. У разі, коли деяке j-те обмеження виконується як нерівність, тобто всі витрати на виробництво одиниці j-го виду продукції перевищують її ціну с_j, виробництво такого виду продукції є недоцільним, і в оптимальному плані прямої задачі обсяг такої продукції дорівнює нулю.

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

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

1.3.3 Третя теорема двоїстості

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

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

(1.29)

Доведення. Розглянемо задачу лінійного програмування, подану в канонічній формі:

(1.30)

(1.31)

(1.32)

Двоїсту задачу до задачі (1.30)--(1.32) сформулюємо так: знайти оптимальний план

,

за якого мінімізується значення

(1.33)

(1.34)

причому умова невід'ємності змінних відсутня.

Позначимо

-- оптимальний план двоїстої задачі,

-- оптимальний план задачі (1.30)--(1.32). За першою теоремою двоїстості відомо, що:

,

Або

.(1.35)

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

.(1.36)

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

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

,

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

Отже, рівності (1.36) справджуються лише за незначних змін , інакше суттєва зміна умов початкової задачі (правих частин системи обмежень (1.31) та цільової функції (1.33)) приведе до зміни базису в оптимальному плані прямої задачі, а значить, і до іншого розв'язку двоїстої .

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

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

.

Отже, за умови незначних змін замість задачі (1.30) - (1.32) маємо нову задачу, де замінено на

.

Позначимо через оптимальний план нової задачі. Для визначення не потрібно розв'язувати нову задачу лінійного програмування, а достатньо скористатися формулою

,

де -- оптимальний план задачі (1.30)--(1.32).



РОЗДІЛ 2. ЗАСТОСУВАННЯ ДВОЇСТОСТІ В ЗАДАЧАХ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ

Теорія двоїстості знайшла своє практичне застосування і в задачах нелінійного програмування. Розглянемо тепер задачу нелінійного програмування у вигляді:

,(2.1)

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

.(2.2)

Ввівши функцію Лагранджа

,

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

, (2.3)

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

.(2.4)

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

(2.5)

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

(2.6)

двоїстою до задачі (2.3) - (2.4).

Має місце теорема, аналогічна теоремі двоїстості ЛП, вперше доведена П. Вульфом.

Теорема 2.1. Нехай функції

, , ,

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

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

(2.7)

(2.8)

де С - симетрична, від'ємно визначена матриця. Перетворимо (2.7) - (2.8) в еквівалентну задачу мінімізації і побудуємо функцію Лагранджа:

(2.9)

Вихідну задачу можна записати у такому вигляді:

(2.10)

.(2.11)

Неважко показати, що задача (2.10) - (2.11) еквівалентна задачі (2,7) - (2,8).

За аналогією з лінійним програмуванням запишемо двоїсту задачу для задачі квадратичного програмування:

(2.12)

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

(2.13)

Підставляючи вираз для із (2.9) в (2.12) і (2.13), дістанемо таку форму запису двоїстої задачі:

,(2.14)

, .(2.15)

Оптимальні розв'язки та зв'язані між собою співвідношеннями:

(2.16)

(2.17)

Використовуючи вираз (2.9) і підставляючи його в (2.16) та (2.17), знаходимо відповідно:

(2.18)

(2.19)

Покажемо, що задачі (2.7) - (2.8) і (2.14) - (2.15) справді є двоїстими і виконується твердження теореми про те, що

.(2.20)

Оскільки звя'зані між собою співвідношеннями (2.18) та (2.19), то маємо

Або

Таким чином, встановлено справедливість відношення (2.20) і теореми (2.1).



РОЗДІЛ 3. СИМПЛЕКСНИЙ МЕТОД ЯК МЕТОД ОТРИМАННЯ РОЗВ'ЯЗКУ ПРЯМОЇ ТА ДВОЇСТОЇ ЗАДАЧ

3.1 Початковий опорний план

Розглянемо задачу лінійного програмування, записану в канонічній формі:

.

Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо:

(3.1)

(3.2)

(3.3)

Система обмежень (3.2) у векторній формі матиме вигляд:

,(3.4)

Де

, ,..., ,

, …, , ,

-- лінійно незалежні одиничні вектори m-вимірного простору, що утворюють одиничну матрицю і становлять базис цього простору. Тому в розкладі (3.4) базисними змінними будуть , а інші змінні -- вільні. Прирівняємо всі вільні змінні до нуля, тобто . Оскільки , а вектори -- одиничні, то отримаємо один із розв'язків системи обмежень (3.2):

(3.5)

тобто допустимий план.

Такому плану відповідає розклад

(3.6)

де -- лінійно незалежні вектори і план є кутовою точкою багатогранника розв'язків, а отже, може бути початковим опорним планом. Так як вже відомим є опорний план, можна будувати першу симплекс таблицю.

3.2 Перевірка плану на оптимальність за допомогою оцінок

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

.

Потім згідно з умовою оптимальності плану задачі лінійного програмування, якщо всі

(для задачі на максимум), то план є оптимальним. Допустимо, що одна з оцінок

,

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

.

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

Якщо хоча б для однієї від'ємної оцінки

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

Нехай

,

тобто мінімальне значення досягається для k-го вектора . Тоді до базису включається вектор . Відповідний стовпчик симплексної таблиці називають розв'язковим.

Для того, щоб вибрати вектор, який необхідно вивести з базису, розраховують останній стовпчик - значення :

.

З розрахованих значень необхідно вибрати найменше . Тоді з базису виключають i-ий вектор, якому відповідає .

Допустимо, що

відповідає вектору, що знаходиться в l-му рядку. Відповідний рядок симплексної таблиці називають розв'язковим.

Перетином напрямного стовпчика та напрямного рядка визначається елемент симплексної таблиці a_lk, який називають розв'язковим елементом. За допомогою елемента a_lk і методу Жордана--Гаусса розраховують нову симплексну таблицю, що визначатиме наступний опорний план задачі.

3.3 Алгоритм розв'язування ЗЛП за допомогою симплекс-методу

Отже, загалом алгоритм розв'язування задачі лінійного програмування симплекс-методом складається з п'яти етапів:

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

2. Побудова симплексної таблиці;

3. Перевірка опорного плану на оптимальність за допомогою оцінок ;

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

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

5. Повторення дій, починаючи з п. 3.

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

У разі застосування симплекс-методу для розв'язування задач лінійного програмування можливі такі випадки:

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

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

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



РОЗДІЛ 4. ПОСТАНОВКА ЕКОНОМІКО-МАТЕМАТИЧНОЇ ЗАДАЧІ ІЗ ЗАСТОСУВАННЯМ ТЕОРІЇ ДВОЇСТОСТІ

Підприємство «Еталон» виготовляє чотири види автобусів (A, B, C, D) використовуючи для цього три види каркасів. Норми витрат ресурсів на одиницю кожної продукції (в умовних одиницях) наведено в таблиці:

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

Ресурс	Норма витрат на одиницю продукції, ум. од., за видами продукції	Запас ресурсу
	А	В	С	D
1	2	5	2	4	250
2	1	6	2	4	280
3	3	2	1	1	80

Відома ціна одиниці продукції кожного виду: для продукції А -- 2 ум. од., для В і D -- по 4 од., для С -- 3 од. Визначити оптимальний план виробництва продукції кожного виду в умовах обмеженості ресурсів, який дає підприємству найбільший дохід. Наведемо симплекс-таблицю, що відповідає оптимальному плану поставленої задачі.

Передбачається виконання наступних завдань:

1. Сформулювати математичну модель даної задачі лінійного програмування та двоїстої до неї;

2. Записати оптимальні плани прямої та двоїстої задач і зробити їх економічний аналіз;

3. Визначити статус ресурсів прямої задачі та інтервали стійкості двоїстих оцінок відносно зміни запасів дефіцитних ресурсів;

4. Визначити план виробництва продукції та зміну загального доходу підприємства, якщо запас першого ресурсу збільшити на 10 од., другого -- зменшити на 10 од., а третього -- збільшити на 20 ум. од;

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

6. Розрахувати інтервали можливої зміни ціни одиниці кожного виду продукції.

Виконання.

1. Математичні моделі прямої та двоїстої задачі мають такий вигляд:

де х_j -- обсяг виробництва продукції j-го виду ;

де y_i -- оцінка одиниці і-го виду ресурсу .

2. Розв'язуючи пряму задачу симплексним метод отримано таку останню оптимальну симплекс таблицю:

Таблиця 4.2 Остання симплексна таблиця із оптимальним планом

Базис	Сбаз	План	2	4	3	4	0	0	0
			х1	х2	х3	х4	х5	х6	х7
х4	4	45	-2	1/2	0	1	1/2	0	-1
х6	0	30	-1	1	0	0	-1	1	0
х3	3	35	5	3/2	1	0	-1/2	0	2
Zj - Cj ? 0	285	5	5/2	0	0	1/2	0	2

З наведеної симплекс-таблиці виявлено:

Х^* = (0; 0; 35; 45; 0; 30; 0), max F = 285;

Y^* = (4; 0; 3) • = (1/2; 0; 2);

min Z = 250/2 + 160 = 285 = max F.

Оптимальний план прямої задачі передбачає виробництво лише двох видів продукції С і Д у кількості відповідно 35 та 45 од. Випуск продукції А та В не передбачається (х₁ = х₂ = 0). Додаткові змінні х₅, х₆, х₇ характеризують залишок (невикористану частину) ресурсів відповідно 1, 2 та 3. Оскільки х₆ = 30, другий ресурс використовується у процесі виробництва продукції не повністю, а перший та третій ресурси -- повністю (х₅ = х₇ = 0). За такого оптимального плану виробництва продукції та використання ресурсів підприємство отримує найбільший дохід у розмірі 285 ум. од.

План двоїстої задачі дає оптимальну систему оцінок ресурсів, що використовуються у виробництві. Так, у₁ = 1/2 та у₃ = 2 відмінні від нуля, а ресурси 1 та 2 використовуються повністю. Двоїста оцінка у₂ = 0 і відповідний вид ресурсу не повністю використовується при оптимальному плані виробництва продукції. Це підтверджується також попереднім аналізом додаткових змінних оптимального плану прямої задачі. Така оптимальна система оцінок дає найменшу загальну вартість усіх ресурсів, що використовуються на підприємстві: min F = 285 ум. од.

3. Статус ресурсів прямої задачі можна визначити трьома способами. Перший -- підстановкою Х ^* у систему обмежень прямої задачі. Якщо обмеження виконується як рівняння, то відповідний ресурс дефіцитний, у противному разі -- недефіцитний.

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

Третій спосіб -- за допомогою двоїстих оцінок. Якщо у_і 0, то зміна (збільшення або зменшення) обсягів і-го ресурсу приводить до відповідної зміни доходу підприємства, і тому такий ресурс є дефіцитним. Якщо у_і = 0, то і-й ресурс недефіцитний. Так,

у₁ = 1/2 (ресурс 1 дефіцитний);

у₂ = 0 (ресурс 2 недефіцитний);

у₃ = 2 (ресурс 3 дефіцитний).

Отже, якщо запас першого дефіцитного ресурсу збільшити на одну умовну одиницю (b₁ = 250 + 1 = 251), то цільова функція maxF збільшиться за інших однакових умов на у₁ = 1/2 ум. од. і становитиме max F= 285,5 ум. од.

Але за рахунок яких змін в оптимальному плані виробництва продукції збільшиться дохід підприємства? Інформацію про це дають елементи стовпчика «х₅» останньої симплекс-таблиці, який відповідає двоїстій оцінці у₁ = 1/2. У новому оптимальному плані значення базисної змінної збільшиться на 1/2, змінної -- зменшиться на одиницю, а -- на 1/2. При цьому структура плану не зміниться, а нові оптимальні значення змінних будуть такими:

Х^* = (0; 0; 34,5; 45,5; 0; 29; 0).

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

max Z = 2 0 + 4 0 + 3 34,5 + 4 45,5 = 285,5,

тобто зросте на у₁ = 1/2.

Проаналізуємо, як зміниться оптимальний план виробництва продукції, якщо запас дефіцитного ресурсу 2 за інших однакових умов збільшити на одну умовну одиницю (b₃ = 80 + 1 = 81). Аналогічно попереднім міркуванням, скориставшись елементами стовпчика «х₇» останньої симплекс-таблиці, що відповідає двоїстій оцінці у₃ = 2, можна записати новий оптимальний план:

Х^* = (0; 0; 37; 44; 0; 30; 0).

max F = 2 0 + 4 0 + 3 37 + 4 44 = 287.

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

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

Приріст (зміну) запасу ресурсу 1 позначимо b₁. Тоді, якщо

,

то новий оптимальний план

Х^* = (0; 0; 35-1/2b₁; 45 + 1/2b₁; 0; 30 - b₁; 0).

Єдина вимога, яку можна поставити до можливих нових оптимальних значень, -- це умова невід'ємності, тобто

.

Це означає, що коли запас ресурсу 1 збільшиться на 30 ум. од. або зменшиться на 90 ум. од., то оптимальною двоїстою оцінкою ресурсу 1 залишиться у₁ = 1/2. Отже, запас ресурсу 1 може змінюватись у межах

,

.

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

,

,

а оптимальний план виробництва продукції

(0; 0; 80; 0; 0; 120; 0) ? Х^* ? (0; 0; 20; 60; 0; 0; 0).

Аналогічно розраховується інтервал стійкості двоїстої оцінки у₃ = 2 дефіцитного ресурсу 3:

,

.

Отже, якщо запас ресурсу 3 збільшиться на 45 ум. од. або зменшиться на 17,5 ум. од., то двоїста оцінка у₃ = 2 цього ресурсу залишиться оптимальною. Згідно із цим можливий дохід підприємства та оптимальний план виробництва продукції перебуватимуть у межах

;

(0; 0; 0; 62,5; 0; 30; 0) ? Х* ? (0; 0; 125; 0; 0; 30; 0).

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

4. За умовою задачі обсяги всіх трьох ресурсів змінюються відповідно

b₁ = +10, b₂ = -10, b₃ = +20.

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

.

З останньої симплекс-таблиці можна записати обернену матрицю:

.

Змінені запаси ресурсів утворюють вектор

.

Тоді новий оптимальний план виробництва продукції за відповідної одночасної зміни запасів усіх трьох ресурсів

,

Тобто

Х ^* = (0; 0; 70; 30; 0; 10; 0).

Усі і тому оптимальним планом двоїстої задачі залишається

Y ^* = (1/2; 0; 2).

Загальний максимальний дохід підприємства зміниться на

?F_max = b₁y₁ + b₂y₂ + b₃y₃ = 10 • 1/2 -10 • 0+ 20 • 2 = +45 ум. од.

Становитиме

max F= 285 + 45 = 330 ум. од.

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

Підставимо Y ^* у систему обмежень двоїстої задачі. Якщо вартість ресурсів на одиницю продукції (ліва частина) перевищує ціну цієї продукції (права частина), то виробництво такої продукції для підприємства недоцільне. Якщо ж співвідношення виконується як рівняння, то продукція рентабельна.

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

Додаткові змінні двоїстої задачі розміщуються в оцінковому рядку останньої симплекс-таблиці у стовпчиках «х₁»--«х₄». Їх оптимальні значення у₄ = 5; у₅ = 5/2; у₆ = 0; у₇ = 0. Тому продукція А і В нерентабельна, а продукція С і Д -- рентабельна.

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

Х ^* = (0; 0; 35; 45).

Для визначення інтервалів зміни коефіцієнтів цільової функції скористаємось тим, що при цьому симплекс-таблиця, яка відповідає оптимальному плану, зберігає свій вигляд за винятком елементів оцінкового рядка. Нові оцінки (Z_j - C_j) мають задовольняти умову оптимальності задачі максимізації, тобто бути невід'ємними.

Зміну коефіцієнта С₁ позначимо С₁. Оскільки х₁ -- небазисна змінна, то в симплекс-таблиці зміниться лише відповідна оцінка Z₁ - C₁:

(Z₁ - C₁) = 4 (-2) + 0 1 +3 3/2 - (2 + С₁) = 5 - С₁.

За умови Z₁ - C₁ 0 дістанемо нерівність 5 - С₁ ? 0, тобто С₁ ? 5. Це означає, що коли ціна одиниці продукції А за інших однакових умов зросте не більш як на 5 ум. од., то оптимальним планом виробництва продукції на підприємстві все одно залишиться

Х ^* = (0; 0; 35; 45).

Лише максимальний дохід зміниться на

max ?F= С₁х₁.

Аналогічно розраховується інтервал зміни коефіцієнта С₂:

(Z₂ - C₂) = 5/2 - С₂ ? 0; С₂ ? 5/2.

Зі зростанням ціни одиниці продукції В на 5/2 ум. од. за інших однакових умов оптимальний план виробництва продукції не зміниться, а

max ?F = С₂Х₂.

Дещо складніше розраховується інтервал зміни коефіцієнтів для базисних змінних. У цьому разі зміни відбуваються також у стовпчику «С_баз» симплекс-таблиці, а це, у свою чергу, стосується всіх ненульових оцінок (Z_j - C_j). Так, для базисної змінної х₃ зміна коефіцієнта на С₃ приведе до таких оцінок:

(Z₁ - C₁) = 4 (-2) + 0 (-1) +(3 + С₃) 5 - 2 = 5 + 5С₃;

(Z₂ - C₂) = 4 1/2 + 0 1 + (3 + С₃) 3/2 - 4 = 5/2 + 3/2С₃;

(Z₅ - C₅) = 4 1/2 + 0 (-1) - 1/2 • (3 + С₃) - 0 = 1/2 - 1/2С₃;

(Z₇ - C₇) = 4 (-1) + 0 0 + 2 • (3 + С₃) - 0 = 2 + 2С₃.

Нові значення оцінок мають задовольняти умову оптимальності, тобто

Z_j - C_j ? 0.

Тому інтервал для С₃ визначається з такої системи нерівностей:

,

.

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

Х ^* = (0; 0; 35; 45).

Для базисної невідомої х₄ інтервал зміни коефіцієнта С₄ розраховується аналогічно:

,

.

Якщо за інших однакових умов ціна одиниці продукції Д зменшиться до 3 ум. од. або збільшиться до 6 ум. од., то оптимальний план виробництва продукції на підприємстві не зміниться

(Х ^* = (0; 0; 35; 45)).

Якщо коливання ціни продукції виходять за визначені межі, то план

Х ^* = (0; 0; 35; 45)

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

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

Для даної задачі побудовано блок схему (Додаток А), а також реалізовано її за допомогою програми (Додаток Б).



ВИСНОВКИ

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

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

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

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



СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Акулич И.А. Математическое програмирование в примерах и задачах: Учеб. пос. для студ. эконом. спец. / И.А. Акулич - М. : Высшая школа, 1986. - 319 с.

2. Боровик О.В. Дослідження операцій в економіці. Навч. пос. / О.В. Боровик, Л.В. Боровик - К. : ЦУЛ, 2007. - 424 с.

3. Вагнер Г. Основы исследования операций: в 3 т. / Г. Вагнер - М. : Мир, 1972. - Т.1. - 336 с.

4. Дацко М.В. Дослідження операцій. Навч. пос. / М.В. Дацко, М.М. Карбовник - Львів : “ПАЇС”, 2009. - 288 с.

5. Дегтярев В.И. Исследование операций: Уч. для вузов по спец АСУ / В.И. Дегтярев - М. : Высшая школа, 1986. - 320 с.

6. Зайченко Ю.П. Дослідження операцій / Ю.П. Зайченко - Київ : ЗАТ “Віпол”, 2000. - 688 с.

7. Исследование операций в экономике: Учебное пособие / Под ред. Н.Ш. Кремера - М. : Банки и биржи, ЮНИТИ, 2001. - 407 с.

8. Исследование операций: в 2 т. / под ред. Дж.Моудера, С.Элмаграби. - М. : Мир, 1981. - Т. 1: Методологические основы и математические методы. - 1981. - 716 с.

9. Калихман И.Л. Сборник задач по математическому програмированию / И.Л. Калихман - М. : Высшая школа, 1986. - 270 с.

10. Кутковецький В.Я. Дослідження операцій: Навчальний посібник / В.Я. Кутковецький - Київ : Вид-во ТОВ “Видавничий дім “Професіонал”, 2004. - 350с.

11. Наконечний С.І. Математичне програмування: Навч. посіб. / С.І. Наконечний, С.С. Савіна - К. : КНЕУ, 2003. - 452с.

12. Охріменко М.Г. Дослідження операцій: Навч. пос. / М.Г. Охріменко, І.Ю. Дзюбан - К. : Центр навч. л-ри, 2006. - 184 с.

13. Таха, Хэмди А. Введение в исследование операций / Хэмди А. Таха - М. : Мир, 2005. - 912с.

14. Ульянченко О.В. Дослідження операцій в економіці. Підручник для студ. вузів / О.В. Ульянченко - Харків : Гриф, 2002. - 580 с.

15. Федоренко І.К. Дослідження операцій в економіці: Підручник / І.К. Федоренко, О.І. Черняк - К. : Знання, 2007. - 558 с.

16. Тынкевич М.А. Экономико-математические методы (исследование операций). Изд. 2, испр. и доп. - Кемерово, 2000.-177 c.



ДОДАТОК А. СПРОЩЕНА БЛОК-СХЕМА АЛГОРИТМУ

Частина 1. - Зчитування і перевірка коректності введених параметрів ЗЛП

Частина 2. - Зведення ЗЛП до стандартизованого вигляду прямої задачі



Частина 3. - Побудова Двоїстої задачі

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



ДОДАТОК Б. ЛІСТИНГ ПРОГРАМИ

unit UnitMain;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ComCtrls, Buttons, ExtCtrls, Menus, Grids, Math;

type

TForm1 = class(TForm)

MainMenu1: TMainMenu;

N1: TMenuItem;

N_VVID: TMenuItem;

N3: TMenuItem;

Panel_ROZMIRU: TPanel;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Edit_N: TEdit;

Edit_M: TEdit;

BtnRozmiryEnter: TSpeedButton;

UpDown1: TUpDown;

UpDown2: TUpDown;

CBox_EXTREMUM: TComboBoxEx;

Panel_A: TPanel;

btn_BuildDuo: TSpeedButton;

SGRD_A: TStringGrid;

PanelDUO: TPanel;

MemoDUO: TMemo;

N2: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N_PZ_Standart: TMenuItem;

N_DZ_standart: TMenuItem;

N8: TMenuItem;

N_makePZ: TMenuItem;

N_makeDZ: TMenuItem;

STB2: TStringGrid;

N6: TMenuItem;

N_PSM: TMenuItem;

N_PSM_DZ: TMenuItem;

procedure N_VVIDClick(Sender: TObject);

procedure BtnRozmiryEnterClick(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure btn_BuildDuoClick(Sender: TObject);

procedure FormResize(Sender: TObject);

procedure N4Click(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure N_PZ_StandartClick(Sender: TObject);

procedure N_DZ_standartClick(Sender: TObject);

procedure N_makeDZClick(Sender: TObject);

procedure N_makePZClick(Sender: TObject);

procedure N_PSMClick(Sender: TObject);

procedure N_PSM_DZClick(Sender: TObject);

private

{ Private declarations }

public

function ReadReal_A(i,j:integer):real; // функція для уникнення помилок вводу при зчитуванні даних

function ReadZnak(i,j:integer):integer;

{ Public declarations }

end;

var

Form1: TForm1;

n,m:integer;

extremum_max, ERROR :boolean;

// оголошення одно- та двовимірних динамічних масивів

C,B: array of real;

A: array of array of real;

Znak: array of integer; { масив знаків нерівностей обмежень

0 - рівне (=)

1 - менше рівне (<=)

2 - більше рівне (>=)}

X_nevid: array of boolean; { масив значень

1 - Xj>=0

0 - обмеження не накладається}

implementation

{$R *.dfm}

function TForm1.ReadZnak(i,j:integer):integer;

...