Навігація
Головна
Симплекс-метод зі штучним базисом (М-метод)Симплекс-методу з природним базисомСимплекс-методу з природним базисомАлгоритм симплекс-методуБ. ШТУЧНІ БУДІВЕЛЬНІ МАТЕРІАЛИ І ВИРОБИМетод лінійного програмування, симплекс-метод і лінійні оцінкиБазис науки про цивілізаціюМетодологічний базис відкритих системМетодологічний базис відкритих системТранспортні особливості базису поставки товарів
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

Симплекс-метод зі штучним базисом (М-метод)

data-override-format="true" data-page-url = "http://stud.com.ua">

Застосовується в тих випадках, коли скрутно знайти первісний опорний план вихідної задачі ЛП, записаної в канонічній формі.

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

В отриманій завданню первісний опорний план очевидний. При застосуванні до цього завдання симплекс-методу оцінки тепер залежатиме "від букви М". Для порівняння оцінок потрібно пам'ятати, що М - досить велике позитивне число, тому з базису будуть виводитися в першу чергу штучні змінні.

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

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

Приклад 2.8. Знайти максимум цільової функції: при умовах

Рішення. Матриця умов містить тільки один одиничний вектор, додамо ще один штучний вектор (штучну неотрицательную змінну в перше обмеження):

Отримаємо наступну М -завдання: знайти максимум цільової функції при умовах

М -завдання вирішуємо симплекс-методом. Початковий опорний план (0, 0, 6, 8), рішення проводимо в симплекс-таблицях (табл. 2.3).

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

Таблиця 2.3

Рішення М -завдання в симплекс-таблицях

Номер

симплекс-

таблиці

Базис

План В

3

2

1

-M

Q

8

2

1

0

1

4

0

1

6

1

1

1

0

6

-

-8м + 6

2М-2

-М-1

0

0

-

3

4

1

data-override-format="true" data-page-url = "http://stud.com.ua">

0,5

0

1

1

2

0

0,5

1

-

14

0

0

0

Отриманий новий опорний план є опорним планом вихідної задачі. Для нього все, тому він є і оптимальним. Таким чином, отриманий оптимальний план вихідної задачі (4, 0, 2) і максимальне значення цільової функції

Приклад 2.9. Вирішити ЗЛП:

Рішення. Наведемо ЗЛП до канонічного виду, перейшовши до задачі "на максимум":

Для знаходження опорного плану переходимо до М -завдання:

Подальше рішення проводимо в симплекс-таблицях (табл. 2.4).

Таблиця 2.4

Рішення ЗЛП М-методом

Номер симплекс-таблиці

Базис

У

-10

5

0

0

0

-M

-M

Q

0

- М

3

2

-1

-1

0

0

1

0

3/2

- М

2

1

1

0

-1

0

0

1

2

0

1

-1

-2

0

0

1

0

0

-

-

-5 М

-3 М + + 10

-5

M

М

0

0

0

-

-10

3/2

1

-1/2

-1/2

0

0

0

-

I

-M

1/2

0

3/2

1/2

-1

0

1

1/3

0

5/2

0

-5/2

-1/2

0

1

0

-

-

-

-М / 2- -15

0

-3 М / 2

-М / 2 +

+5

M

0

0

-

-10

5/3

1

0

-1/3

-1/3

0

-

II

5

1/3

0

1

1/3

-2/3

0

-

0

10/3

0

0

0

-5/3

1

-

-

-

-15

0

0

5

0

0

-

У симплекс-таблице II отриманий опорний план вихідної ЗЛП; оскільки всі симплекс-різниці, то цей план є і оптимальним, тобто (вихідні змінні), (додаткові змінні), при цьому.

При розгляді графічного методу виділяють три особливих випадки рішення ЗЛП. У симплекс-методі ці випадки визначаються наступним чином.

1. Якщо знайдений оптимальний план і оцінки всіх вільних змінних строго більше нуля, то оптимальний план є єдиним; якщо оцінки деяких вільних змінних в оптимальному плані дорівнюють нулю, то цей план буде неєдиним, оскільки введення цих змінних в базис чи не порушує критерію оптимальності і не змінює оптимальне значення цільової функції. Відповідно до цього оптимальний план в табл. 2.2 є єдиним, а в табл. 2.3 та 2.4 - неєдиним (перший особливий випадок).

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

3. Якщо в спрямовуючий стовпці всі елементи a ik непозитивні (див. 2.23), то це свідчить про незамкнутости області визначення ЗЛП; в цьому випадку ЗЛП не має рішення зважаючи необмеженості цільової функції (третій особливий випадок).

Для автоматизації вирішення задач лінійного програмування можуть бути використані стандартні офісні засоби Microsoft Excel - надбудова Пошук рішення, що використовує симплексний метод (лінійна оптимізація за допомогою надбудови Пошук рішення докладно розглянута, наприклад, в літературі [1]).[1]

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

  • [1] Мур Дж., Уедерфорд Л. та ін. Економічне моделювання в Microsoft Excel. Μ .: Вільямс, +2004.
 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
data-override-format="true" data-page-url = "http://stud.com.ua">

Cхожі теми

Симплекс-метод зі штучним базисом (М-метод)
Симплекс-методу з природним базисом
Симплекс-методу з природним базисом
Алгоритм симплекс-методу
Б. ШТУЧНІ БУДІВЕЛЬНІ МАТЕРІАЛИ І ВИРОБИ
Метод лінійного програмування, симплекс-метод і лінійні оцінки
Базис науки про цивілізацію
Методологічний базис відкритих систем
Методологічний базис відкритих систем
Транспортні особливості базису поставки товарів
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук