Методи і способи вирішення завдань цілочисельного параметричного програмування

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Зміст

Введення

1. Основні поняття лінійного програмування

2. Цілочисельне програмування

2.1 Постановка завдання і методи вирішення

2.2 Приклад розв'язання задачі цілочислового програмування

3. Параметричне програмування

3.1 Завдання з параметром в цільовій функції

3.2 Завдання з параметром у вільних членах системи обмежень

3.3 Завдання, цільова функція і права частина обмежень якої містить параметр

4. Цілочисельне параметричне програмування

4.1 Приклад розв'язання задачі цілочисельного програмування з параметром в цільовій функції

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

Висновок

Список літератури

Введення

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

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

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

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

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

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

У першому розділі даної роботи розглянуто основні поняття лінійного програмування.

У другому розділі сформульована задача цілочисельного програмування та розглянуто методи її вирішення. Наведено приклад рішення задачі цілочислового програмування.

У третьому розділі розглянуті задачі параметричного програмування і на прикладах показані методи вирішення різних завдань цього типу.

У четвертому розділі сформульовані і досліджені задачі цілочисельного параметричного програмування. Самостійно була вирішена задача цілочисельного параметричного програмування з параметром в цільовій функції двома способами. На основі рішення даного завдання визначено метод розв'язання задач такого типу. Також вирішено завдання цілочисельного програмування з параметром у вільних членах системи обмежень.

При написанні диплома використовувалася наступна довідкова література: Кузнєцов Ю.М., Кузубов В.І., Волощенко А.Б. Математичне програмування, Ашманов С.А. Лінійне програмування. Деякі приклади були взяті з книг Копилов В.І. Лекції та практичні заняття з математичного програмування, Акуліч І.Л. Математичне програмування в прикладах і задачах. Алгоритми методів вирішення завдань цілочисельного і параметричного програмування найбільш доступно і повно, на мій погляд, розкриваються в книзі Акуліч І.Л.

1. Основні поняття лінійного програмування

Розрізняють три основні форми завдань лінійного програмування в залежності від обмежень різного типу.

Стандартна задача лінійного програмування має вигляд:

(1.1)

(1.2)

У матричній формі завдання (1.1) - (1.2) має вигляд:

де - Матриця коефіцієнтів. Вектор називають вектором коефіцієнтів лінійної форми, вектор - Вектором обмежень.

Канонічна задача лінійного програмування має вигляд:

або, в матричній формі:

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

Теорема. Стандартна, канонічна і загальна завдання лінійного програмування еквівалентні.

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

2. Цілочисельне програмування

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

2.1 Постановка завдання і методи вирішення

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

Потрібно знайти мінімальне значення лінійної функції

(2.1.1)

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

(2.1.2)

(2.1.3)

- Цілі. (2.1.4)

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

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

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

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

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

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

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

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

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

де і - Невід'ємні.

Оскільки за умовою - Невід'ємні цілі числа, то і різниця

(2.1.5)

також ціле невід'ємне число.

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

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

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

  1. Використовуючи симплексний метод, знаходять рішення задачі (2.1.1) - (2.1.3) без урахування вимоги цілочисельності змінних.

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

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

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

Метод гілок і меж. Продовжимо розгляд завдання (2.1.1) - (2.1.4), що складається у визначенні мінімального значення лінійної функції

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

- Цілі.

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

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

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

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

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

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

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

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

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

Отже, процес знаходження рішення задачі цілочислового програмування (2.1.1) - (2.1.4) методом гілок і меж включає наступні основні етапи:

1. Знаходять розв'язок задачі цілочисельного програмування (2.1.1) - (2.1.3).

2. Складають додаткові обмеження для однієї із змінних, значення якої в оптимальному плані задачі (2.1.1) - (2.1.3) є дробовим числом.

3. Знаходять вирішення завдань і , Які виходять з завдання (2.1.1) - (2.1.3) в результаті приєднання додаткових обмежень.

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

2.2 Приклад розв'язання задачі цілочислового програмування

Приклад 2.2.1. Знайти найменше значення при обмеженнях

Рішення. Помножимо друга нерівність на (-1):

Для того щоб перейти від нерівностей до равенствам, додамо до лівих частинах нерівностей додаткові змінні:

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

Таблиця 2.2.1

БП

СЧ

1

2

-1

1

1

0

0

2

-4

2

-1

0

1

0

5

3

0

1

0

0

1

З

0

-1

1

3

0

0

0

Таблиця 2.2.2

БП

СЧ

1

2

-1

1

1

0

0

3

-2

1

0

1

1

0

4

1

1

0

-1

0

1

З

-3

-7

4

0

0

0

0

Таблиця 2.2.3

БП

СЧ

4

0

0

1

2

1

0

3

-2

1

0

1

1

0

1

3

0

0

-2

-1

1

З

-15

1

0

0

-7

-4

0

Таблиця 2.2.4

БП

СЧ

4

0

0

1

2

1

0

11 / 3

0

1

0

-1 / 3

1 / 3

2 / 3

1 / 3

1

0

0

-2 / 3

-1 / 3

1 / 3

З

-46 / 3

0

0

0

-19 / 3

-11 / 3

-1 / 3

Отримали оптимальне рішення цієї задачі , В якому - Дробові. Складемо додаткове обмеження для змінної, що має найбільшу дробову частину. Маємо:

Тоді згідно з формулою (2.1.5), додаткове обмеження має вигляд:

Помножимо обидві частини останнього нерівності на (-1) і перетворимо його в рівняння:

Допишемо коефіцієнти цього рівняння знизу до таблиці 2.2.4, додамо додатковий стовпець, відповідний змінної , Отримаємо

Таблиця 2.2.5

БП

СЧ

4

0

0

1

2

1

0

0

11 / 3

0

1

0

-1 / 3

1 / 3

2 / 3

0

1 / 3

1

0

0

-2 / 3

-1 / 3

1 / 3

0

-2 / 3

0

0

0

-2 / 3

-1 / 3

-2 / 3

1

З

-46 / 3

0

0

0

-19 / 3

-11 / 3

-1 / 3

0

Застосуємо двоїстий симплекс - метод, в результаті отримаємо

Таблиця 2.2.6

БП

СЧ

4

0

0

1

2

1

0

0

3

0

1

0

-1

0

0

1

0

1

0

0

-1

-1 / 2

0

1 / 2

1

0

0

0

1

1 / 2

1

-3 / 2

З

-15

0

0

0

-6

-7 / 2

0

-1 / 2

Оптимальне цілочисельне рішення:

3. Параметричне програмування

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

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

3.1 Завдання з параметром в цільовій функції

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

Дана лінійна функція

(3.1.1)

і система лінійних обмежень

(3.1.2)

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

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

Для всіх задача має один і той же оптимальний план, що і при .

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

1) якщо , То завдання нерозв'язна для будь-якого ;

2) якщо , То завдання нерозв'язна для всіх ;

3) якщо , То завдання нерозв'язна для всіх .

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

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

Процес знаходження рішення задачі включає наступні етапи:

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

2. Визначають безліч значень параметра , Для яких знайдений оптимальний план є оптимальним або завдання нерозв'язна. Ці значення параметра виключають з розгляду.

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

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

Приклад 3.1.1. Для всіх значень параметра знайти максимальне значення функції

за умов:

Рішення. Візьмемо (число 0 вибрано довільно) і знайдемо симплекс-методом оптимальний план.

Таблиця 3.1.1.

БП

СЧ

12

1

1

1

0

0

10

1

-1

0

1

0

6

-1

1

0

0

1

З

0

-2

0

0

0

Таблиця 3.1.2.

БП

СЧ

6

2

0

1

0

0

16

0

0

0

1

0

6

-1

1

0

0

1

З

0

0

0

Таблиця 3.1.3.

БП

СЧ

3

1

0

1 / 2

0

-1 / 2

16

0

0

0

1

1

9

0

1

1 / 2

0

1 / 2

З

0

0

0

Визначимо значення , При яких план, відповідний таблиці 3.1.3, залишиться оптимальним:

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

Таблиця 3.1.4.

БП

СЧ

11

1

0

1 / 2

1 / 2

0

16

0

0

0

1

1

1

0

1

1 / 2

-1 / 2

0

З

0

0

0

Цей план оптимальний за умови:

Отже, при При маємо:

Таблиця 3.1.5.

БП

СЧ

10

1

-1

0

1

0

16

0

0

0

1

1

2

0

2

1

-1

0

З

20

0

0

2

0

Цей план оптимальний за умови: . Отже, при

2. Завдання з параметром у вільних членах системи обмежень

Дана лінійна функція і система лінійних обмежень

(3.2.1)

(3.2.2)

Алгоритм рішення задачі (3.2.1) - (3.2.2) подібний розглянутому вище алгоритму розв'язання задачі (3.1.1) - (3.1.2). Вважаючи значення параметра рівним деякому числу , Знаходимо рішення отриманої завдання лінійного програмування. При цьому значенні параметра або визначаємо оптимальний план задачі, або встановимо її нерозв'язність. У першому випадку знайдений план є оптимальним для будь-якого , Де

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

.

Якщо при завдання (3.2.1) - (3.2.2) нерозв'язна, то або цільова функція задачі (3.2.1) не обмежена на безлічі планів, або система рівнянь (3.2.2) не має невід'ємних розв'язків. У першому випадку завдання нерозв'язна для всіх , А в другому випадку визначаємо всі значення параметра , Для яких система рівнянь (3.2.2) несовместна, і виключаємо їх з розгляду. Після визначення проміжку, в якому завдання (3.2.1) - 3.2.2) має один і той же оптимальний план або нерозв'язна, вибираємо нове значення параметра , Що не належить знайденому проміжку, і знаходимо рішення отриманої завдання лінійного програмування. При цьому рішення нового завдання шукаємо за допомогою двоїстого симплекс-методу. Продовжуючи ітераційний процес, після кінцевого числа кроків отримуємо рішення завдання (3.2.1) - (3.2.2). Отже, процес знаходження рішення завдання (3.2.1) - (3.2.2) включає такі основні етапи:

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

2. Знаходять значення параметра , Для яких завдання (3.2.1) - (3.2.2) має один і той же оптимальний план або нерозв'язна. Ці значення параметра виключають з розгляду.

3. Вибирають значення параметра із частини проміжку і встановлюють можливість визначення нового оптимального плану. У разі існування оптимального плану знаходять його двоїстим симплекс-методом ..

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

Приклад 3.2.1. Для кожного значення параметра знайти максимальне значення функції

Рішення. Вважаючи , Знаходимо рішення:

Таблиця 3.2.1.

БП

СЧ

1

1

1

0

0

2

-1

0

1

0

-2

2

0

0

1

З

10

-1

0

0

0

Таблиця 3.2.2.

БП

СЧ

2

0

1

0

-1 / 2

1

0

0

1

1 / 2

-1

1

0

0

1 / 2

З

9

0

0

0

1 / 2

Оптимальний план при : Цей план буде залишатися оптимальним, поки серед його компонент не виявиться негативного числа:

.

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

Таблиця 3.2.3.

БП

СЧ

0

2

1

0

1 / 2

0

1

0

1

1

1

-1

0

0

-1 / 2

З

0

9

0

0

5

Цей план залишається оптимальним при

.

Якщо , То це рішення не є планом, так як . Так як у рядку немає негативних чисел, то вихідна задача нерозв'язна.

При , не є планом, так як . За допомогою таблиці 3.2.2 переходимо до наступного рішення:

Таблиця 3.2.4.

БП

СЧ

-4

0

-2

0

1

3

0

1

1

0

1

1

1

0

0

З

11

0

1

0

0

Цей план оптимальний за умови . При завдання нерозв'язна, оскільки в рядку немає негативних чисел.

3. Завдання, цільова функція і права частина обмежень якої містить параметр

Приклад 3.3.1. Для всіх значень параметра знайти максимальне значення функції

Рішення. Нехай . Знаходимо симплекс-методом рішення задачі.

Таблиця 3.3.1.

БП

СЧ

1

-1

1

0

-1

2

0

1

З

0

0

Таблиця 3.3.2.

БП

СЧ

1 / 2

0

1

1 / 2

-1 / 2

1

0

1 / 2

З

0

0

План оптимальний за умови

а серед компонент вектора немає негативних чисел:

Отже, при , ,

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

Таблиця 3.3.3.

БП

СЧ

0

1

1

1

1

-2

0

-1

З

0

0

Вектор оптимальний за умови

тобто при .

Якщо , То з симплексного таблиці 3.3.2 випливає, що завдання не має рішення, тому що в рядку немає негативних чисел.

Ми розглянули інтервал . Нехай , Тоді переходимо до нового оптимального плану:

Таблиця 3.3.4.

БП

СЧ

0

1

1

1

1

0

2

1

З

0

0

Таким чином, при , , .

4. Цілочисельне параметричне програмування

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

4.1 Приклад розв'язання задачі цілочисельного програмування з параметром в цільовій функції

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

.

Рішення. I спосіб. Перейдемо від нерівностей до равенствам, додаючи до лівих частинах нерівностей додаткові змінні:

Візьмемо (Число 0 вибрано довільно) і знайдемо симплекс-методом оптимальний план.

Таблиця 4.1.1.

БП

СЧ

1

2

-1

1

1

0

0

2

-4

2

-1

0

1

0

5

3

0

1

0

0

1

З

0

+1

1

3 +4

0

0

0

Таблиця 4.1.2.

БП

СЧ

1

2

-1

1

1

0

0

3

-2

1

0

1

1

0

4

1

1

0

-1

0

1

З

-3

0

-3

0

0

Таблиця 4.1.3.

БП

СЧ

4

0

0

1

2

1

0

3

-2

1

0

1

1

0

1

3

0

0

-2

-1

1

З

-15

0

0

0

Таблиця 4.1.4.

БП

СЧ

4

0

0

1

2

1

0

11 / 3

0

1

0

-1 / 3

1 / 3

2 / 3

1 / 3

1

0

0

-2 / 3

-1 / 3

1 / 3

З

0

0

0

Визначимо значення параметра t, при яких план, відповідний таблиці 4.1.4 залишиться оптимальним:

.

Отже, при завдання має оптимальне рішення: , . Воно не є цілочисловим: - Дробові. Складемо додаткове обмеження для змінної . Маємо:

,

, , , .

,

.

Таблиця 4.1.5.

БП

СЧ

4

0

0

1

2

1

0

0

11 / 3

0

1

0

-1 / 3

1 / 3

2 / 3

0

1 / 3

1

0

0

-2 / 3

-1 / 3

1 / 3

0

-2 / 3

0

0

0

-2 / 3

-1 / 3

-2 / 3

1

З

0

0

0

0

Застосуємо двоїстий симплекс-метод. Отримаємо:

Таблиця 4.1.6.

БП

СЧ

4

0

0

1

2

1

0

0

3

0

1

0

-1

0

0

1

0

1

0

0

-1

-1 / 2

0

1 / 2

1

0

0

0

1

1 / 2

1

-3 / 2

З

0

0

0

0

Отримали цілочисельне рішення. Розглянемо, при всіх чи

.

Отже, при отримали оптимальне цілочисельне рішення , . Знайдемо оптимальне цілочисельне рішення для .

З таблиці 4.1.6 отримаємо

Таблиця 4.1.7.

БП

СЧ

2

0

0

1

0

1

-2

3

4

0

1

0

0

1 / 2

1

-1 / 2

1

1

0

0

0

0

1

-1

1

0

0

0

1

1 / 2

1

-3 / 2

З

0

0

0

0

-1 / 2

Отримали цілочисельне рішення, подивимося, чи є воно оптимальним:

.

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

Таблиця 4.1.8.

БП

СЧ

4

0

0

1

2

1

0

3

-2

1

0

1

1

0

1

3

0

0

-2

-1

1

З

-

0

0

0

Рішення цілочисельне. Визначимо , При яких план залишається оптимальним

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

Таблиця 4.1.9.

БП

СЧ

2

0

0

1 / 2

1

1 / 2

0

13 / 3

0

1

1 / 6

0

1 / 2

2 / 3

5 / 3

1

0

1 / 3

0

0

1 / 3

З

0

0

0

-1 / 2

Визначимо значення параметра , При яких план залишається оптимальним

.

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

,

, , , .

,

.

Таблиця 4.1.10.

БП

СЧ

2

0

0

1 / 2

1

1 / 2

0

0

13 / 3

0

1

1 / 6

0

1 / 2

2 / 3

0

5 / 3

1

0

1 / 3

0

0

1 / 3

0

-1 / 3

0

0

-1 / 6

0

-1 / 2

-2 / 3

1

З

0

0

0

-1 / 2

0

Таблиця 4.1.11.

БП

СЧ

2

0

0

1 / 2

1

1 / 2

0

0

4

0

1

0

0

0

0

1

3 / 2

1

0

1 / 4

0

-1 / 4

0

1 / 2

1 / 2

0

0

1 / 4

0

3 / 4

1

-3 / 2

З

0

0

0

0

і - Дробові. Складемо додаткове обмеження для :

, .

Таблиця 4.1.12.

БП

СЧ

2

0

0

1 / 2

1

1 / 2

0

0

0

4

0

1

0

0

0

0

1

0

3 / 2

1

0

1 / 4

0

-1 / 4

0

1 / 2

0

1 / 2

0

0

1 / 4

0

3 / 4

1

-3 / 2

0

-1 / 2

0

0

-1 / 4

0

-3 / 4

0

-1 / 2

1

З

0

0

0

0

0

Таблиця 4.1.13.

БП

СЧ

2

0

0

1 / 2

1

1 / 2

0

0

0

3

0

1

1 / 2

0

-3 / 2

0

0

2

1

1

0

0

0

-1

0

0

1

2

0

0

1

0

3

1

0

-3

1

0

0

1 / 2

0

3 / 2

0

1

-2

З

0

0

0

0

0

система не має рішення.

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

- Плани не існують;

- , .

- , .

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

1. При знаходять оптимальний план без умови цілочисельності або встановлюють нерозв'язність завдання.

2. Знаходять значення , Для яких задача має один і той же план, або нерозв'язна.

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

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

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

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

Візьмемо (Число 0 вибрано довільно) і знайдемо симплекс-методом оптимальний план.

Таблиця 4.2.1.

БП

СЧ

1

2

-1

1

1

0

0

2

-4

2

-1

0

1

0

5

3

0

1

0

0

1

З

0

+1

1

3 +4

0

0

0

Таблиця 4.2.2.

БП

СЧ

1

2

-1

1

1

0

0

3

-2

1

0

1

1

0

4

1

1

0

-1

0

1

З

-3

0

-3

0

0

Таблиця 4.2.3.

БП

СЧ

4

0

0

1

2

1

0

3

-2

1

0

1

1

0

1

3

0

0

-2

-1

1

З

-15

0

0

0

Таблиця 4.2.4.

БП

СЧ

4

0

0

1

2

1

0

11 / 3

0

1

0

-1 / 3

1 / 3

2 / 3

1 / 3

1

0

0

-2 / 3

-1 / 3

1 / 3

З

0

0

0

План оптимальний, але не цілочисельний. Складемо додаткове обмеження для змінної :

,

, , , .

Додаткове обмеження має вигляд:

,

.

Таблиця 4.2.5.

БП

СЧ

4

0

0

1

2

1

0

0

11 / 3

0

1

0

-1 / 3

1 / 3

2 / 3

0

1 / 3

1

0

0

-2 / 3

-1 / 3

1 / 3

0

-2 / 3

0

0

0

-2 / 3

-1 / 3

-2 / 3

1

З

0

0

0

0

Застосуємо двоїстий симплекс-метод. Отримаємо:

Таблиця 4.2.6.

БП

СЧ

4

0

0

1

2

1

0

0

3

0

1

0

-1

0

0

1

0

1

0

0

-1

-1 / 2

0

1 / 2

1

0

0

0

1

1 / 2

1

-3 / 2

З

0

0

0

0

Отримали оптимальне цілочисельне рішення при , Знайдемо значення , При яких залишається той же план:

.

Отже, при отримали оптимальне цілочисельне рішення , . Знайдемо оптимальне цілочисельне рішення для . Нехай .

Таблиця 4.2.7.

БП

СЧ

4

0

0

1

2

1

0

0

3

-2

1

0

1

1

0

0

0

2

0

0

-2

-1

0

1

1

3

0

0

-2

-1

1

0

З

0

0

0

0

Отримали оптимальне цілочисельне рішення при , Знайдемо значення , При яких залишається той же план:

Отже, при отримали оптимальне цілочисельне рішення , . Знайдемо оптимальне цілочисельне рішення задачі для значень параметра . Повернемося до таблиці 4.2.6. Нехай , Тоді дозволяє стовпець - , Роздільна рядок - . Отримаємо:

Таблиця 4.2.8.

БП

СЧ

2

0

0

1

0

0

-2

3

4

0

1

0

0

1 / 2

1

-1 / 2

1

1

0

0

0

0

1

-1

1

0

0

0

1

1 / 2

1

-3 / 2

З

-7t-9

0

0

0

0

-1 / 2

9t +6

(-26t-19) / 2

Отримали цілочисельне рішення задачі, знайдемо значення параметра, при яких воно оптимально:

.

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

Таблиця 4.2. 9.

БП

СЧ

2 / 3

0

0

1 / 3

0

0

-2

1

13 / 3

0

1

1 / 6

0

1 / 2

1

0

5 / 3

1

0

1 / 3

0

0

1

0

2

0

0

1 / 2

1

1 / 2

1

0

З

(5 t-8) / 3

0

0

(26 t +19) / 6

0

-1 / 2

(T-1) / 3

0

Отримали оптимальний план, але він не цілочисельний. Складемо додаткове обмеження для змінної :

,

, , , .

,

Таблиця 4.2.10.

БП

СЧ

2 / 3

0

0

1 / 3

0

0

-2

1

0

13 / 3

0

1

1 / 6

0

1 / 2

1

0

0

5 / 3

1

0

1 / 3

0

0

1

0

0

2

0

0

1 / 2

1

1 / 2

1

0

0

-1 / 3

0

0

-1 / 6

0

-1 / 2

-2 / 3

0

1

З

(5 t-8) / 3

0

0

(26 t +19) / 6

0

-1 / 2

(T-1) / 3

0

0

Таблиця 4.2.11.

БП

СЧ

2

0

0

5 / 6

0

3 / 2

0

1

-3

4

0

1

0

0

0

0

0

3 / 2

3 / 2

1

0

1 / 4

0

-1 / 4

0

0

3 / 2

2

0

0

1 / 2

1

1 / 2

0

0

3 / 2

1 / 2

0

0

1 / 4

0

3 / 4

1

0

-3 / 2

З

(3 t-15) / 2

0

0

(51t +39) / 12

0

(-T-1) / 2

0

0

(T-1) / 2

і - Дробові. Складемо додаткове обмеження для :

, .

Таблиця 4.2.12.

БП

СЧ

2

0

0

5 / 6

0

3 / 2

0

1

-3

0

4

0

1

0

0

0

0

0

3 / 2

0

3 / 2

1

0

1 / 4

0

-1 / 4

0

0

3 / 2

0

2

0

0

1 / 2

1

1 / 2

0

0

3 / 2

0

1 / 2

0

0

1 / 4

0

3 / 4

1

0

-3 / 2

0

-1 / 2

0

0

-1 / 4

0

-3 / 4

0

0

-1 / 2

1

З

(3 t-15) / 2

0

0

(51t +39) / 12

0

(-T-1) / 2

0

0

(T-1) / 2

0

Таблиця 4.2.13.

БП

СЧ

5

0

0

7 / 3

0

6

0

1

0

-6

3

0

1

1 / 2

0

-3 / 2

0

0

0

3

1

1

0

0

0

-1

0

0

0

3

2

0

0

1 / 2

1

1 / 2

0

0

0

3

2

0

0

1

0

3

1

0

0

3

1

0

0

1 / 2

0

3 / 2

0

0

1

-2

З

t-7

0

0

(8t +7) / 2

0

(-2t +1) / 2

0

0

0

t-1

Рішення цілочисельне, подивимося, при яких значеннях параметра t воно оптимально:

система не має рішення.

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

- Плани не існують;

- , .

- , .

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

Приклад 4.2.1 Для кожного значення знайти невід'ємне рішення, яке мінімізує лінійну функцію при обмеженнях

, .

Рішення. Перейдемо від нерівностей до равенствам, додаючи до лівих частинах нерівностей додаткові змінні:

, .

Візьмемо і знайдемо симплекс-методом оптимальний план.

Таблиця 4.3.1.

БП

СЧ

1 + t

2

-1

1

1

0

0

2

-4

2

-1

0

1

0

5

3

0

1

0

0

1

З

0

-1

1

3

0

0

0

Таблиця 4.3.2.

БП

СЧ

1 + t

2

-1

1

1

0

0

3 + t

-2

1

0

1

1

0

4-t

1

1

0

-1

0

1

З

-3-3t

-7

4

0

-3

0

0

Таблиця 4.3.3.

БП

СЧ

4 +2 t

0

0

1

2

1

0

3 + t

-2

1

0

1

1

0

1-2t

3

0

0

-2

-1

1

З

-15-7t

1

0

0

-7

-4

0

Таблиця 4.3.4.

БП

СЧ

4 +2 t

0

0

1

2

1

0

(11-t) / 3

0

1

0

-1 / 3

1 / 3

2 / 3

(1-2t) / 3

1

0

0

-2 / 3

-1 / 3

1 / 3

З

0

0

0

-19 / 3

-11 / 3

-1 / 3

Рішення , оптимально і целочисленное при . Нехай . Тоді рішення не є цілочисловим. Складемо додаткове обмеження:

,

, , , .

Додаткове обмеження має вигляд:

,

.

Таблиця 4.3.5.

БП

СЧ

4 +2 t

0

0

1

2

1

0

0

(11-t) / 3

0

1

0

-1 / 3

1 / 3

2 / 3

0

(1-2t) / 3

1

0

0

-2 / 3

-1 / 3

1 / 3

0

-2 / 3

0

0

0

-2 / 3

-1 / 3

-2 / 3

1

З

0

0

0

-19 / 3

-11 / 3

-1 / 3

0

Застосуємо двоїстий симплекс-метод. Отримаємо:

Таблиця 4.3.6.

БП

СЧ

4 +2 t

0

0

1

2

1

0

0

(9-t) / 3

0

1

0

-1

0

0

1

-2t / 3

1

0

0

-1

-1 / 2

0

1 / 2

1

0

0

0

1

1 / 2

1

-3 / 2

З

(-19t-45) / 3

0

0

0

-6

-7 / 2

0

-1 / 2

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

Таблиця 4.3.7.

БП

СЧ

5

3

0

1

0

0

1

7 / 2

-1 / 2

1

0

0

1 / 2

1 / 2

(2t -1) / 2

-3 / 2

0

0

1

-1 / 2

-1 / 2

З

111 / 6

-19 / 2

0

0

0

-1 / 2

- 7 / 2

Отримали, що - Дробові. Складемо додаткове обмеження для :

,

, , , .

Додаткове обмеження має вигляд:

,

.

Таблиця 4.3.8.

БП

СЧ

5

3

0

1

0

0

1

0

7 / 2

-1 / 2

1

0

0

1 / 2

1 / 2

0

(2t -1) / 2

-3 / 2

0

0

1

-1 / 2

-1 / 2

0

-1 / 2

-1 / 2

0

0

0

-1 / 2

-1 / 2

1

З

111 / 6

-19 / 2

0

0

0

-1 / 2

-7 / 2

0

Таблиця 4.3.9.

БП

СЧ

5

3

0

1

0

0

1

0

3

-1

1

0

0

0

0

1

t-1

-2

0

0

1

0

-1

1

1

1

0

0

0

1

1

-2

З

11 4 / 6

-9

0

0

0

0

-3

-1

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

Інтервалами оптимальності цілочисельних планів для різних значень параметра є: - Плани не існують;

- , .

- , .

- , .

Висновок

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

Визначено основні етапи рішення задачі цілочисельного програмування з параметром в цільовій функції. Розглянуто алгоритми розв'язання задач цілочисельного програмування з параметром в цільовій функції і завдань цілочисельного програмування з параметром в системі обмежень, наведені відповідні приклади. За результатами роботи підготовлено і здана до друку стаття "Рішення задачі цілочисельного параметричного програмування". Основні етапи роботи були представлені у вигляді доповіді на підсумковій науковій конференції студентів ФМФ ЧДПУ ім. І. Я. Яковлєва по секції "Алгебра".

Список літератури

  1. Кузнєцов Ю.М., Кузубов В.І., Волощенко А.Б. Математичне програмування. - М.: Вища школа, 1980. - 300 с.

  2. Копилов В.І. Лекції та практичні заняття з математичного програмування. - Навчальний посібник. - Чебоксари: Чуваська державний педагогічний університет імені І. Я. Яковлєва, 2005. - 109 с.

  3. Акулич І.Л. Математичне програмування в прикладах і задачах. - М.: Вища школа, 1986. -

  4. Ашманов С.А. Лінійне програмування. М.: Наука, 1981. - 304 с.

  5. Юдін Д.Б., Гольдштейн Є.Г. Лінійне програмування. - М.: Фізматліт, 1963. - 776 с.

  6. Васильєв Ф.П., Іваницький А.Ю. Лінійне програмування. - М.: Факторіал, 2003. - 347с.


Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Диплом
371.5кб. | скачати


Схожі роботи:
Програмування вирішення завдань
Застосування лінійного програмування для вирішення економічних завдань оптимізація прибутку
Оптимізаційні методи вирішення економічних завдань
Excel вирішення завдань з підбором параметрів
Програмування різних типів завдань
Використання моделювання в навчанні вирішення завдань у 5 класі
Використання інформатики для вирішення економічних завдань
Особливості вирішення завдань за трудовим цивільному кримінального права
Розробка формату зберігання даних програм і вирішення завдань
© Усі права захищені
написати до нас