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

1.1 Поняття опорного та оптимального плану.

1.2 Алгоритм розв’язання задач симплексним методом.

1.3 Деякі зауваження до використання симплексного методу.

1.1. Поняття опорного та оптимального плану.

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

(1.1)

При умовах

, , (1.2)

Де і — задані функції, а — деякі дійсні числа.

Сукупність чисел , що задовольняють обмеженням (1.2) задачі МП, називається Припустимим розв’язком (або Планом).

План , при якому цільова функція (1.1) досягає максимального (мінімального) значення, називається Оптимальним.

1.2. Алгоритм розв’язання задач симплексним методом.

Алгоритм симплексного методу будемо розглядати на прикладі задачі про норок і нутрій, яка описана в Лекції 1. Математична постановка задачі має вигляд:

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

І. Складаємо першу симплексу таблицю (знаходимо опорний план).

1)  Визначимо базисні змінні. Для цього:

A) випишемо вектори з координатами, що відповідають коефіцієнтам системи обмежень при відповідних змінних:

B)Серед виписаних векторів знайдемо ті, що складають систему одиничних.

Нагадаємо, що Одиничним називається вектор, у якого одна координата дорівнює одиниці, а всі інші – нулі. В Систему одиничних векторів повинно входити стільки векторів, скільки координат має кожен з них, при чому таких, що в першому одиниця знаходиться на першому місці, а всі інші координати – нулі; в другому одиниця знаходиться на другому місці, а всі інші нулі і т. д.

В нашій задачі систему одиничних складають вектори .

C)  Змінні, що відповідають одиничним векторам, називаються Базисними. В нашому випадку це змінні .

2)  Заповнюємо таблицю:

№	Базис	Сб	План	16	6	0	0	0	Оціночне відношення
Х1	Х2	Х3	Х4	Х5
1	Х3	0	180	2	6	1	0	0	90
2	Х4	0	240	4	1	0	1	0	60
3	Х5	0	426	6	7	0	0	1	71
M+1			0	-16	-6	0	0	0

A)  В стовпчик „Базис” записуємо базисні змінні.

B)  Над змінними запишемо коефіцієнти цільової функції при відповідних змінних.

C)  В стовпчик „Сб” Записуємо коефіцієнти цільової функції при базисних змінних.

D)  В стовпчик „План” записуємо координати вектора Р0.

E)  В стовпчики Х1, Х2, …, Х5 Заносять відповідно координати векторів Р1, Р2, …, Р5.

F)  Заповнюють рядок (m+1):

—  на перетині (m+1)-го рядка і стовпчика „План” записують скалярний добуток двох векторів: і .

—  на перетині (m+1)-го рядка і стовпчиків Х1, Х2, …, Х5 відповідно записують значення виразів: , де , а
— коефіцієнти системи обмежень, що записані в таблиці над змінними . Так, наприклад, на перетині (m+1)-го рядка і стовпчика Х1 Записуємо число .

ІІ. Оцінюємо складений план на оптимальність. Можливі три випадки:

1)  (m+1)-й рядок не містить від’ємних елементів, значить план вважається Оптимальним. Перехід до пункту V.

2)  Серед чисел (m+1)-го рядка знаходяться від’ємні, а у відповідному до цього числа стовпчику немає жодного додатного. Тоді задача розв’язків не має.

3)  Серед чисел (m+1)-го рядка знаходяться від’ємні, і у відповідному до цього числа стовпчику є хоча б одне додатне число. Це означає, що опорний план можна покращити. В даному випадку переходять до нової симплексної таблиці.

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

1)  Знаходження нового базису:

A)  визначення змінної, що вводиться в новий базис: серед чисел (m+1)-го рядка, що знаходяться у стовпчиках Х1, Х2, …, Х5, знаходять найменше від’ємне. Стовпчик, в якому це число знаходиться, називається Направляючим, а змінна, що в ньому знаходиться, вводиться в новий базис.

B)  визначення змінної, що виводиться з базису: ділять почленно елементи стовпчика „План” на Додатні елементи направляючого стовпчика. Отримані частки записують в стовпчик „Оціночні відношення” симплексної таблиці. Серед них знаходять найменшу. Рядок, якому вона відповідає, називається Направляючим, а змінна, що в ньому знаходиться, виводиться з базису.

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

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

2)  Заповнення нової симплексної таблиці:

№	Базис	Сб	План	16	6	0	0	0	Оціночне відношення
Х1	Х2	Х3	Х4	Х5
1	Х3	0	60	0	5/2	1	-1/2	0	24
2	Х1	16	60	1	¼	0	¼	0	240
3	Х5	0	66	0	11/2	0	-3/2	1	12
M+1			960	0	-2	0	4	0

A)  В стовпчик „Базис” записуємо базисні змінні.

B)  Над змінними запишемо коефіцієнти цільової функції при відповідних змінних.

C)  В стовпчик „Сб” Записуємо коефіцієнти цільової функції при базисних змінних.

D)  Елементи направляючого рядка ділимо на генеральний елемент.

E)  На перетині однойменних рядків і стовпчиків ставимо одиниці, всі інші елементи базисних стовпчиків – нулі.

F)  Клітини таблиці, що залишилися, заповнюємо за правилом чотирикутника:

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

180 –елемент попередньої таблиці, що знаходився в клітині (х3, План).

2 – відповідний елемент по рядку. Знаходимо його, проводячи уявну лінію від попереднього елемента до перетину з проведеною вертикальною лінією.

240 — відповідний елемент по стовпчику. Знаходимо його, проводячи уявну лінію від попереднього елемента до перетину з проведеною горизонтальною лінією.

4 – генеральний елемент.

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

№	Базис	Сб	План	16	6	0	0	0	Оціночні відношення
Х1	Х2	Х3	Х4	Х5
1	Х3	0	30	0	0	1	2/11	-5/11
2	Х1	16	57	1	0	0	7/22	-1/22
3	Х2	6	12	0	1	0	-3/11	2/11
M+1			984	0	0	0	38/11	4/11

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

V. Виписують отриману відповідь із стовпчика „План”. На перетині (m+1)-го рядка і стовпчика „План” знаходиться значення цільової функції. Інші елементи стовпчика план показують значення базисних змінних. Якщо змінна не увійшла в базис, її значення дорівнює нулю.

Відповідно до нашого прикладу . Або, фермер отримає максимальний прибуток в розмірі 984 грош. од., якщо буде вирощувати 57 норок і 12 нутрій.

1.3. Деякі зауваження до використання симплексного методу

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

2)  Якщо за умовою задачі цільова функція була спрямована на мінімум, то отримане кінцеве значення цільової функції із стовпчика „План” слід помножити на (-1).

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

2. Термінологічний словник

Правило прямокутника

Н. Е.- новий елемент; С. Е.- старий елемент; В. Е.Р.- відповідний елемент по рядку; В. Е.С.- відповідний елемент по стовпчику; Г. Е.- генеральний елемент.

Направляючий (генеральний) стовпчик – стовпчик, якому відповідає найбільший по модулю серед від’ємних елементів Δі m+1-го рядка симплексної таблиці.

3. Рекомендована література

1. Богаєнко І. М., Григорків B. C., Бойчук М. В., Рюмашин М.0. Математичне програмування: Навч. посіб. — К.: Логос, 1996.

2. Бугір М. К. Зошит для практичних занять з математичного програмування. — Тернопіль: Підручники і посібники, 1999.

3. Бугір М. К. Математика для економістів. Лінійна алгебра, лінійні моделі: Навч. посіб. — К.: ВЦ «Академія», 1998.

4. Гвоздинський А. М. Оптимізаційні задачі в організаційному управлінні: Навч. посіб.-Харків: ХДТУР, 1997.

5. Гетманцев В. Д. Лінійна алгебра і лінійне програмування:

Навч. посіб. — К.: Либідь, 2001.

6. Григорків B. C., Бойчук М. В. Практикум з математичного програмування: Навч. посіб. — Чернівці: Прут, 1995.

7. Деордица Ю. С., Савченко В. Т. Компьютерные технологии в экономике и менеджменте: Учеб. пособие. — Луганск: ВУГУ, 1999.