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

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

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

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

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

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

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

Див. також

• Лінійне програмування
• Комбінаторна оптимізація

Джерела

• Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. — К.: КНЕУ, 2003. — 452 с. [ 2 травня 2013 у Wayback Machine.]