36107

МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ

Конспект

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

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

Украинкский

2013-09-21

1.78 MB

17 чел.

МІНІСТЕРСТВО ОСВІТИ  І НАУКИ УКРАЇНИ

ОДЕСЬКА НАЦІОНАЛЬНА АКАДЕМІЯ ХАРЧОВИХ ТЕХНОЛОГІЙ

Кафедра КС і УБП

КОНСПЕКТ ЛЕКЦІЙ

З КУРСУ «МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ»

для студентів професійного  напрямку

6.030504, 6.030509, 6.030510, 6.030601денної й заочної форм навчання

Затверджено

Методичною радою ОНАХТ

протокол № 10

від 24.06.09

Одеса ОНАХТ 2009


    Конспект лекцій  з курсу "Математичне програмування" для студентів професійного напрямку 6.030504, 6.030509, 6.030510, 6.030601, денної й заочної форм навчання  / Укладачі: В.Г.Візінг, Н.О. Макоєд -Одеса: ОНАХТ, 2009.- 60 с.

Укладачі           В.Г. Візінг, канд. фіз.-мат. наук, доцент,

                         Н.О. Макоєд, канд. пед. наук, доцент.

                        

Відповідальний за випуск   завідувач кафедрою КС і УБП  канд. фіз-мат. наук, доцент В.Е. Волков                           

                        

                      

           

Відповідальний за випуск

завідувач кафедрою КС і УБП канд. ф-м. наук, доцент  Волков В.Е.

ВСТУП

 

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

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

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

Поняття оптимальності й критерію зв'язані між собою. Застосування терміну "оптимальний" коректне лише при вказуванні критерію.

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

Математичне програмування – розділ прикладної математики, в якому розглядаються методи вирішення економічних задач,  пов'язаних з вибором найкращого варіанта планування. Термін «програмування» слід розуміти як вибір програми, плану.

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

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

Основна робота з математичного програмування була написана в 1939 році радянським математиком Л.В. Канторовичем. Створення ЕОМ дало потужний поштовх розвитку математичного програмування. У теперішні  часи ця область перебуває в стадії розвитку.

 

1.РІШЕННЯ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ МЕТОДОМ ГАУСА - ЖОРДАНА

1.1. Основні поняття

Система m лінійних рівнянь із n невідомими має такий вигляд:

 

 

Тут хj ( j=1, n ) – змінні ( або невідомі) системи, аij ( i =1,m; j = 1,n ) – коефіцієнти при змінних,   вi ( i =1,m  ) – вільні члени.

Рішенням системи ( І.І)  називається всякий набір значень   змінних х1, х2, …, хn, при якому всі рівняння перетворюються в тотожності. Система називається сумісною, якщо вона має хоча б одне рішення, і несумісною – у протилежному випадку.

 Наприклад, система

сумісна, тому що вона має, зокрема, таке рішення:

х1 = 1;  х2 = 2;  х3 = 0 . Система ж    

несумісна.

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

Нарешті якщо у системі є рівняння виду

0∙ х1 + 0∙ х2 + ... + 0∙ хn = 0, то таке рівняння можна вилучити, одержавши систему, рівносильну вихідній.

1.2. Приведення системи лінійних рівнянь до жорданової форми

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

Визначення. Жордановою формою системи (I.I) називається система лінійних рівнянь, що володіє наступними властивостями:

а) вона рівносильна системі (I.I)

б) у кожному рівнянні жорданової форми є така змінна, котра входить у це рівняння з коефіцієнтом 1,  а в інші рівняння - з коефіцієнтом 0.

Так, якщо системі (I.I) рівносильна наступній системі лінійних рівнянь:

                                    (1.2)

то (І.2) є жорданова форма для (I.I). При цьому змінні х1, х2,... ,хк називаються базисними, останні змінні хк+1,..., хn   називаються вільними. Жорданова форма завжди є сумісною системою лінійних рівнянь. Дійсно, система (І.2) має наступне рішення:

                (І.3)

Оскільки система (І.2) рівносильна системі ( І.І ) , то (І.3) є рішенням системи (І.І).

Таким чином, якщо для системи лінійних рівнянь  ( І.І ) існує жорданова форма, то ( І.І ) - сумісна система. Несумісна система  жорданової форми не має.

 Покажемо, що будь-яку сумісну систему можна привести до жорданової форми. Це досягається методом Гауса-Жордана, який полягає в наступному.

Розглянемо перше рівняння системи (І.І). Виберемо в ньому змінну, коефіцієнт при якій відмінний від нуля. Припустимо, що а11 0. Поділимо рівняння на а11.

 Одержимо рівняння

                                               х1+ а12х2 + … + а1nхn = в1                        (І.4)

Будемо змінну х1 робити базисною в жордановій формі. Для цього її потрібно вилучити з інших рівнянь системи. Щоб вилучити х1 із другого рівняння, помножимо рівняння (І.4) на  -а21 і складемо із другим рівнянням. Потім вилучимо х1 із третього рівняння, для чого рівняння (І.4) помножимо на -а31 і складемо із третім рівнянням. Аналогічно змінна х1 вилучається з інших рівнянь. Таким чином, взявши за "ведуче" перше рівняння й провівши серію "жорданових вилучень", ми одержимо рівносильну (I.I) систему рівнянь, у якій x1 входить у перше рівняння з коефіцієнтом 1 , а в інші рівняння - з коефіцієнтом 0.

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

Якщо на деякому кроці виникне рівняння виду

          0∙ х1 + 0∙ х2 + ... + 0∙ хn =  0                                                 (І.5)

то вилучаємо його із системи. Якщо ж виникне рівняння виду

0∙ х1 + 0∙ х2 + ... + 0∙ хn = b ≠ 0, то це свідчить про несумісність вихідної системи  ( І.І), а несумісна система до жорданової форми не приводиться.

Отже , метод Гауса-Жордана сумісну систему лінійних рівнянь приводить до жорданової форми, а у випадку несумісної системи виявляє несумісність.

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

Очевидно, та сама система може мати багато різних жорданових форм.

Приклад. Привести до жорданової форми

Виберемо як ведуче перше рівняння, а як базисну змінну - змінну х1. Поділимо перше рівняння на (-1) (коефіцієнт при х1), одержимо:

Помножимо це рівняння на (+5) і додамо до другого рівняння, потім помножимо його на (-3) і додамо до третього рівняння.

Одержимо систему:

Тепер зробимо ведучим друге рівняння, а базисною змінною - змінну . Поділивши друге рівняння на (-8) і виключивши з першого й третього рівнянь, одержимо систему:

Нарешті, у третьому рівнянні вибираємо за базисну змінну . Поділимо це рівняння на (-1) і виключимо  з інших рівнянь. Одержимо жорданову форму:

Змінні є базисними, змінна - вільною.

1.3. Поняття загального, часного й базисного рішень

.

Нехай система (І.І) представлена в жордановій формі (1.2). Виразимо базисні змінні через вільні.

                                    (1.6)

(1.6) називається загальним рішенням системи (I.I).

Якщо вільним змінним додати будь-які числові значення й обчислити значення базисних змінних із системи (1.6), то вийде рішення вихідної системи, яке має назву часне. Часне рішення називається базисним, якщо вільні змінні приймають нульові значення. Рішення (1.3) є базисним.

У прикладі загальне рішення таке:

 

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

то система має єдине рішення; воно є й загальним, і часним , і базисним. Якщо ж k‹n , тобто жорданова форма містить вільні змінні, то система має нескінченно багато рішень.

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

2.І. Приклад задачі лінійного програмування - задача про використання обладнання.

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

Таблиця 2.1.

Вироби

верстати

А

В

Резерви часу (у годинах)

I

Витрати часу на виробництво одиниці виробу (у годинах)

2

3

30

II

4

2

40

III

3

4

60

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

6

7

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

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

побудова економіко-математичної моделі;

вирішення отриманої математичної задачі яким-небудь математичним методом;

впровадження результату вирішення в практику.

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

Побудуємо економіко-математичну модель задачу про використання обладнання.

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

max

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

2.2. Задача про використання сировини

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

Підприємство випускає продукцію n видів , на виготовлення якої витрачається сировина m видів , запаси котрої на підприємстві дорівнюють відповідно . Відомі витрати сировини Si на виробництво одиниці продукції (i = ; j = ). Вартість одиниці продукції  дорівнює (j = ). Потрібно скласти такий план випуску продукції, при якому прибуток від реалізації продукції був би  найбільшим.

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

Нехай - кількість одиниць продукції  (j = ).

Математична модель має вигляд:

f = →  max

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

                                        ( 2.0)

2.3. Задачі складання раціону (задача про дієту)

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

Позначимо через  xj кількість кілограмів корму j-го виду.

Очевидно, математична модель задачі така.

f = →  min

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

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

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

де - дійсні числа.

Наприклад, співвідношення  2х -  ≤ 1  або    ≥  0 є

лінійними, а   співвідношення    ≥ 3  або sin x1 ≤  не є лінійними.                                                                                              

Загальна постановка задачі лінійного програмування (ЗЛП) полягає в наступному.                                                   

Дано деяку лінійну функцію

f = n                                                             (2.1)

і деяка система лінійних обмежень, накладених на змінні :

                                                      (2.2)

Потрібно знайти такі значення змінних, які

задовольняли б обмеженням (2.2) і при цьому  обертали б в оптимум (max і min) функцію (2.1).

Функція (2.1) називається цільовою. Кожний набір значень змінних, при яких задовольняються обмеження (2.2), називається припустимим рішенням або припустимим планом ЗЛП. Сукупність  всіх  припустимих  рішень називається  областю припустимих рішень (ОПР).

Наведені  в  параграфах  2.1,   2.2,   2.3  задачі є задачами  лінійного програмування.

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

Говорять, що ЗЛП розв'язна, якщо вона має оптимальний план. У протилежному випадку задача називається нерозв'язною.

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

а)  ОПР порожня;

б)  ОПР непорожня, але цільова функція не обмежена на ОПР зверху, якщо в ЗЛП шукається її максимум, або - не обмежена знизу, якщо в ЗЛП шукається мінімум цільової функції.         

Наприклад, задача: f = min

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

                                

нерозв'язна через порожнечу ОПР.

Задача ж  f = max  при обмеженні

нерозв'язна через те, що цільова функція не обмежена зверху на ОПР. (Щоб переконатися в цьому, розгляньте такі припустимі рішення : і т.д.).

2.5. Геометричний метод вирішення ЗЛП

У випадку, коли число змінних у ЗЛП дорівнює двом, завдання можна вирішити геометрично. Розглянемо приклади.

         Приклад 1

 f = max

Кожне припустиме рішення ЗЛП будемо зображувати точкою координатної площини. Побудуємо ОПР (рис. 2.1). Розглянемо перше лінійне обмеження . Сукупність точок площини, що задовольняють цьому обмеженню, являє собою напівплощину, обмежену прямою . Спочатку побудуємо цю граничну пряму (її можна побудувати по двох точках: (0,6) і (9,0). Ця пряма розіб'є площину  на дві напівплощини. Щоб вирішити питання про те, яку із цих двох напівплощин визначає нерівність , візьмемо в одній з напівплощин яку-небудь точку, що не лежить на граничній прямій, і підставимо її координати в нерівність. Наприклад, за таку точку  візьмемо початок координат - точку (0,0). Оскільки , то напівплощина, обумовлена нерівністю , містить точку (0,0). Аналогічно знаходимо напівплощини, обумовлені іншими обмеженнями. Далі визначимо ОПР як загальну частину отриманих напівплощин. Одержимо опуклий багатокутник

Рис.2.1.

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

f = ,то кожна лінія рівня має вигляд . Бачимо, що при різних значеннях параметра С маємо паралельні прямі. Побудуємо, наприклад, дві лінії рівня, поклавши С = 4 і С = 8. Відзначимо стрілкою напрямок, у якому переміщається лінія рівня при збільшенні С. Пересуваючи лінію рівня в зазначеному напрямку, знайдемо точку ОПР, у якій С має найбільше значення. Це буде точка А. Вона є результатом перетинання двох прямих:  і

Для знаходження координат точки А вирішимо систему

Одержимо  оптимальне  рішення

Приклад 2.  f = min

 

       

рис. 2.2.

У цьому прикладі напівплощини, обумовлені лінійними обмеженнями, не мають загальних точок. Тому ЗЛП нерозв'язна через порожнечу ОПР.

Приклад 3. f =

У даному прикладі   (рис.2.3) ОПР - опукла необмежена багатокутна область.

рис. 2.3.

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

Приклад 4.  f = 

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

Наприклад,

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

обладнання,  що розглядалася в параграфі 2.1. Її математична модель

 f =

Побудуємо ОПР (рис 2.4).  Потім проведемо лінію  рівня . Укажемо стрілкою напрямок, у якому переміщається лінія рівня із збільшенням C. Максимум цільової функції на ОПР досягається в точці А. Для відшукання координат точки А вирішимо систему:

 

рис.2.4.

Звідси

Відповідь. Оптимальний план такий: виробів А потрібно робити 7,5 одиниць, виробів В -5 одиниць; при цьому прибуток буде дорівнювати 80 грошовим одиницям.

Геометричний метод можна використовувати для вирішення ЗЛП із числом змінних n = 3. При більшому числі змінних ЗЛП не допускає наочного геометричного вирішення. Разом з тим для довільного числа змінних справедливі твердження:

1)  область припустимих рішень являє собою опуклий  багатогранник;

2) якщо ЗЛП розв'язна, то оптимальне рішення досягається в одній з вершин опуклого багатогранника.

2.6. Канонічний вигляд ЗЛП

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

Для однаковості запису ЗЛП уводиться так звана канонічна форма запису.

Говорять, що ЗЛП записано в канонічній формі, якщо вона має такий вигляд:

                                       (2.3)

                                  

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

    1)   потрібно мінімізувати цільову функцію;

    2)    всі   лінійні   обмеження,  крім   вимог невід’ємності  змінних, мають вигляд рівностей;

  1.  на всі змінні накладені вимоги  невід’ємності .

Покажемо, що будь-яку ЗЛП можна привести до канонічного виду.

1) Якщо в ЗЛП потрібно максимізувати цільову функцію f, то покладемо g = - f і зажадаємо мінімізувати функцію g. Вийде нова ЗЛП, що еквівалентна вихідній в тому розумінні, що кожне оптимальне рішення вихідної задачі буде оптимальним рішенням нової задачі  і навпаки.

2)  Припустимо, що в ЗЛП є лінійне обмеження виду

. Замінимо таке обмеження наступними двома обмеженнями:

де z - нова змінна, котра в цільову функцію вводиться з коефіцієнтом  0 (інакше кажучи, змінна z не вводиться в цільову функцію). Значення змінної z можна не враховувати після вирішення нової задачі.

Аналогічно, обмеження виду  заміняється двома обмеженнями:

3) Припустимо, що в ЗЛП не до всіх змінних пред'явлена вимога невід’ємності. Тоді кожну змінну , на яку не накладена вимога невід’ємності , представимо у вигляді різниці двох невід’ємних  змінних:

                                              (2.6)

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

Зазначеними прийомами будь-яка ЗЛП приводиться до канонічного виду.

Приклад. Привести до канонічного виду

Проробимо описані дії.

Тепер одержимо ЗЛП у канонічному виді:

2.7. Поняття опорного плану ЗЛП.

Нехай ЗЛП задана в канонічному вигляді (2.3 - 2.5). Припустимо, що система рівнянь (2.4) приведена до жорданової форми з невідємними   правими частинами:

               (2.6)

де .

Дорівнявши до нуля вільні змінні, одержимо базисне рішення системи (2.4)

                        (2.7)

У силу умови набір значень змінних (2.7) задовольняє й обмеженням (2.5). Тому (2.6) є припустимим рішенням ЗЛП.

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

Виявляється, що якщо ОПР зобразити геометрично, то кожний опорний план ЗЛП відповідає вершині багатогранника. Тому справедлива наступна теорема.

Якщо ЗЛП розв'язна, то існує оптимальний опорний план.

3. СИМПЛЕКСНИЙ МЕТОД ВИРІШЕННЯ ЗЛП

3.1. Загальна характеристика й основні етапи симплекс - методу

Основоположниками симплекс-методу є радянський математик Л.В. Канторович і американський математик Дж. Данциг.

Симплекс-методом можна вирішити будь-яку ЗЛП або виявити її нерозв'язність. Багато спеціальних класів ЗЛП можна вирішити іншими, більш ефективними для цих класів методами. Однак перевага симплекс-методу - його універсальність. Майже для всіх ЕОМ розроблені стандартні програми для вирішення ЗЛП симплекс - методом.

Опишемо загальну ідею симплекса-методу.

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

При вирішенні ЗЛП симплекс-методом можна виділити наступні етапи:

1) приведення ЗЛП до канонічного вигляду;

2) приведення системи лінійних рівнянь до жорданової форми з невідємними правими частинами з одночасною перевіркою на нерозв'язність ЗЛП через суперечливість системи лінійних обмежень;

3) дослідження опорного плану на оптимальність;

4) дослідження ЗЛП на нерозв'язність через необмеженість знизу на ОПР цільової функції;

5) перехід до нового, "кращого" опорного плану.

3.2. Табличний вигляд ЗЛП. Симплекс - таблиці

Для скорочення й упорядкування записів при вирішенні ЗЛП симплекс-методом використовуються так звані симплекси-таблиці. Щоб скористатися симплекс-таблицею, ЗЛП потрібно привести до табличного вигляду. Робиться це так.

Нехай ЗЛП записана в канонічному вигляді (2.3-2.5). Для приведення ЗЛП до табличного вигляду систему (2.4) слід спочатку привести до жорданової форми з невідємними правими частинами. Припустимо, що ця жорданова форма має вигляд (2.6). Виразимо з (2.6) базисні змінні через вільні:

                                              (3.1)       

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

                                                     (3.2)

У табличному вигляді цільова функція записується так:

                                                    (3.3)

де      .

Відзначимо наступні особливості табличного вигляду ЗЛП:

а) система лінійних рівнянь приведена до жорданової форми з невідємними правими частинами;

б)  із цільової функції виключені базисні змінні й вона записана у формі (3.3).

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

                                   (3.4)

Тоді заповнена симплекс-таблиця виглядає так.

Таблиця 3.1.

Базис

Змінні

Вільні члени

...

xk

...

1

0

...

0

...

0

1

...

0

...

.

.

.

.  .

. .

...

. .

 .  .

 .  .

 ...

.  .

.  .  .

0

0

...

1

 ...

f

0

0

...

0

....

                                                                                                                                                  Опорний план ЗПЛ:  ..., називається  опорним  планом, що  відповідає цій  симплекс-таблиці.  Як видно з формули (3.2), значення цільової функції при цьому опорному плані дорівнює γ0.

Розглянемо приклад. Привести до табличного вигляду наступну ЗЛП і заповнити симплекс-таблицю:

Спочатку ЗЛП потрібно привести до канонічного вигляду. Для цього функцію f потрібно замінити на - f:

 

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

Табличний вигляд ЗЛП такий:

 

Заповнимо симплекс-таблицю (для скорочення записів перший стовпчик названий "Б", останній стовпчик - "Q").

Таблиця 3.2.

Б

Q

4

1

-5

0

8

-7

0

-2

1

4

-f

-4

0

8

0

-20

Опорний план, що відповідає цій симплекс-таблиці, має вигляд:

. Значення функції - f при цьому опорному плані дорівнює - 20.

3.3. Умова оптимальності опорного плану

Нехай є заповнена симплекс-таблиця. Сформулюємо умову оптимальності опорного плану.

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

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

Таблиця 3.3.

Б

Q

1

0

2

-1

3

2

0

1

2

0

-1

3

f

0

0

-5

-3

-1

6

Значення цільової функції при опорному плані, що відповідає симплекс-таблиці, дорівнює 6. Випишемо цільову функцію в табличному вигляді: , звідки . Оскільки при будь-якому припустимому рішенні ЗЛП змінні приймають тільки невід’ємні значення, то з останнього запису цільової функції видно, що її значення в будь-якій точці ОПР не менше 6. Отже, мінімальне значення цільової функції на ОПР дорівнює 6 і воно досягається при опорному плані, що відповідає симплекс-таблиці,  .

3.4. Умова нерозв'язності ЗЛП через необмеженість знизу на ОПР цільової функції

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

Умова нерозв'язності формулюється так.

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

Для обґрунтування знову скористаємося прикладом.

Таблиця 3.4.

Б

Q

1

0

2

5

-2

2

0

1

-3

0

-1

3

f

0

0

3

-1

2

4

Стовпець у нижньому рядку містить додатне число, а в інших рядках - недодатні числа. Доведемо нерозв'язність ЗЛП.

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

Нехай а - довільне додатне число. Очевидно, ЗЛП має наступне припустиме рішення: .  Обчислимо значення цільової функції при цьому припустимому рішенні. З таблиці 3.4 маємо:

. При зазначеному припустимому рішенні f = 4 - 2а. Звідси бачимо, що значення цільової функції може стати як завгодно малим при досить великому  значенні  а. Інакше кажучи, цільова функція не обмежена знизу на ОПР. Отже, ЗЛП нерозв'язна.

3.5. Перехід до нового опорного плану.

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

1)  новий базис повинен бути як і раніше припустимим, тобто праві частини відповідної жорданової форми повинні бути як і раніше невід’ємними;

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

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

Правило вибору генерального елемента.

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

Проілюструємо це правило на прикладі.

Таблиця 3.5.

Б

Q

1

0

0

2

-1

4

0

1

0

3

4

8

0

0

1

-2

6

3

F

0

0

0

7

5

12

Як генеральний стовпець можна вибрати або стовпець , або стовпець . Виберемо  (найчастіше вибирають той стовпець, у якого внизу більше додатне число). Тепер перейдемо до вибору генерального рядка. Для цього розглянемо два рядки - і .  Складаємо відносини 4:2 і 8:3. Менше значення має відношення 4:2, тому перший рядок вибираємо генеральним. Отже, генеральний елемент дорівнює 2 - він стоїть на перетинанні стовпця й рядка .

Після вибору генерального елемента потрібно перейти до нового опорного плану, при якому змінна стає базисною, а змінна  х1- вільною. Коефіцієнт при  в новій жордановій формі повинен  дорівнювати 1. Тому перший рядок таблиці 3.5 ділиться на 2. Помноживши потім отриманий перший рядок на (-3) і додавши до другого рядка, виключимо  із другого рівняння. Аналогічно, за допомогою жорданової процедури виключаємо  із третього рівняння й із цільової функції (останнє вимагає табличний вигляд ЗЛП). У результаті одержимо наступну таблицю.

Таблиця 3.6

Б

Q

0

0

1

2

1

0

0

3

2

1

0

1

0

5

7

f

0

0

0

-2

Звернемо увагу, що в стовпці Q у перших трьох рядках стоять невід’ємні числа, тобто новий базис як і раніше, є припустимим. Це не випадковий факт: так буде завжди при точному дотриманні правила вибору генерального  рядка. Далі, значення цільової функції при новому опорному плані дорівнює -2, при старому воно  дорівнювало 12. "Поліпшення" опорного плану гарантує правило вибору генерального стовпця. Хоча ці факти ми суворо не доводимо, потрібно мати на увазі, що вони завжди мають місце.

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

  

3.6. Табличний симплекс-алгоритм

 

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

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

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

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

4. Заповнюємо  нову симплекс-таблицю, у якій:

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

    2) генеральний рядок ділимо на генеральний елемент;

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

Приклад I.  Вирішити симплекс-методом

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

x3=10 - 2x1 - x2

x4= 8 - x1 - 2x2

і підставимо в цільову функцію

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

Тепер маємо табличний вигляд ЗЛП:

Заповнимо першу симплекс-таблицю     

  

Таблиця 3.7

Б

Q

2

1

1

0

10

1

2

0

1

8

F

10

6

0

0

28

У таблиці 3.7 умови оптимальності й нерозв'язності не виконуються. Виберемо за генеральний стовпець , у якого в нижньому рядку стоїть додатне число. Потім, порівнюючи відносини 10:3 і 8:1, виберемо перший рядок як генеральний. У таблиці  генеральний елемент  2 .

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

Таблиця 3.8

Б

  

Q

1

0

5

0

1

3

F

0

1

-5

0

-22

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

Таблиця 3.9

Б

Q

1

0

4

0

1

2

F

0

0

-24


Таблиця 3.9 задовольняє умові оптимальності.

Відповідь: оптимальний план

Мінімальне значення цільової функції fmin = - 24.

Приклад 2. Вирішити симплекс-методом:

Насамперед, ЗЛП потрібно привести до канонічного вигляду

 

Тепер приводимо ЗЛП до  табличного  вигляду.  Бачимо,   що  система рівнянь записана в жордановій формі з невід’ємними правими частинами ( і z - базисні змінні).    Однак у цільову функцію входить базисна змінна . Маємо:

Отже, табличний вигляд ЗЛП такий:

Заповнюємо симплекс-таблицю (таблиця 3.10).

Таблиця 3.10

Б

z

Q

-1

1

1

0

1

z

1

-2

0

1

4

g

2

0

0

0

-1

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

Таблиця 3.11

Б

z

Q

0

-1

1

1

5

z

1

-2

0

1

4

g

0

4

0

-2

-9

Звернемо увагу на стовпець . Він показує, що цільова функція g не обмежена знизу на ОПР. Згадуючи, що g =-f, одержуємо відповідь.

Відповідь: ЗЛП нерозв'язна через необмеженість  зверху  на ОПР цільової функції f.

Приклад 3. Вирішимо симплекс-методом задачу про використання обладнання, поставлену в параграфі 2.1. Саме там приводилася її математична модель

                                       

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

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

Заповнюємо симплекс-таблицю (таблиця 3.12).

Таблиця 3.12

Б

Q

2

3

1

0

0

30

4

2

0

1

0

40

3

4

0

0

1

60

G

6

7

0

0

0

0

Умови оптимальності й нерозв'язності не виконуються. Стовпець (у нижньому рядку якого стоїть найбільше додатне число) виберемо генеральним. Порівнюючи відносини 30:3, 40:2, і 60:4, обираємо перший рядок як генеральний. Поділивши його на 3 і зробивши за допомогою жорданової процедури нулі у всіх інших рядках генерального стовпця, після заміни базисної змінної на змінну , одержимо таблицю 3.13.

Таблиця 3.13

Б

Q

x2

1

0

0

10

z2

0

1

0

20

0

0

1

20

g

0

0

0

-70

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

Таблиця 3.14

Б

Q

0

1

0

5

1

0

0

0

0

1

g

0

0

- 2

0

-80

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

Оскільки змінні не фігурували у вихідній постановці задачі, крім того, функція f = - g у вихідній постановці максимізувалася, то можна записати наступне оптимальне рішення вихідної задачі                                          

Повертаючись до змістовної постановки (параграф 2.1), доходимо наступного висновку: прибуток підприємства буде максимальним (80 грош.од.), якщо виробів А випустити 7,5 од., виробів В випустити 5 од.

Це ж завдання ми вирішили геометрично (див. параграф 2.5, приклад 5) і, природно, одержали саме такий  результат.

3.7. Відшукування початкового опорного плану ЗЛП методом штучного базису

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

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

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

Нехай ЗЛП записана в канонічному вигляді.

   (3.5)

 

Насамперед потрібно зробити невід’ємними праві частини системи (3.6). Цього можна домогтися множенням на (-1) рівнянь із відємними       правими частинами. Отже, будемо вважати, що

               (3.8)

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

        (3.9)

 

Змінні називаються штучними. Вони складають базис у жордановій формі (3.10), який називається штучним базисом.

ОПР допоміжної задачі непорожня, тому що їй належить наступний набір значень змінних:  (див.(3.10),(3.11),(3.12)(3.8)). Цільова функція (3.9), що є сумою невідємних змінних, обмежена знизу на ОПР нулем: . Таким чином, для допоміжної задачі жодна із двох причин нерозв'язності не має місця, тому допоміжна задача розв'язна. Оскільки  система рівнянь записана в жордановій формі з невідємними правими частинами, то ми можемо привести допоміжну задачу до табличного вигляду й вирішити симплекс-методом. Після вирішення можуть появитися два випадки.

1.                                                                (3.I3)

Покажемо, що тоді вихідна задача (3.5 - 3.7) нерозв'язна через порожнечу ОПР. Дійсно, нехай, всупереч цьому твердженню, є припустиме рішення  вихідної задачі. Тоді набір значень змінних  

є, мабуть, припустимим рішенням допоміжної задачі. Значення цільової функції F при цьому припустимому рішенні дорівнює 0, що суперечить (3.13).

            2.                                                              (3.14)

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

а) серед базисних змінних немає штучних. Тоді вилучаємо з жорданової форми всі члени, що містять штучні вільні змінні, одержимо жорданову форму з невід’ємними  правими частинами для вихідної задачі;

б) серед базисних змінних є штучні. З огляду на (3.9) і (3.14), можна стверджувати, що в оптимальному плані значення всіх штучних змінних рівні 0. Тому права частина кожного рівняння, що містить штучну змінну за базисну,  дорівнює 0, тобто таке рівняння можна записати так:

                                  (3.15)

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

                                                                       (3.16)

За допомогою жорданової процедури вилучимо xj з інших рівнянь системи. Оскільки права частина рівняння (3.16) дорівнює 0, то праві частини інших рівнянь після вилучення xj не зміняться й залишаться  невідємними .

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

Приклад I. Вирішити симплекс-методом

Задача записана в канонічному вигляді, однак права частина другого рівняння системи відємна. Тому систему рівнянь перепишемо так:

Запишемо допоміжну задачу

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

Табличний вигляд допоміжної задачі такий:

Побудуємо першу симплекс-таблицю (таблиця 3.15)

Таблиця 3.15

Б

Q

1

-1

1

1

0

3

-2

5

1

0

1

1

F

-1

4

2

0

0

4

Перейдемо до нової симплекс-таблиці (таблиця 3.16)

Таблиця 3.16

Б

Q

0

1

1

0

F

0

0

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

Таблиця 3.17

Б

Q

1

0

2

0

1

1

F

0

0

0

-1

-1

0

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

Опустивши штучні змінні, одержимо жорданову форму з невідємними правими частинами для вихідної задачі:

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

Складемо симплекс-таблицю для вихідної задачі (таблиця 3.18) і переходимо до наступної таблиці 3.1

Таблиця 3.18

Б

Q

1

0

2

0

1

1

F

0

0

1

                                    

  Таблиця 3.19

Б

Q

1

-2

0

0

1

1

F

0

-1

0

-1

Одержимо оптимальне рішення:

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

Приклад 2. Вирішити симплекс-методом

Складемо допоміжну задачу

Відомими прийомами приведемо її до табличного виду:

Заповнимо симплекс-таблицю (таблиця 3.20)

Таблиця 3.20

Б

Q

2

-1

1

1

0

2

4

-2

0

0

1

5

F

6

-3

1

0

0

7

Перейдемо до нової симплекс-таблиці (3.21)

Таблиця 3.21

Б

Q

1

0

1

0

0

-2

-2

1

1

F

0

0

-2

-3

0

1

Одержимо оптимальний план. Значення цільової функції при оптимальному плані . Тому вихідна ЗЛП нерозв'язна через порожнечу ОПР.

Цікаво відзначити, що система лінійних рівнянь вихідної ЗЛП сумісна  й приводиться до жорданової форми. Однак вона не приводиться до жорданової форми з невідємними правими частинами.

Зробимо ще одне корисне зауваження. У розглянутому прикладі 2 можна було б скласти більш просту допоміжну задачу:

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

3.8. Виродженість опорного плану. Зациклення

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

                                                                                  

Приклад. Нехай табличний вигляд ЗЛП такий:

Складемо першу симплекс-таблицю (таблиця 3.22).

Таблиця 3.22

Б

Q

1

0

1

-1

0

0

1

2

3

10

f

0

0

2

1

4

Опорний план, що відповідає цій симплекс-таблиці, є виродженим, тому що значення базисної змінної  дорівнює 0. Перейдемо до нової симплекс-таблиці (табл.3.23)

Таблиця 3.23

Б

Q

1

0

1

-1

0

-2

1

0

5

10

f

-2

0

2

3

4

При новому опорному плані значення цільової функції залишилося колишнім: f=4.

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

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

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

  1.  ДВОЇСТІСТЬ У ЛІНІЙНОМУ ПРОГРАМУВАННІ

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

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

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

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

Сировина

Види продукції

Запаси

сировини

П 1

П 2

П 3

П 4

Норми витрати сировини

1

2

5

5

3

80

2

7

2

3

4

90

3

5

4

6

7

100

Прибуток

14

10

15

12

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

Для запису математичної моделі задачі позначимо через xj кількість продукції Пj (j=1, 2, 3, 4). Математична модель задачі:

Сформулюємо тепер двоїсту задачу. Припустимо , що деяка організація вирішила купити у підприємства всю сировину. Покупець прагне установити ціни уi на одиницю сировини i-ro виду (i = 1, 2, 3, 4) так, щоб мінімізувати сумарну вартість сировини, що виражається величиною φ=80у1+90у2+100у3. При цінах, запропонованих покупцем, підприємство одержить за сировину, витрачену на виготовлення продукції П1, виторг 2y1+7у2+5у3. Підприємство погодиться на угоду з покупцем, якщо цей виторг буде не менше прибутку підприємства від виготовлення одиниці продукції П1, тобто якщо буде виконуватися умова 2y1+7у2+5у3≥14. Такого ж обмеження покупець змушений ураховувати й для всіх інших видів продукції. Таким чином, математична модель задачі, розв'язуваної покупцем, має вигляд:

Отримана задача є двоїстою для вихідної.

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

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

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

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

Задача 1.

 

Легко бачити, що до такого вигляду можна привести будь-яку ЗЛП. Двоїста задача для задачі 1 записуються так:

Задача 2.

Можна показати, що має місце принцип взаємної двоїстості: двоїстою до задачі 2 є задача 1. Таким чином, несуттєво, яку із задач 1 або 2 називати прямою, а яку двоїстою.

Приклад 1. Дана ЗЛП

 

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

Задачу потрібно привести до вигляду, в якому записана задача 1. Всі обмеження, крім вимог невід’ємності  змінних, повинні бути нерівностями вигляду ≤. Першу нерівність помножимо на (-1). Потім замінимо рівність – x1+x2=2 двома нерівностями -x1+x2≤2 і -x1+x2≥2; другу із цих нерівностей помножимо на (-1). У результаті ЗЛП прийме вигляд:

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

 

  1.  Теореми двоїстості

Приведемо без доказу наступні дві теореми.

Перша теорема двоїстості. Пряма задача розв'язна тоді й тільки тоді, коли розв'язна двоїста. При цьому fmaxmin.

Друга теорема двоїстості. Для того, щоб два припустимих рішення x1', x2',...,xn' і у1', у2',…,ym' пари двоїстих задач були оптимальними, необхідно й достатньо, щоб ці рішення задовольняли умовам

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

Приклад 2. Дана задача

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

Звернемо увагу, що дана задача записана у формі (4.4) - (4.6). Оскільки має місце принцип взаємної двоїстості, то будемо записувати двоїсту задачу у формі (4.1) - (4.3). Одержимо:

Вирішимо геометрично двоїсту задачу. Побудуємо на координатній площині граничні прямі (1) 8у1–5у2=11; (2) –у1+3у2=1; (3) –2у1–7у2=–7; знаходимо напівплощини, визначаємо ОПР, а потім знаходимо на ОПР оптимальну точку А (див. рисунок 4.1). Для відшукання координат точки А вирішуємо систему рівнянь

Одержуємо у1=2, у2=1. Підставивши ці значення змінних у цільову функцію, одержимо φmax=7.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 4.1.

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

Підставивши у1=2, у2=1, після очевидних перетворень одержимо систему

Вирішивши отриману систему, знайдемо  х1= 9/19;   х2=34/19; х3=0; fmin= 7.

  1.  ТРАНСПОРТНА ЗАДАЧА

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

  1.  Задача про перевезення.

Є m пунктів відправлення (ПВ) А1, А2,..., Аm, у яких зосереджений деякий вантаж у кількостях а12,...,аm і n пунктів призначення ( ПП.) В1, В2,..., Вn, у які потрібно завезти цей вантаж у кількостях b1,b2,...,bn , причому

  . Відомі вартості cij перевезення одиниці

вантажу з пунктів Аi у пункти Вj ( ; ). Передбачається, що

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

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

Потрібно скласти такий план перевезень із пунктів Аi у пункти Вj, при якому витрати на перевезення були б найменшими.

Вихідні дані задачі звичайно подаються у вигляді транспортної таблиці (табл. 5.1).

Таблиця 5.1

                Пп

Пв                           

В1

В2

. . .

В3

Запаси

А1

с11

        

С12

        

. . .

С1n

        

а1

А2

С21

        

С22

        

. . .

С2n

        

а2

. . .

. . .

. . .

. . .

. . .

. . .

Аm

Сm1

        

Сm2

        

. . .

Сmn

        

аm

Потреби

в1

в2

. . .

вn

Вартості cij проставляються  в  правих  верхніх  кутах відповідних клітинок.

Складемо математичну модель задачі. Нехай xij – кількість вантажу, перевезеного з пункту Аi у пункт Вj. Цільова функція задачі  (загальна  вартість перевезень)  записується  в такий спосіб:

 

Систему обмежень записуємо, керуючись тим, що:

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

б) потреби пунктів призначення повинні бути задоволені;

в) перевезення можуть бути тільки невідємними.

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

 

Ми бачимо, що задача про перевезення є ЗЛП.

  1.  Загальна постановка транспортної задачі

Транспортною задачею  називається ЗЛП наступного вигляду:

Відзначимо наступну особливість транспортної задачі як ЗЛП спеціального вигляду: система рівнянь розбита на дві групи (5.2) і (5.3) так, що кожна змінна входить рівно в одне рівняння групи з коефіцієнтом 1.

Рівняння (5.2) називаються горизонтальними, рівняння (5.3) -вертикальними.

Будь-який набір значень змінних xij називається планом перевезень. План перевезень називається припустимим, оптимальним або опорним, якщо він є припустимим, оптимальним або опорним планом ЗЛП (5.1 - 5.4).

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

  1.  Відшукання початкового опорного плану перевезень

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

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

б) метод мінімального елемента в рядку;

в) метод мінімального елемента.

Нехай є транспортна задача (5.1 - 5.4). Хоча в системі (5.2 - 5.3) m+n рівнянь, опорний план містить тільки m+n–1 базисних змінних. Це пояснюється тим, що одне з рівнянь є наслідком інших, і в жордановій формі m+ n–1 рівнянь.

Опишемо метод відшукання вихідного опорного плану, так званим методом північно-західного кута.

Візьмемо  північно-західну клітинку (Аij). Проставимо в ній перевезення, що дорівнює min(ai,bj). Потім "зменшуємо" транспортну таблицю, керуючись правилами:

  1.  якщо ai < bj, то виключаємо з подальшого розгляду пункт відправлення (ПВ) Аi (і відповідний рядок); а в "меншій" таблиці потребу пункту призначення (ПП) Вj вважаємо  рівною   bj - ai ;
  2.  якщо  bj <ai, то виключаємо ПП Вj (і відповідний стовпець); в "меншій" таблиці вважаємо запас ПВ Аi рівним  ai - bj;
  3.  якщо ai = bj, то:

а) якщо в таблиці тільки один ПВ Аi і один ПП Вj, то алгоритм зупиняється;

б) якщо в таблиці один ПВ Аi і декілька ПП, то виключаємо Вj , вважаючи в "меншій" таблиці запас пункту Аi рівним 0;

в) якщо в таблиці один ПП Вj і декілька ПВ, то виключаємо Аi, вважаючи в "меншій" таблиці потребу пункту Вj, рівною 0;

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

Подібні кроки проробляють доти, поки не будуть виключені всі рядки й стовпці.   

У результаті застосування методу північно-західного кута деякі клітинки заповнені, деякі - ні. Заповнені клітинки називаються базисними (навіть якщо стоїть 0), незаповнені - вільними. Доведемо, що число базисних клітинок дорівнює m+ n-1.

Дійсно, на кожному кроці, крім останнього, виключаємо або рядок, або стовпець. На останньому кроці виключаємо і рядок, і стовпець. Оскільки число  рядків і стовпців у сумі дорівнює m+n, то  всього  буде  пророблено   m + n -1 кроків, а на кожному кроці заповнюється одна клітинка, відтак  число базисних клітинок дорівнюватиме  m + n -1.

Скористаємося прикладом (табл. 5.2).

Таблиця 5.2

                ПП

ПВ                           

В1

В2

В3

В4

Запаси

А1

10    4

  15    3

5

   7

25

А2

   2

5          1

0       8

      6

5

А3

0    4

      9

30   3

  15    2

45

Потреби

10

20

30

15

75=75

 

Розглянемо північно-західну клітинку транспортної таблиці - клітинку (1.1).  Проставимо  в ній  перевезення x11=min(a1,b1)=min(25,10)=10. Після  цього потребу пункту В1 повністю задоволено. Вилучаємо з таблиці перший стовпчик. В «меншій» транспортній таблиці запас пункту А1  покладемо рівним 25 – 10 = 15. Розглянемо північно-західну клітинку нової «меншої» таблиці. Керуючись саме таким же правилом, проставимо в ній перевезення x12= 15. Запас пункту А1 вичерпаний, і ми вилучаємо перший рядок. В отриманій транспортній таблиці потреба пункту В2  дорівнює 5. У північно-західну клітинку проставимо перевезення x22=min(5,5)=5. При цьому одночасно вичерпано  запас пункту А2  і задоволено потребу   пункту В2 .Переходячи до нової таблиці, не можна одночасно вилучити і стовпець, і рядок – потребує вилучення або стовпець, або рядок.  Виключимо з таблиці, наприклад, стовпець. Другій рядок ще не виключений з таблиці, тому запас пункту А2  покладемо рівним 0, тому у північно-західну клітинку ставимо перевезення x23=min(30,0)=0.  Після цього виключаємо із розгляду другій рядок. Далі покладемо x33=min(30,45)=30, виключаємо третій стовпець, проставляємо x34=15 .    Вихідний опорний план знайдено.  Базисними змінними є х11, х12, х22, х23, х33, х34. Значення базисних змінних в опорному плані дорівнюють перевезенням, проставленим у відповідних клітках. Опорний план є вироджений, тому що х23=0. Число базисних змінних дорівнює m+ n-1, тобто 3+4-1=6.

Метод північно-західного кута засвоюється дуже легко. Щоб переконатися в цьому, проробіть самостійно такий приклад (табл. 5.3.):

Таблиця 5.3

                Пп

Пв                           

В1

В2

В3

Запаси

А1

     2

     3

1

40

А2

   4

         2

      5

60

А3

3

      2

  6

50

Потреби

70

40

40

150=150

У вас повинен вийти результат, зафіксований у  таблиці 5.4.

                                                                                           

           Таблиця 5.4

Пп

Пв

В1

В2

В3

Запасы

А1

                 2

      40   -          

3

               1

     +            

40

А2

                 4

     30  +

  -                                           

               2

       30    -

    +

               5

60

А3

                 3

  +                 

               2

    - 10 +

               6

     - 40

50

Потребности

      70

     40

      40

150 = 150

      5.4. Цикли перерахування

5.4.1. Поняття циклу перерахування

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

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

Цикл називається означеним, якщо його вершинам позмінно приписано знаки "+" і "–".

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

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

У таблиці 5.4 пунктиром показано два цикли перерахування. Перший проходить через вільну клітинку (1,3), а другий – через вільну клітинку (3,1).

5.4.2. Максимально припустиме зрушення по циклу  перерахування

Зрушенням на величину h ≥ 0 по циклу перерахування називається збільшення на число h перевезень, що стоять у додатних вершинах циклу, і зменшення на число h перевезень, що стоять  у відємних  вершинах.

Оскільки в кожному рядку й кожному стовпці транспортної таблиці
кількість додатних вершин дорівнює кількості від
ємних
вершин циклу, то при зрушенні на будь-яке число h умови (5.2) і (5.3)
не порушуються. Щоб не порушувалася умова (5.4), величина зрушення
не повинна перевищувати мінімального перевезення, що стоїть у від
ємній
вершині циклу.

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

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

Розглянемо приклад (табл.5.4). Зробимо максимально припустиме зрушення по циклу перерахування, що проходить через вільну клітинку (1,3). Перевезення, що стоять у відємних вершинах циклу, дорівнюють 40, 30  і 40. Тому величина максимально припустимого зрушення h=min(40, 30, 40)=30. Після зрушення одержимо новий опорний план перевезень (табл.5.5).

     Таблиця 5.5.

Пн

По

В1

В2

В3

Запасы

А1

                 2

      10  -           

3

               1

    + 30          

40

А2

                 4

      60  

        

               2

     

               5

60

А3

                 3

            +           

               2

     40

               6

    _ 10

50

Потреби

      70

     40

      40

150 = 150

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

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

Звернемось до таблиці 5.5. Величина максимально припустимого зрушення по циклу перерахування дорівнює 10. З двох відємних клітинок (1,1)  і (3,3) тільки одна в результаті зрушення перетворюється у вільну. Зробивши вільною  клітинкою клітинку (3,3),  отримаємо   новий опорний план перевезення (табл. 5.6).

       Таблиця 5.6.

Пп

Пв

В1

В2

В3

Запасы

А1

                 2

       0             

3

               1

      40          

40

А2

                 4

      60  

        

               2

     

               5

60

А3

                 3

      10           

               2

     40

               6

    

50

Потреби

      70

     40

      40

150 = 150

Порівняємо сумарні вартості планів перевезень, зображених у
таблицях 5.4, 5.5, 5.6.

Таблиця 5.4: f = 2*40 + 4*30 + 2*30 + 2*10 + 6*40 = 520 гр. од.
Таблиця 5.5: f = 2*10 +1*30 + 4*60 + 2*40 + 6*10 = 430 гр. од.
Таблиця 5.6: f = 1*40 +4*60 + 3*10 + 2*40  = 390 гр. од.

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

5.4.3. Ціна циклу перерахування

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

Наприклад, ціна циклу перерахування, зазначеного в таблиці 5.4, дорівнює  (1+3)-(2+6)=4-8= - 4.

Ціна циклу перерахування - це збільшення цільової функції при зрушенні h=1 по циклу перерахування.

Якщо, наприклад, зробити одиничне зрушення по циклу перерахування таблиці 5.5, вийде план перевезень, сумарна вартість якого 430 - 4 = 426.

Має місце твердження: при зрушенні на величину h >= 0 по циклу перерахування з ціною γ , збільшення Δf цільової функції обчислюється за формулою

Δf   =  γ · h       (5.5)

У справедливості формули (5.5) можна переконатися  на прикладах таблиць   5.4, 5.5, 5.6.   З   формули    (5.5)   виходить,    що   при додатному   зрушенні  по   циклу  перерахування   з   відємною    ціною значення цільової функції зменшується. Тому пошук оптимального плану    перевезень    зводиться    до    виявлення    циклів    перерахування    з відємною ціною й здійснення максимально припустимих зрушень по них. А якщо циклів перерахування з відємною  ціною не виявиться?

Теорема:    Опорний   план   перевезень,   при   якому   всі   цикли перерахування мають відємні ціни, є оптимальний.

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

5.5. Потенціали

Нехай    у    транспортній    задачі     з    пунктами    відправлення А1, А2,..., Аm і пунктами призначення В1, В2,..., Вn є деякий опорний план перевезень. Поставимо кожному пункту відправлення Ai число αi ( ), кожному пункту призначення Вj - число βj ( ) так, щоб для кожної базисної клітинки (p,q) виконувалася рівність

αp + βq = cpq       (5.6)

Числа αi і βj називаються потенціалами пунктів відправлення й призначення відповідно.

Для відшукування потенціалів потрібно для кожної базисної клітинки скласти рівняння вигляду  (5.6)   і   вирішити   отриману систему m + n – 1 рівнянь із   m + n   невідомими. Така   система має нескінченно багато рішень. Щоб одержати конкретне рішення, один з потенціалів вважають рівним 0.

Знайдемо, наприклад, систему потенціалів для опорного плану, наведеного у таблиці 5.6. Складемо систему рівнянь:

Покладемо α1=0. Тоді β1=2; β3=1; α2=2; α3=1; β2=1.
Доповнимо таблицю 5.6 стовпцем з потенціалами α
i і рядком з потенціалами βj, одержимо таблицю 5.7.

Таблиця 5.7

                Пп

Пв                           

В1

В2

В3

Запаси

αi

А1

2                  2

0

1                   3

1                   1

40

40

0

А2

4                  4

60

3                   2

3                   5

60

2

А3

3                  3

10

2                   2

40

2                   6

50

1

Потреби

70

40

40

150=150

βj

2

1

1

Назвемо псевдовартістю перевезення одиниці вантажу з пункту Аi у пункт Вj величину

Розраховані для таблиці 5.7 псевдовартості розміщені в лівих верхніх кутах цієї таблиці.

Потенціали і псевдовартості мають цікаву економічну інтерпретацію. Припустимо, що є перевізник, що бере  з пункту Аi  плату αi  за вивіз одиниці вантажу, а з пункту Вj - плату βj за ввезення одиниці вантажу. Тоді псевдовартість  –  це той виторг, що одержує перевізник за перевезення одиниці вантажу з пункту Аi у пункт Вj. Корисно застосувати цю інтерпретацію для кращого розуміння тієї умови оптимальності опорного плану, що буде наведено нижче.

А поки доведемо  наступне   твердження:    

ціна   γij  циклу перерахунку, що проходить через вільну клітинку (ij), виражається формулою

 

Для доказу розглянемо рисунок 5.1.

Рис. 5.1.

Клітинка (ij) - єдина вільна клітка зображеного циклу перерахування. Ціна γij циклу перерахування, відповідно до визначення, дорівнює

Оскільки для базисних клітинок виконуються рівності (5.6), то
можна записати:

, що й було потрібно довести.

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

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

Наприклад, опорний план перевезень таблиці 5.7 не є
оптимальний, оскільки для клітинки (2.2) псевдовартість більше
вартості. Ціна циклу перерахування, що проходить через цю клітинку
від
ємна  й дорівнює 2–3=–1 (у цьому можна зайвого разу
переконатися, підрахувавши ціну, виходячи з визначення). Зробивши максимально припустиме зрушення величиною h=40, одержимо таблицю 5.8.

Таблиця 5.8

                Пп

Пв                           

В1

В2

В3

Запаси

αi

А1

2                  2

0

0               3           

1                   1

40

40

0

А2

4                  4

20

2                   2

40

3                   5

60

2

А3

3                  3

50

1                   2

2                   6

50

1

Потреби

70

40

40

150=150

βj

2

0

1

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

fmin=40• 1+20• 4+40• 2+50• 3=350 грошових одиниць.

5.6. Алгоритм вирішення транспортної задачі методом потенціалів

1. Відшукуємо вихідний опорний план перевезень (наприклад, методом північно-західного кута). Перехід до пункту 2.

2. Будуємо систему потенціалів. Для цього для кожної базисної
клітинки (p,q) записуємо рівняння α
pq=cpq. Виходить
система m+n–1 рівнянь із m+n невідомими потенціалами. Один з
потенціалів вважаємо рівним 0 і знаходимо із системи інші
потенціали. Перехід до пункту 3.

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

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

Приклад. Вихідні дані задачі наведені в таблиці 5.9.

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

Таблиця 5.9

                Пп

Пв                           

В1

В2

В3

В4

Запаси

αi

А1

     2

15

1                   4

5                   7

11                   6

15

0

А2

    5

7

    4

18

8

10

14                   9

35

3

А3

3                  4

2                 11

    6

7

    12

13

20

1

Потреби

22

18

17

13

70=70

βj

2

1

5

11

Для визначення потенціалів вирішимо наступну систему:

Покладемо α1=0. Тоді β1=2; α2=3; β2=1; β3=5; α3=1; β4=11. Знайдені потенціали вносимо в таблицю 5.9.

Обчислюємо псевдовартості для вільних клітинок і проставляємо їх у ліві верхні кути клітинок. Вибираємо вільну клітку, у якій ;  наприклад, виберемо клітинку (1,4). Будуємо цикл перерахування, що проходить через цю клітинку, і зробимо по ньому максимально припустиме зрушення h = 10 (у від’ємних  клітинках найменшим перевезенням є х23=10). Після зрушення клітинка (2,3) стає вільною, а клітинка (1,4) - базисною. Одержуємо новий опорний план, записаний у таблиці 5.10.

 Таблиця 5.10

                Пп

Пв                           

В1

В2

В3

В4

Запаси

αi

А1

     2

5

1                   4

0                   7

                     6

10

15

0

А2

    5

17

    4

18

3                   8

9                     9

35

3

А3

8                  7

7                 11

    6

17

    12

3

20

6

Потреби

22

18

17

13

70=70

βj

2

1

0

6

Знову будуємо систему потенціалів, розраховуємо псевдовартості,  будуємо цикл перерахування, що проходить через клітинку (3,1), робимо по ньому максимально припустиме зрушення величиною h=3.

                                                                                 

        Таблиця 5.11

                Пп

Пв                          

В1

В2

В3

В4

Запаси

αi

А1

     2

2

1                   4

-4                 7

                     6

13

15

0

А2

    5

17

    4

18

-1                 8

9                     9

35

3

А3

                 4

3

2                 11

    6

17

8                   12

20

2

Потреби

22

18

17

13

70=70

βj

2

1

-4

6

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

Отже, оптимальний план має такий вигляд: х11=2; х14=13; х21=17; х22=18; х31=3; х33=17.

При цьому fmln = 2• 2 + 13• 6 + 17• 5 + 18• 4 + 3• 4 + 17• 6 =353 гр. од.

5.7. Відкриті транспортні задачі.

При  розгляді  транспортної  задачі  (5.1  -  5.4) передбачалася справедливість рівності .  Такі транспортні задачі  називаються закритими (збалансованими). На практиці часто виникають так звані відкриті (незбалансовані) транспортні задачі, для яких .

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

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

Відкрита  транспортна  задача  зводиться до  закритої у такий спосіб.

Нехай  . Введемо фіктивний пункт призначення Вn+1 з потребою .

Будемо вважати, що cin+1=0 при всіх . Після вирішення отриманої закритої транспортної задачі опустимо перевезення в пункт Вn+1; одержимо оптимальний план перевезень для відкритої транспортної задачі.

Аналогічно, у випадку справедливості нерівності   вводиться фіктивний пункт відправлення Аm+1, і справа зводиться до вирішення закритої транспортної задачі.

Приклад. Нехай вихідні дані наведені в таблиці 5.12

 Таблиця 5.12

                Пп

Пв                          

В1

В2

В3

Запаси

А1

                2

                    4

                3

20

А2

                1

                5

                 4

30

Потреби

15

25

18

58 #50

Це відкрита транспортна задача, у якій  .

Введемо фіктивний пункт відправлення А3 із запасом 8 (табл. 5.13)

Таблиця 5.13

                Пп

Пв                           

В1

В2

В3

Запаси

А1

                2

                    4

                3

20

А2

                1

                5

                 4

30

А3

                0

                0

                 0

8

Потреби

15

25

18

58=58

Вийшла закрита транспортна задача. Вирішимо її методом
потенціалів    (табл. 5.14, 5.15, 5.16, 5.17).

  Таблиця 5.14     Таблиця 5.15

   Пп Пв                           

В1

В2

В3

Запаси

αi

     Пп Пв                           

В1

В2

В3

Запаси

αi

А1

        2

15

        4

5

3       3

20

0

А1

2       2

        4

20

5       3

20

1

А2

3      1

       5

20

       4

10

30

1

А2

        1

15

       5

5

       4

10

30

0

А3

-1     0

1       0

        0

8

8

-3

А3

-3     0

1       0

        0

8

8

-4

Потре

би

15

25

18

58=58

Потре

би

15

25

18

58=58

βj

2

4

3

βj

1

5

4

  Таблиця 5.16     Таблиця 5.17

   Пп Пв                           

В1

В2

В3

Запаси

αi

     Пп Пв                           

В1

В2

В3

Запаси

αi

А1

0       2

        4

10

       3

10

20

0

А1

0       2

        4

2

       3 18

20

0

А2

        1

15

       5

15

       4

30

1

А2

        1

15

       5

15

4         4

30

1

А3

-3     0

1       0

        0

8

8

-3

А3

-4     0

          0

8

        0

8

-4

Потре

би

15

25

18

58=58

Потре

би

15

25

18

58=58

βj

0

4

3

βj

0

4

3

У таблиці 5.17 - оптимальний план перевезень для закритої транспортної задачі. Опускаємо перевезення з фіктивного пункту А3,
одержимо оптимальний план для відкритої транспортної задачі (табл.5.18).

fmin = 2• 4 + 18• 3 + 15• 1 + 15• 5 = 152

Потреба пункту В2 задоволена не повністю.

  Таблиця 5.18

     Пн По                           

В1

В2

В3

Запаси

А1

         2

        4

2

       3 18

20

А2

        1

15

       5

15

       4

30

Потре

би

15

25

18

6. ЦІЛОЧИСЛОВЕ ЛІНІЙНЕ ПРОГРАМУВАННЯ

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

6.1. Загальна постановка задачі цілочислового лінійного програмування (ЗЦЛП)

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

                                        (6.1)

                                   

Для ЗЦЛП використовується саме така ж термінологія, що й для ЗЛП: цільова функція, припустиме рішення, оптимальне рішення тощо. Якщо в ЗЦЛП відкинути вимогу цілочисельності, то вийде так звана послаблена задача. Послаблена задача є ЗЛП, у той час як ЗЦЛП такою не є. Справа в тому, що вимога цілочисельності змінних не можна записати у вигляді лінійного обмеження. Аналітично його записати можна. Дійсно, позначимо через [a] цілу частину числа а, тобто найбільше ціле, що не більше а. Наприклад,  [3.4] =3; [-7.2]= -8. Вимога цілочисельності змінної xj можна записати  так: xj -[xj ] =0. Однак це співвідношення не є лінійним. Таким чином, не можна сказати, що ЗЦЛП є окремий випадок ЗЛП - вона взагалі не є ЗЛП.

Для ЗЦЛП не існує такого універсального  ефективного методу вирішення, яким є симплекс-метод для ЗЛП. З точних методів вирішення відзначимо метод відсікання Гоморі й комбінований метод гілок та  меж. Суть цього комбінованого методу ми викладемо.

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

Наведемо приклади ЗЦЛП.

6.2. Цілочислова задача про використання сировини

Підприємство випускає  n видів штучної продукції вартістю за штуку. Для  виготовлення продукції використовується  m видів сировини,  запаси якої на підприємстві рівні відповідно . Відома (m х n) – матриця (aij), в якій - витрата i – ої сировини  на виробництво одиниці продукції  j -го виду. Потрібно скласти такий план виробництва, при якому прибуток від реалізації продукції був б найбільшим.

Математична модель задачі має вигляд:

f = →  max

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

                                        

Тут  - кількість  продукції j -го виду.  

Це  задача цілочислового лінійного програмування.

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

6.3. Задача про рюкзак

Цілочисельність задачі про використання сировини не є яскраво вираженою ЗЦЛП. До типових ЗЦЛП зараховані так звані комбінаторні оптимізаційні задачі. У комбінаторних задачах є кінцева множина варіантів, з яких потрібно вибрати оптимальний. Прикладом такого задачі є задача про рюкзак.

Є рюкзак місткістю V і n предметів об’ємами  v1, v2 , ...,vn і вартостями с1,  c2 ,..., c n . Потрібно впакувати рюкзак так, щоб вартість упакованих предметів була максимальною.

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

Нехай xj – змінна, що приймає тільки два значення: 0 або 1,  причому   xj =0, якщо j-й предмет не впаковується в рюкзак; xj = 1, якщо j-й предмет упаковується в рюкзак. Тоді задача записується так:

                                    

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

                                                                          

Ця ЗЦЛП  називається задачею  булєва програмування. Обмеження задачі можна записати інакше:

        

           

6.4. Вирішення ЗЦЛП методом округлення

Метод округлення - найпростіший метод наближеного вирішення ЗЦЛП. Його сутність полягає в тому, що вирішується ослаблена задача (як задача лінійного програмування) і отримане оптимальне рішення ЗЛП округляється до цілочислового рішення. Цей метод має два суттєвих недоліки:

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

Приклад 1.

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

 

Зробимо округлення:

  1.   x1=2; x2=0. Одержимо неприпустиме рішення - не задовольняється   обмеження 7x1+4x2<=13 (дійсно,  7*2+4*0<=13 – хибна нерівність).

               2)х1=1; х2=0. Це припустиме рішення. Значення цільової функції f=21*1+11*0=21, що значно відрізняється  від оптимального значення.

Оптимальне рішення цієї ЗЦЛП  таке: х1=0;  х2=3; fmax =33.

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

 

6.5. Метод гілок і меж

Цей метод точного вирішення ЗЦЛП найчастіше використовується на практиці. Він полягає в наступному.

Спочатку вирішується ослаблена задача. Якщо отримане оптимальне рішення цілочислове, то ЗЦЛП вирішена. Якщо ж оптимальне рішення ЗЛП не є цілочисловим, то робимо "розгалуження" у такий спосіб. Нехай змінна хs прийняла в оптимальному рішенні значення qs,  що не є цілим. Тоді розглядаємо дві ЗЦЛП. Перша  виходить додаванням обмеження хs <=[qs],  друга – додаванням обмеження хs >=[qs] + 1, де  [qs] - ціла частина числа qs .

Кожна із цих двох задач аналогічним способом може розбитися ще  на дві задачі і  т.д.

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

Недолік методу гілок і меж полягає в тому, що часто оптимальне рішення ЗЦЛП досягається після дуже великої кількості розгалужень.

Повернемося до  ЗЦЛП прикладу 1.

    

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

                    Вихідна ЗЦЛП №1

( оптимальний план )

оптимальний план                                                           ОПР порожня.

                                             

                                                         

   

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

 х1=1, х2=1, fmax=32                                                             х1= , х2=2, fmax=37

A=32- межа

оптимальний план                                                            ОПР порожній

х1=0, х2= , fmax=35,75

              

        

Оптимальний план                                                                        ОПР порожній

х1=0, х2=3, fmax=33>A

Оптимальний план ЗЦЛП: х1=0, х2=3, fmax=33.

7. ЗАГАЛЬНА ПОСТАНОВКА Й РІЗНОВИДИ ЗАДАЧ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ

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

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

z = f(x1, x2, . . . , xn)     (7.1)

і деяка система обмежень , накладених на змінні x1, x2, . . . , xn:

Потрібно  знайти  такий  набір  значень  змінних x1, x2, . . . , xn, що задовольняє обмеженням (7.2), і при цьому  мінімізує або максимізує функцію (7.1).

Якщо всі функції, що фігурують в (7.1) і (7.2), лінійні, то ми маємо ЗЛП. У протилежному  випадку виходить задача  нелінійного програмування.

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

У деяких задачах математичного програмування ОПР складається з дискретної множини точок. Такі задачі називаються дискретними оптимізаційними задачами. Наприклад, якщо в ЗЛП зажадати, щоб змінні приймали тільки цілі значення, то вийде дискретна оптимізаційна задача - задача цілочислового лінійного програмування. Дискретні задачі, як правило, складніші безперервних. Із задач дискретної оптимізації в теперішні часи   проводяться інтенсивні наукові дослідження.

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

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

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

ЛІТЕРАТУРА

1. Крушевский А.В., Зшивальників К.М. Математичне програмування й моделювання в економіці.-К.: Вища шк., 1979

2. Ковалів Ю.Н., Кузубов В.М., Волощенко А.Б. Математичне програмування.-М.: Высш.шк.,1980

3. Таха  X.   Введення  в  дослідження  операцій. (В 2-х книгах).-
М.:Мир,1985

4. Міну М. Математичне програмування. Теорія й
алгоритми.-М.: Наука, 1990.

ЗМІСТ

  1.  РІШЕННЯ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ МЕТОДОМ ГАУСА - ЖОРДАНА........................................................ . . . . . . . . . . . . . . . . . .  4

     1.1. Основні поняття ...................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4

     1.2. Приведення системи лінійних рівнянь до жорданової форми. . . . 5

 1.3. Поняття загального, часного й базисного рішень . . . . . . . . . . . . . 7

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

      2.І. Приклад задач лінійного програмування – задача  про використання обладнання . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.

      2.2. Задача про використання сировини . . . . . . . . . . . . . . . . . . . . . . . . . 9

      2.3. Задача складання раціону (задача про дієту) . . . . . . . . . . . . . . . . . .9

      2.4. Загальна постановка задач лінійного програмування (ЗЛП) . . . . .10

      2.5. Геометричний метод рішення ЗЛП . . . . . . . . . . . . . . . . . . . . . . . . . .11.

      2.6. Канонічний вигляд ЗЛП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15

      2.7. Поняття опорного плану ЗЛП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

  1.  СИМПЛЕКСНИЙ МЕТОД РІШЕННЯ ЗЛП

      3.1. Загальна характеристика і основні етапи симплекс – методу . . . . .17

      3.2.Табличний вид ЗЛП. Симплекс – таблиці . . . . . . . . . . . . . . . . . . . . . 18

      3.3. Умова оптимальності опорного плану . . . . . . . . . . . . . . . . . . . . . . . .20

      3.4. Умова нерозв'язності ЗЛП через необмеженість знизу на ОПР цільовій функції . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .20

      3.5. Перехід до нового опорного плану . . . . . . . . . . . . . . . . . . . . . . . . . .21

      3.6. Табличний симплекс-алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

      3.7. Відшукання початкового опорного плану ЗЛП методом штучного базису . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

     3.8. Виродженість опорного плану. Зациклення . . . . . . . . . . . . . . . . . . . .34

   4.    ДВОЇСТІСТЬ У ЛІНІЙНОМУ ПРОГРАМУВАННІ

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

4.2. Поняття двоїстої задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36

4.3. Теореми двоїстості . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37  

   5. ТРАНСПОРТНА ЗАДАЧА            

              5.1. Задача про перевезення . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39  

              5.2. Загальна постановка транспортної задачі . . . . . . . . . . . . . . . . . . . . . .40

       5.3. Відшукання початкового  опорного плану . . . . . . . . . . . . . . . . . . . . 41                                5.4. Цикли перерахування . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43

               5.5. Потенціали . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46.

               5.6. Алгоритм вирішення транспортної задачі методом потенціалів . . .49

       5.7. Відкриті транспортні задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  51

   6.   ЦІЛОЧИСЛОВЕ ЛІНІЙНЕ ПРОГРАМУВАННЯ  

6.1. Загальна постановка задачі цілочислового лінійного програмування (ЗЦЛП) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..53

6.2. Цілочислова задача про використання сировини . . . . . . . . . . . . . . . . .54

6.3. Задача  про рюкзак . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55

6.4. Вирішення  ЗЦЛП методом округлення . . . . . . . . . . . . . . . . . . . . . . . . 55

6.5. Метод гілок і меж . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56

7.  ЗАГАЛЬНА ПОСТАНОВКА І  РІЗНОВИДИ ЗАДАЧ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Література  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59  

Зміст . . . . . .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59  


Y2

(5)

(3)

1

A

(4)

Y1

0,3

ОПР

-1

0

1,4

3,5

(2)

-2,2

(1)

-

-

+

+

-

-

+

+

+

(i,r)

(i,j)

(t,r)

(k,s)

(k,j)

+

-

+

-

+

-

-

+

+

-

+

-

+

-

+

-

+

-

+

-

+

-

ЗЦЛП №3

Додаємо обмеження х1>=2

ЗЦЛП №2

Додаємо

обмеження

 х1<=1

 ЗЦЛП №5

Додаємо обмеження

х2>=2

ЗЦЛП №4

Додаємо 

обмеження  

х2<=1

ЗЦЛП №6

Додаємо обмеження

х1<=0

ЗЦЛП №7

Додаємо обмеження

х1>=1

ЗЦЛП №8

Додаємо обмеження

х2<=3

ЗЦЛП №9

Додаємо обмеження

х2>=4


 

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

28530. Режим гаммирования ГОСТ 28147–89 РГПЧ 77.46 KB
  В данных режимах шифрование информации производится побитовым сложением по модулю 2 каждого 64битного блока шифруемой информации с блоком гаммы шифра. последовательности элементов данных вырабатываемых с помощью некоторого криптографического алгоритма для получения зашифрованных открытых данных. Для наложения гаммы при зашифровании и ее снятия при расшифровании должны использоваться взаимно обратные бинарные операции например сложение и вычитание по модулю 264 для 64битовых блоков данных. Гаммирование решает обе упомянутые проблемы:...
28531. Гаммирование с обратной связью 16.05 KB
  Данный режим очень похож на режим гаммирования и отличается от него только способом выработки элементов гаммы – очередной элемент гаммы вырабатывается как результат преобразования по циклу 32З предыдущего блока зашифрованных данных а для зашифрования первого блока массива данных элемент гаммы вырабатывается как результат преобразования синхропосылки по тому же циклу 32З. Как видно из соответствующего уравнения при расшифровании блока данных в режиме гаммирования с обратной связью блок открытых данных зависит от соответствующего и...
28532. Выработка имитовставки к массиву данных 15.64 KB
  Ранее мы обсудили влияние искажения шифрованных данных на соответствующие открытые данные. Мы установили что при расшифровании в режиме простой замены соответствующий блок открытых данных оказывается искаженным непредсказуемым образом а при расшифровании блока в режиме гаммирования изменения предсказуемы. Означает ли это что с точки зрения защиты от навязывания ложных данных режим гаммирования является плохим а режимы простой замены и гаммирования с обратной связью хорошими – Ни в коем случае.
28533. Криптографические средства 24 KB
  Они имеют своей задачей защиту информации при передаче по линиям связи хранении на магнитных носителях а так же препятствуют вводу ложной информации имитостойкость. Основные задачи криптографии Криптографические методы защиты информации используются как самостоятельно так и в качестве вспомогательного средства для решения задач не имеющих на первый взгляд отношения к криптографии. Интересы криптографии сосредоточены на двух задачах: обеспечение конфиденциальности при хранении и передаче информации когда никто кроме владельца...
28534. Характер криптографической деятельности 68.5 KB
  Вместе с тем большую если не центральную роль в защите информации играет ранее сверх засекреченная область деятельности – криптография. Криптография в переводе с греческого означает тайнопись как систему изменения правил написания текстов с целью сделать эти тексты непонятными для непосвященных лиц не путать с тайнописью основанной на сокрытии самого факта написания текста например симпатическими чернилами и т. Шифровались религиозные тексты прорицания жрецов медицинские рецепты использовалась криптография и в государственной сфере....
28535. Защита данных с помощью шифрования 44.5 KB
  Защита данных с помощью шифрования – одно из возможных решений проблемы безопасности. Зашифрованные данные становятся доступными только тем кто знает как их расшифровать и поэтому похищение зашифрованных данных абсолютно бессмысленно для несанкционированных пользователей. Основные направления использования криптографических методов – передача конфиденциальной информации по каналам связи например электронная почта установление подлинности передаваемых сообщений хранение информации документов баз данных на носителях в...
28536. Требования к криптосистемам 29 KB
  Независимо от способа реализации для современных криптографических систем защиты информации сформулированы следующие общепринятые требования: стойкость шифра противостоять криптоанализу должна быть такой чтобы вскрытие его могло быть осуществлено только решением задачи полного перебора ключей и должно либо выходить за пределы возможностей современных компьютеров с учетом возможности организации сетевых вычислений или требовать создания использования дорогих вычислительных систем; криптостойкость обеспечивается не секретностью...
28537. Имитостойкость и помехоустойчивость шифров 13.41 KB
  Они имеют своей задачей защиту информации при передаче по линиям связи хранении на магнитных носителях а так же препятствуют вводу ложной информации имитостойкость. Различают стойкость ключа сложность раскрытия ключа наилучшим известным алгоритмом стойкость бесключевого чтения имитостойкость сложность навязывания ложной информации наилучшим известным алгоритмом и вероятность навязывания ложной информации. Аналогично можно различать стойкость собственно криптоалгоритма стойкость протокола стойкость алгоритма генерации и...
28538. КРАТКИЕ СВЕДЕНИЯ О КРИПТОАНАЛИЗЕ 39.5 KB
  Нарушителю доступны все зашифрованные тексты. Нарушитель может иметь доступ к некоторым исходным текстам для которых известны соответствующие им зашифрованные тексты. Его применение осложнено тем что в реальных криптосистемах информация перед шифрованием подвергается сжатию превращая исходный текст в случайную последовательность символов или в случае гаммирования используются псевдослучайные последовательности большой длины. Дифференциальный или разностный криптоанализ – основан на анализе зависимости изменения шифрованного текста...