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

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

, (1.1)

за умов

; (1.2)

(1.3)

(1.4).

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

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

– методи відтинання;

– комбінаторні методи.

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

методи розв'язування повністю цілочислових задач (дробовий алгоритм Гоморі);

методи розв'язування частково цілочислових задач (другий алгоритм Гоморі, або змішаний алгоритм цілочислового програмування).

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

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

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

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

Фермеру для удобрення земельної ділянки необхідно придбати 107 кг добрив. Він може купити добрива в упаковках по 35 кг вартістю 14 ум. од. або по 24 кг вартістю 12 ум. од. Метою фермера є закупівля не менше, ніж 107 кг добрив з мінімальними витратами. Причому потрібно купувати або цілу упаковку, або не купувати її зовсім, бо частину упаковки придбати неможливо.

Розв'язання. Позначимо кількість упаковок вагою 35 кг та вагою 24 кг відповідно змінними та . Маємо модель цієї задачі:

,

, ,, - цілі числа.

У результаті розв'язування задачі будь-яким з вищенаведених методів отримаємо оптимальний план: , . Отже, за оптимальним планом найменші витрати, що дорівнюють 50 ум. од., можливі у разі закупівлі однієї упаковки добрив вагою 35 кг та трьох упаковок вагою по 24 кг.

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

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

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

,

звідки p - 1 відношення можна виразити через будь-яке з них, наприклад, через перше:

,або ,.

Замінивши та їх значеннями, отримаємо p - 1 обмеження стосовно комплектів:

=,

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

.

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

Отже, необхідно знайти найбільше значення функції:

за обмежень:

,

- цілі числа .

Розглянемо приклад задачі оптимального розкрою матеріалів.

Приклад 1.2: У цеху розрізують прути завдовжки 6 м на заготівки довжиною 1,4, 2 і 2,5 м. Цех обслуговує двох замовників, для кожного з яких окремо необхідно знайти:

1. як розрізати 200 прутів, щоб отримати не менше як 40, 60 і 50 заготівок завдовжки відповідно 1,4; 2 і 2,5 м. Критерій оптимізації - мінімум відходів;

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

Розв'язання.

1) розв'яжемо задачу за умовами першого замовника. Маємо партію прутів у кількості штук. Відома нижня межа кількості заготівок кожного виду. Введемо такі позначення:

- вид заготівки;

- спосіб розрізання прута;

- вихід у разі розрізування прута j-им способом заготівок r-го виду;

- відходи в разі розрізування прута j-им способом;

- кількість наявних прутів;

- нижня межа потреби в r-ій заготівці;

- кількість прутів, які розрізані за j-им способом.

Запишемо математичну модель для розв'язування першого пункту задачі оптимального розкрою.

Критерієм оптимальності є мінімальна кількість відходів: .

Кількість отриманих заготівок кожного виду має бути не меншою від зазначених потреб:

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

.

Змінні задачі - невід'ємні і цілі числа. Отже, маємо математичну модель:

,

,

- цілі числа.

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

Таблиця 1.0

Бажано, щоб у множину ввійшли всі можливі варіанти, навіть такі, які на перший погляд здаються неефективними, наприклад, Х6.

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

за умов:

а) кількість заготівок завдовжки 1,4 м:

;

б) кількість заготівок завдовжки 2 м:

;

в) кількість заготівок завдовжки 2,5 м:

;

г) кількість наявних прутів:

;

д) невід'ємність змінних:

;

є) цілочисловість змінних:

- цілі числа .

Отже, загалом маємо математичну модель виду:

- цілі числа .

Розв'язуючи задачу одним із методів цілочислового програмування, отримуємо набір альтернативних оптимальних планів (загальною кількістю 146). Наприклад, такий план забезпечує виготовлення всіх видів заготівок у мінімально можливій кількості за найменшого загального обсягу відходів, причому для цього використовуються лише 54 прути: , , тобто 4 прути необхідно розрізати другим способом (по три заготівки довжиною 2 м) та 50 прутів четвертим способом (по одній заготівці кожного виду). Сумарна довжина залишків дорівнює п'яти метрам. Аналогічне значення цільової функції () дає оптимальний план, за яким виготовляється більша кількість кінцевої продукції та витрачається весь наявний матеріал:

.

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

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

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

- вид заготівки;

- спосіб розрізування прута;

- вихід у разі розрізування прута j-им способом заготівок r-го виду;

- кількість наявних прутів;

- кількість прутів, які розрізані за j-им варіантом;

- кількість r-го виду заготівок у комплекті;

- кількість всіх заготівок r-го виду.

Математична модель у цьому разі суттєво відрізняється від моделі, що розглянута вище.

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

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

=; =, звідки,. ,

Замінимо та їх значеннями:

=або ;

=або .

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

.

Всі мають задовольняти умову невід'ємності: , та цілочисловості.

Отже, необхідно знайти найбільше значення функції:

за обмежень:

, ,

- цілі числа .

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

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

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

.

Обмеження щодо формування комплектів матимуть вигляд: , або

,

Звідси

,

аналогічно для :

, або

.

Обмеження щодо використання наявних прутів:

.

Обмеження стосовно невід'ємності та цілочисловості змінних:

;

- цілі числа .

Отже, загалом маємо таку математичну модель:

max

- цілі числа .

Розв'язавши задачу будь-яким з вищеописаних методів, отримаємо оптимальний план:

,

комплектів.

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

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

Позначимо:

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

,

де - відстань між містами і та j.

Обмеження щодо одноразового в'їзду в кожне місто:

.

Обмеження щодо одноразового виїзду з кожного міста:

.

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

.

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

.

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

Отже, маємо таку математичну модель:

Приклад 1.3:

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

рис.2.1

Максимальне значення функціонала для даної задачі знаходиться в точці В. Округлення дасть таке значення оптимального плану (точка D на рис.2.1). Очевидно, що точка D не може бути розв'язком задачі, оскільки вона навіть не належить множині допустимих розв'язків (чотирикутник ОАВС), тобто відповідні значення змінних не задовольнятимуть систему обмежень задачі.

Зауважимо, що геометрично множина допустимих планів будь-якої лінійної цілочислової задачі являє собою систему точок з цілочисловими координатами, що знаходяться всередині опуклого багатокутника допустимих розв'язків відповідної нецілочислової задачі. Отже, для розглянутого на рис.2.1 випадку множина допустимих планів складається з дев'яти точок (рис.2.2), які утворені перетинами сім'ї прямих, що паралельні осям та і проходять через точки з цілими координатами 0, 1,2. Для знаходження цілочислового оптимального розв'язку пряму, що відповідає цільовій функції, пересуваємо у напрямку вектора нормалі до перетину з кутовою точкою утвореної цілочислової сітки. Координати цієї точки і є оптимальним цілочисловим розв'язком задачі. У нашому прикладі оптимальний цілочисловий розв'язок відповідає точці М ().

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

Графічний метод

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

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

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

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

Отриманий новий багатогранник розв'язків містить всі цілі точки, які були в початковому, і розв'язок, що буде отримано на ньому, буде цілочисловим (рис.2.3).

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

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

Нехай маємо задачу цілочислового програмування:

(1.5)

за умов:

(1.6)

, (1.7)

- цілі числа (1.8).

Допустимо, що параметри - цілі числа.

Не враховуючи умови цілочисловості, знаходимо розв'язок задачі (1.5) - (1.7) симплексним методом. Нехай розв'язок існує і міститься в такій симплексній таблиці:

Таблиця 1.5

Змінні - базисні, а - вільні. Оптимальний план задачі: . Якщо - цілі числа, то отриманий розв'язок є цілочисловим оптимальним планом задачі (1.5) - (1.8). Інакше існує хоча б одне з чисел, наприклад, - дробове. Отже, необхідно побудувати правильне обмеження, що відтинає нецілу частину значення .

Розглянемо довільний оптимальний план задачі (1.5) - (1.7). Виразимо в цьому плані базисну змінну через вільні змінні:

. (1.9)

Виразимо коефіцієнти при змінних даного рівняння у вигляді суми їх цілої та дробової частин. Введемо позначення: - ціла частина числа b, - дробова частина числа b*1. Отримаємо:

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

Наприклад, для = =2, ==;

для = =,

, (1.10)

. (1.11)

Отже, рівняння (1.11) виконується для будь-якого допустимого плану задачі (1.5) - (1.7). Допустимо тепер, що розглянутий план є цілочисловим оптимальним планом задачі. Тоді ліва частина рівняння (1.11) складається лише з цілих чисел і є цілочисловим виразом. Отже, права його частина також є цілим числом і справджується рівність:

, (1.12)

де N - деяке ціле число.

Величина N не може бути від'ємною. Якщо б , то з рівняння (1.12) приходимо до нерівності:

.

Звідки . Тобто це означало б, що дробова частина перевищує одиницю, що неможливо. У такий спосіб доведено, що число N є невід'ємним.

Якщо від лівої частини рівняння (2.12) відняти деяке невід'ємне число, то приходимо до нерівності:

, (1.13)

яка виконується за допущенням для будь-якого цілочислового плану задачі (1.5) - (1.7). У такий спосіб виявилося, що нерівність (1.13) є шуканим правильним відтинанням.

Отже, для розв'язування цілочислових задач лінійного програмування (1.1) - (1.4) методом Гоморі застосовують такий алгоритм:

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

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

Якщо задача (1.1) - (1.3) не має розв'язку (цільова функція необмежена, або система обмежень несумісна), то задача (1.1) - (1.4) також не має розв'язку.

2. Коли в умовно-оптимальному плані є дробові значення, то вибирається змінна, яка має найбільшу дробову частину. На базі цієї змінної (елементів відповідного рядка останньої симплексної таблиці, в якому вона міститься) будується додаткове обмеження Гоморі:

.

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

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

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

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

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

Приклад 2.1 Сільськогосподарське підприємство планує відкрити сушильний цех на виробничій площі 190 м2, маючи для цього 100 тис. грн і можливість придбати устаткування двох типів: А і В. Техніко-економічну інформацію стосовно одиниці кожного виду устаткування подано в табл.1.6:

Таблиця 1.6

Розв'язання. Нехай і -кількість комплектів устаткування відповідно типу А і В.

Запишемо економіко-математичну модель задачі:

, ;

; ,

і - цілі числа.

Розв'язуємо задачу, нехтуючи умовою цілочисловості. Остання симплексна таблиця набуде вигляду:

Таблиця 6.3

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

.

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

.

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

.

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

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

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

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

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

Тобто допустиме ціле значення має задовольняти одну з нерівностей виду:

або .

Дописавши кожну з цих умов до задачі з послабленими обмеженнями, дістанемо дві, не пов'язані між собою, задачі.

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

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

перша задача:

(1.14)

за умов

; (1.15), (1.16)

(1.17), , (1.18)

друга задача

(1.19)

за умов:

, ; (1.20)

; (1.21)

- цілі числа ; (1.22)

, (1.23)

де -дробова компонента розв'язку задачі (1.1) - (1.4).

Наведені задачі (1.14) - (1.18) і (1.19) - (1.23) спочатку послаблюємо, тобто розв'язуємо з відкиданням обмежень (1.17) і (1.22). Якщо знайдені оптимальні плани задовольняють умови цілочисловості, то ці плани є розв'язками задачі (1.1) - (1.4). Інакше пошук розв'язку задачі триває. Для дальшого розгалуження вибираємо розв'язок задачі з більшим значенням цільової функції, якщо йдеться про максимізацію, і навпаки - з меншим значенням цільової функції в разі її мінімізації. Подальше розгалуження виконується доти, доки не буде встановлено неможливість поліпшення розв'язку. Здобутий останній план - оптимальний.