29. Застосування теорем двоїстості в розв’язуванні задач лінійного програмування. Навести відповідні формули.

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

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

(5.9)

.

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

(5.10)

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

Аналогічно:

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

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

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

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

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

(5.14)

(5.15)

(5.16)

маємо нову задачу, де замінено на . Позначимо через оптимальний план нової задачі. Для визначення не потрібно розв’язувати нову задачу лінійного програмування, а достатньо скористатися формулою , де – оптимальний план задачі (5.14-5.16).

30. Цілочислове програмування. Приклади застосування цілочислових задач в плануванні й управлінні виробництвом. Навести відповідні формули.

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

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

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

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

за умов:

; (8.2)

; (8.3)

– цілі числа .

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

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

Рисунок 8.1

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

Зауважимо, що геометрично множина допустимих планів будь-якої лінійної цілочислової задачі являє собою систему точок з цілочисловими координатами, що знаходяться всередині опуклого багатокутника допустимих розв’язків відповідної нецілочислової задачі. Отже, для розглянутого на рис.8.1 випадку множина допустимих планів складається з дев’яти точок (рис.8.2), які утворені перетинами сім’ї прямих, що паралельні осям Ох₁ та Oх₂ і проходять через точки з цілими координатами 0, 1, 2.

Рисунок 8.2

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

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