Рішення та постоптімальний аналіз завдання лінійного програмування

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

БЕРДЯНСЬКИЙ УНІВЕРСИТЕТ МЕНЕДЖМЕНТУ І БІЗНЕСУ

КАФЕДРА МАТЕМАТИКИ ТА МАТЕМАТИЧНИЙ МЕТ0ДІВ

Курсова робота

з дисципліни

«Математичні методи дослідження операцій»

на тему

Рішення та постоптімальний аналіз завдання лінійного програмування

Варіант № 3 / 4

1. Теоретичні відомості

1.1 Симплекс-метод

Теорема (фундаментальна). Якщо ЗЛП має оптимальне рішення (в обмеженій області завжди, а в необмеженій - залежно від обмеженості цільової функції Z), то воно збігається, принаймні, з одним із допустимих базисних рішень (ДБР) системи обмежень.

Згідно фундаментальної теоремі замість дослідження нескінченної кількості допустимих рішень, необхідно дослідити лише кінцеве число ДБР. Таким чином, принципова схема рішення ЗЛП така:

знайти всі ДБР;

обчислити для кожного з них відповідне значення ЦФ z;

порівняти та визначити найкраще.

Але, в загальному випадку при великих значеннях п і т кількість ДБР може бути величезним (близько З _п ^т) і практичне здійснення перебору всіх ДБР стане неможливим. Ці труднощі обумовлені тим, що вказана принципова схема пов'язана з безладним перебором ДБР, без обліку, наскільки нове проверяемое ДБР змінює ЦФ z і наближає чи воно нас до шуканого оптимуму. Якщо ж вказаний перебір ДБР виробляти цілеспрямовано, домагаючись на кожному кроці монотонного зміни ЦФ z, тобто щоб кожне наступне ДБР було краще попереднього (або принаймні не гірше), то число аналізованих ДБР можна різко скоротити.

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

> Спосіб визначення вихідного ДБР;

> Правило переходу до наступного "краще" ДБР;

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

Табличний симплекс-метод

Нехай для вихідної ЗЛП поставлено початкова ДБР, базис якого утворюють перші т стовпців матриці А. Введемо нову змінну z і за допомогою елементарних перетворень Жордана-Гаусса перетворимо розширену систему до діагональної формі щодо змінних z, x _1, x ₂ ,..., x _m:

Даною діагональної формі надалі будемо ставити у відповідність наступну таблицю:

Надалі другий стовпець будемо опускати!

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

Схема табличного симплекс-метода.

Крок 0. Початковий крок.

Нехай задано ДБР х ° вихідної завдання. Побудуємо відповідну цьому ДБР х ° симплекс-таблицю.

Крок 1. Перевірка умови оптимальності.

Якщо коефіцієнти z-рядки d _{0 J,} j = 1, m невід'ємні, то припинити обчислення: поточної симплекс-таблиці відповідає оптимальне ДБР.

Крок 2. Вибір ведучого шпальти.

Серед коефіцієнтів d ₀ j, j = 1, n вибрати негативний. Нехай ми вибрали d _{0 p.} Тоді р-й стовпець буде ведучим. Мінлива х _р буде вводитися в безліч базисних змінних.

Крок 3. Вибір ведучої рядка.

Якщо коефіцієнти a _ip, i = 1, m непозитивно, то припинити обчислення:

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

Елемент таблиці a _qp на перетині провідних рядка та стовпця називається провідним елементом.

Крок 4. Перехід до нової симплекс-таблиці.

Використовуючи перетворення Жордана-Гаусса над СЛАУ, в симплекс-таблице зробити провідний елемент рівним одиниці, а всі інші коефіцієнти ведучого шпальти рівними нулю. Зліва від таблиці в q-ої рядку запишемо змінну х _р.

Перейти на крок 1.

1.2 Постоптімальний аналіз

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

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

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

1. Компоненти вектора обмежень b _t

Після знаходження оптимального рішення. Видається цілком логічним з'ясувати, як відіб'ється на оптимальному рішенні зміна запасів ресурсів. Зазначимо, що нерівності моделі типу "<" зазвичай можуть бути інтерпретовані, як обмеження на використання лімітованого ресурсу. А обмеження типу ">" можуть бути інтерпретовані, як деякі вимоги до модельованого процесу.

При аналізі змін запасів ресурсів особливо важливими є два наступних аспекти:

> На скільки можна збільшити (зменшити) запас деякого ресурсу для поліпшення отриманого оптимального значення цільової функції z?

> На скільки можна знизити (збільшити) запас деякого ресурсу при збереженні отриманого оптимального значення цільової функції z?

2. Коефіцієнти ЦФ Cj

Визначається межі допустимих змін коефіцієнтів цільової функції.

> Який діапазон зміни (збільшення або зменшення) того чи іншого коефіцієнта цільової функції, при якому не відбувається зміна оптимального рішення?

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

1. Існує діапазон зміни А коефіцієнтів ЦФ як базисних, так і небазисних змінних, в яких поточне оптимальне рішення залишається оптимальним.

- Для небазисних змінних існує тільки нижня або верхня межа;

- Для базисних - зазвичай існують і нижня і верхня межі.

2. Зміна коефіцієнта ЦФ базисної змінної завжди призводить до зміни значення ЦФ.

3. Ефект від зміни коефіцієнтів ЦФ може розглядатися з двох позицій:

- З точки зору збуту нас цікавлять рівноважні ціни;

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

Знаходження діапазонів зміни запасів ресурсів

Недефіцитні ресурси

Якщо в оптимальному рішенні додаткова змінна S i - ro обмеження базисна, то це обмеження є не зв'язує (не активним у точці оптимуму), а ресурс - недефіцитних. У цьому випадку значення додаткової базисної змінної дає діапазон зміни, в якому відповідна компонента d _i може:

• Зменшаться (у разі знака обмеження "<")

• Збільшується (у разі знака обмеження ">").

Нехай S ⁰ - Значення відповідної додаткової змінної в точці оптимуму. Тоді рішення залишається допустимим і оптимальним в діапазоні bi + Δ, де

Дефіцитні ресурси

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

Для обмеження типу "<":

Для обмеження типу ">":

Зміна коефіцієнтів Ц.Ф.

Існує діапазон зміни коефіцієнтів 'цільової функції як базисних так і не базисних змінних, в яких отримане рішення залишається оптимальним. Зміна коефіцієнта базисної змінної в межах цього діапазону призводить до зміни значення цільової функції, оскільки Z = С ^т _в * β, а одна з компонент вектора Св змінюється. Зміна коефіцієнта небазисной змінної не змінює значення завдання.

Для завдання на m ах:

Базисні перемінні:

Для базисної змінної діапазон стійкості, в якому може змінюватися коефіцієнт Ci, залишаючи поточне рішення оптимальним, задається виразом: Ci + Δ

де dj - відносна оцінка змінної xj в поточному оптимальному рішенні.

E сли відсутні відповідно.

Чи не базисні змінні:

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

Для завдання на min: Базисні перемінні:

Для базисної змінної діапазон стійкості, в якому може змінюватися коефіцієнт С i, залишаючи поточне рішення оптимальним, задається виразом: С i + Δ

He базисні змінні:

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

(D _N) <Δ <∞

2. Змістовна постановка задачі

Варіант 3 / 2

Транспортна компанія для перевезення інжиру з Багдада в Мекку використовує мулів, одногорбих і двогорбих верблюдів. Двогорбий верблюд може перевезти - 1000 фунтів, одногорбий - 500 фунтів, а мул - 300 фунтів. За один перехід двогорбий верблюд споживає 2 стоси сіна і 40 галонів води. Одногорбий верблюд споживає 2 стоси сіна і 30 галонів води. Мул - 1 стос сіна і 10 галонів води. Пункти постачання компанії, розташовані в різних оазисах уздовж шляху, можуть видати не більше 900 галонів води і 35 кіп сіна. Верблюди і мули орендуються у пастуха поблизу Багдада, орендна плата дорівнює 12 піастрам за двогорбого верблюда, 5 піастрам за одногорбого і 4 піастрам за мула.

Якщо компанія повинна перевести 8000 фунтів інжиру з Багдада в Мекку, скільки треба використовувати верблюдів і мулів для мінімізації орендної плати пастуху?

3. Математична постановка задачі

Змінні:

Х1 - Двогорбий верблюд

Х2 - одногорбий верблюд

Х3 - Мул

Цільова функція - мінімізація орендної плати.

Z min = 12Х1 + 5х2 + 4х3

Обмеження:

Використання ресурсу «вода» не більше 900 галонів:

40Х1 + 30х2 + 10х3 <900

Використання ресурсу «сіно» не більше 35 кіп:

3х1 + 2Х2 + Х3 <35

Компанія повинна перевести 8000 фунтів інжиру:

1000Х1 + 500Х2 + 300х3 = 8000

Всі змінні повинні бути не негативні:

Х1, Х2, Х3> 0

4. Рішення задачі симплекс-методом

ЦФ:

Zmin = 12 X 1 + 5 X 2 + 4 X 3

Обмеження:

40 X 1 + 30 X 2 + 10 X 3 <900

3 X 1 + 2 X 2 + X 3 <35

1000 X 1 + 500 X 2 + 300 X 3 = 8000

X 1, X 2, X 3> 0

Наведемо завдання до канонічної формі і введемо штучні змінні:

Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 - MR1

40X1 + 30X2 + 10X3 + 0S1 = 900

3X1 + 2X2 + X3 + 0S2 = 35

1000X1 + 500X2 + 300X3 + R1 = 8000

X1, X2, X3> 0

R1 = - 1000X1 - 500X2 - 300X3 + 8000

Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 - M (- 1000X1 - 500X2 - 300X3 + 8000) = (12 + 1000M) X1 + (5 + 500M) X2 + (4 + 300M) X3 - 8000M

Z + (-12 - 1000M) X1 + (-5 - 500M) X2 + (-4 - 300M) X3 = - 8000M

Складаємо симплекс таблицю:

У результаті: Z = 80, X 1 = 0, X 2 = 16, X 3 = 0

5. Постоптімальний аналіз рішення

5.1 Визначення статусу та цінності ресурсів

Zmin = 12 X 1 + 5 X 2 + 4 X 3

40X1 + 30X2 + 10X3 + S1 = 900

3 X 1 + 2 X 2 + X 3 + S 2 = 35

1000 X 1 + 500 X 2 + 300 X 3 = 8000

Двоїста задача має вигляд:

ω max = 900Y1 + 35Y2 + 8000Y3

40Y1 + 3Y2 + 1000Y3 <12 (X1)

30Y1 + 2Y2 + 500Y3 <5 (X2)

10Y1 + 1Y2 + 300Y3 <4 (X3)

Y1 <0 (S1)

Y 2 <0 (S 2)

У оптимальної таблиці прямої задачі базисними змінними є S 1, S 2 і X 2. Згідно з співвідношеннями доповнює нежорсткої відповідні цим змінним обмеження - нерівності двоїстої задачі в точці оптимуму виконуються як рівності. Таким чином, отримуємо наступну систему лінійних рівностей.

30 Y 1 + 2 Y 2 + 500 Y 3 = 5 Y 1 = 0

Y 1 = 0 Y 2 = 0

Y 2 = 0 Y 3 = 0,01

Рішення отриманої системи лінійних рівнянь:

Y 1 = 0; Y 2 = 0; Y 3 = 0,01

За основною теоремою двоїстості рішення прямої і двоїстої завдання повинні збігатися:

ω = 900 * 0 + 35 * 0 + 8000 * 0.01 = 80 => ω = Z

5.2 Цінності ресурсів

Відповідно до теорії подвійності, двоїста мінлива Y i (і = 1,2,3) визначає цінність і-го ресурсу - величину, на яку зміниться значення цільової функції при збільшенні на одиницю рівня запасу відповідного ресурсу.

Таким чином, при зміні в деяких межах рівнів запасів ресурсів маємо:

- При збільшенні на 1 одиницю ресурсу «вода» не приведуть до зміни

- При збільшенні на 1 одиницю ресурсу «сіно» не приведуть до зміни

- При збільшенні на 1 фунта перевезення, підвищиться орендна плата на 0,01 піастрів.

5.3 Визначення допустимих діапазонів зміни рівнів запасів ресурсів

Недефіцитні ресурси:

Мінлива S 1 - базисна, ресурс «вода» недефіцитних.

Обмеження має знак «<»

-420 <Δ1 <∞

Абсолютний діапазон зміни:

480 < b 1 <∞

Мінлива S 2 - базисна, ресурс «сіно» недефіцитних.

Обмеження має знак «<»

-3 <Δ2 <∞

Абсолютний діапазон зміни:

32 < b 2 <∞

Дефіцитні ресурси:

Мінлива R1 - не базисна, ресурс дефіцитний.

-8000 <Δ3 <750

Абсолютний діапазон зміни:

0 < b 3 <8750

5.4 Визначення допустимих діапазонів зміни коефіцієнтів цільової функції

Базисні перемінні:

Мінлива X 2 - базисна:

- ∞ <Δ2 <1

Абсолютний діапазон зміни коефіцієнта ЦФ:

- ∞ <С2 <13

Чи не базисні змінні:

Мінлива Х1 - не базисна:

2 <Δ1 <∞

Абсолютний діапазон зміни коефіцієнта ЦФ:

14 < C 1 <∞

Мінлива Х3 - не базисна:

1 <Δ3 <∞

Абсолютний діапазон зміни коефіцієнта ЦФ:

5 < C 3 <∞

6. Відповідь

Оптимальне рішення завдання:

- Використання «двогорбий верблюд» - 0

- Використання «одногорбий верблюд» - 16

- Використання «мул» - 0

При цьому оптимум = 80 піастрам

Діапазон зміни рівня запасів в:

- Запаси води -420 <Δ1 <∞

- Запаси сіна -3 <Δ2 <∞

- Співвідношення -8000 <Δ3 <750

Абсолютні діапазони зміни рівнів запасів:

- Запаси води 480 < b 1 <∞

- Запаси сіна 32 < b 2 <∞

- Співвідношення 0 < b 3 <8750

Цінність ресурсів:

- При збільшенні на 1 одиницю ресурсу «вода» не приведуть до зміни

- При збільшенні на 1 одиницю ресурсу «сіно» не приведуть до зміни

- При збільшенні на 1 фунта перевезення, підвищиться орендна плата на 0,01 піастрів.

Діапазон зміни коефіцієнтів:

- Двогорбий верблюд 2 <Δ1 <∞

- Одногорбий верблюд ∞ <Δ2 <1

- Мул 1 <Δ3 <∞

Абсолютні діапазони зміни:

- Двогорбий верблюд 14 < C 1 <∞

- Одногорбий верблюд - ∞ <С2 <13

- Мул 5 < C 3 <∞

7. Завдання на застосування графічного способу розв'язання задач лінійного програмування

№ 28

Z = 2 X 1 + X 2 → min

X 1 - X 2> 4 (1)

X 1 + X 2> 4 (2)

4 X 1 - X 2 <16 (3)

7 X 1 + X 2 <14 (4)

X 1, X 2> 0

Відповідь: Ні рішень

№ 58

Z = - X 1 + 3 X 2 → max

-2 X 1 + X 2 <2 (1)

X 1 + 2 X 2> 6 (2)

X 1> 2 (3)

3 X 1 + 4X2 <24 (4)

X 1, X2> 0

Відповідь: X 1 = 2

X 2 = 4.5

Z = 11.5

СПИСОК ЛІТЕРАТУРИ

1. Дослідження операцій. У 2-ух томах. Методологічні основи і математичні методи. / Под ред. Дж. Моудера, С. Елмаграбі. - М.: Мир, 1981. Т. 1.-712 с.

2. Муртаф Б. Сучасне лінійне програмування. Теорія і практика-М.: Світ, 1984 .- 224 с. Т.

3. Таха X. Введення в дослідження операцій: У 2-ух томах. - М.: Мир, 1985. Т. 1.-325С.

4. Каліхман І.Л. Лінійна алгебра та програмування. - М.: Вища школа, 1967.-428 с.

5. Конспект лекцій.