Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

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

«До табунника прийшли три козаки купувати коней.«Добре, я вам продам коней, — сказав табунник, — першому я продам півтабуна і ще півконя, другому — половину коней, що залишаться,і ще півконя, третій також здобуде половину коней, що залишаться, з півконем. Собі ж я залишу тільки 5 коней». Здивувалися козаки, як це табунник буде розділяти коней на частини. Але після деяких роздумів вони заспокоїлися, і угода відбулася»

(Задача з книги, виданої у XVIII столітті)

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

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

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

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

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

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

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

(6.1)

за умов:

; (6.2)

; (6.3)

— цілі числа . (6.4)

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