Сподобалось? Додати до закладок

Розв'язання задач симплекс-методом: приклади онлайн

Завдання 1.Компанія виробляє полиці для ванних кімнат двох розмірів – А та В. Агенти з продажу вважають, що на тиждень на ринку може бути реалізовано до 550 полиць. Для кожної полиці типу А потрібно 2 м2 матеріалу, а для полиці типу - 3 м2 матеріалу. Компанія може отримати до 1200 м2 матеріалу на тиждень. Для виготовлення однієї полиці типу А потрібно 12 хв машинного часу, а виготовлення однієї полиці типу В - 30 хв; машину можна використовувати 160 годин на тиждень. Якщо прибуток від продажу полиць типу А становить 3 грошові одиниці, як від полиць типу У - 4 ден. од., то скільки полиць кожного типу слід випускати на тиждень?

Завдання 2.Вирішити завдання лінійного програмуваннясимплекс-методом.

Завдання 3.Підприємство виробляє 3 види продукції: А1, А2, А3, використовуючи сировину двох типів. Відомі витрати сировини кожного типу на одиницю продукції, запаси сировини на запланований період, а також прибуток від одиниці продукції кожного виду.

1. Скільки виробів кожного виду необхідно зробити, щоб отримати максимум прибутку?
2. Визначити статус кожного виду сировини та її питому цінність.
3. Визначити максимальний інтервал зміни запасів кожного виду сировини, у якого структура оптимального плану, тобто. номенклатура випуску не зміниться.
4. Визначити кількість продукції і прибуток від випуску зі збільшенням запасу однієї з дефіцитних видів сировини до максимально можливої ​​(не більше цієї номенклатури випуску) величини.
5. Визначити інтервали зміни прибутку від одиниці продукції кожного виду, за яких отриманий оптимальний планне зміниться.

Завдання 4.Розв'язати задачу лінійного програмування симплексним методом:

Завдання 5.Розв'язати задачу лінійного програмування симплекс-методом:

Завдання 6.Розв'язати задачу симплекс-методом, розглядаючи як початковий опорного плану, план, наведений за умови:

Завдання 7.Розв'язати задачу модифікованим симплекс-методом.
Для виробництва двох видів виробів А та Б використовується три типи технологічного обладнання. На виробництво одиниці виробу А обладнання першого типу використовується а1 = 4 години, обладнання другого типу а2 = 8 годин, а обладнання третього типу а3 = 9 годин. На виробництво одиниці виробу Б обладнання першого типу використовується б1 = 7 годин, обладнання другого типу б2 = 3 години, а обладнання третього типу б3 = 5 годин.
На виготовлення цих виробів обладнання першого типу може працювати не більше t1=49 годин, обладнання другого типу не більше t2=51 годин, обладнання третього типу не більше t3=45 годин.
Прибуток від одиниці готового виробу А становить АЛЬФА=6 рублів, а вироби Б – БЕТТА=5 рублів.
Скласти план виробництва виробів А і Б, що забезпечує максимальний прибуток від реалізації.

Завдання 8.Знайти оптимальне рішення двоїстим симплекс-методом

Розглянуто приклад розв'язання задачі симплекс методом, а також приклад розв'язання двоїстої задачі.

Умова задачі

Для реалізації трьох груп товарів комерційне підприємствомає в своєму розпорядженні три види обмежених матеріально-грошових ресурсів у кількості b 1 = 240, b 2 = 200, b 3 = 160 одиниць. У цьому на продаж 1 групи товарів на 1 тис. крб. товарообігу витрачається ресурсу першого виду у кількості a 11 = 2 одиниці, ресурсу другого виду у кількості a 21 = 4 одиниці, ресурсу третього виду у кількості a 31 = 4 одиниці. Для продажу 2 та 3 груп товарів на 1 тис. руб. товарообігу витрачається відповідно ресурсу першого виду в кількості a 12 = 3, a 13 = 6 одиниці, ресурсу другого виду в кількості a 22 = 2, a 23 = 4 одиниці, ресурсу третього виду в кількості a 32 = 6, a 33 = 8 одиниць . Прибуток від трьох груп товарів на 1 тис. крб. товарообігу становить відповідно c1 = 4, c2 = 5, c3 = 4 (тис. руб.). Визначити плановий обсяг та структуру товарообігу так, щоб прибуток торговельного підприємствабула максимальною.

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

Розв'язання задачі симплекс методом

Нехай x 1 , x 2 , x 3 - кількість реалізованих товарів, у тис. руб., 1, 2, 3-ї груп, відповідно. Тоді математична модельзавдання має вигляд:

F = 4 · x 1 + 5 · x 2 + 4 · x 3 -> max

0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Вирішуємо симплекс методом.

Вводимо додаткові змінні x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, щоб нерівності перетворити на рівність.

Як базис візьмемо x 4 = 240; x 5 = 200; x6 = 160.

Дані заносимо в симплекс таблицю

Симплекс таблиця №1

Цільова функція:

0 · 240 + 0 · 200 + 0 · 160 = 0

Обчислюємо оцінки за формулою:

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

Оскільки є негативні оцінки, то план не є оптимальним. Найнижча оцінка:

Вводимо змінну x 2 в базис.

Визначаємо змінну, що виходить із базису. Для цього знаходимо найменше невід'ємне відношення для шпальти x 2 .

= 26.667

Найменше невід'ємне: Q3 = 26.667. Виводимо змінну x 6 з базису

3-й рядок ділимо на 6.
З 1-го рядка віднімаємо 3-й рядок, помножений на 3
З 2-го рядка віднімаємо 3-й рядок, помножений на 2

Обчислюємо:

Отримуємо нову таблицю:

Симплекс таблиця №2

Цільова функція:

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Обчислюємо оцінки за формулою:

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Оскільки є негативна оцінка Δ 1 = - 2/3, то план не є оптимальним.

Вводимо змінну x 1 у базис.

Визначаємо змінну, що виходить із базису. Для цього знаходимо найменше невід'ємне відношення для шпальти x 1 .

Найменше невід'ємне: Q 3 = 40. Виводимо змінну x 2 з базису

3-й рядок ділимо на 2/3.
З 2-го рядка віднімаємо 3-й рядок, помножений на 8/3

Обчислюємо:

Отримуємо нову таблицю:

Симплекс таблиця №3

Цільова функція:

0 · 160 + 0 · 40 + 4 · 40 = 160

Обчислюємо оцінки за формулою:

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Оскільки негативних оцінок немає, то план є оптимальним.

Рішення завдання:

Відповідь

x 1 = 40; x 2 = 0; x3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

Тобто необхідно реалізувати товар першого виду обсягом 40 тис. крб. Товар 2-го та 3-го видів реалізовувати не треба. При цьому максимальний прибутокскладе Fmax = 160 тис. руб.

Розв'язання двоїстої задачі

Подвійне завдання має вигляд:

Z = 240 · y 1 + 200 · y 2 + 160 · y 3 -> min

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3> = 0))) (~)">!}

Вводимо додаткові змінні y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, щоб нерівності перетворити на рівність.

Сполучені пари змінних прямої та двоїстої задач мають вигляд:

З останньої симплекс таблиці № 3 прямої задачі знаходимо рішення двоїстої задачі:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

. Алгоритм симплекс-методу

Приклад 5.1.Розв'язати таке завдання лінійного програмування симплекс-методом:

Рішення:

I ітерація:

х3, х4, х5, х6 х1,х2. Висловимо базисні змінні через вільні:

Наведемо цільову функцію наступного виду:

На основі отриманого завдання сформуємо вихідну симплекс-таблицю:

Таблиця 5.3

Вихідна симплекс-таблиця

				Оціночні відносини

Відповідно до визначення базисного рішення вільні змінні дорівнюють нулю, а значення базисних змінних – відповідним значенням вільних чисел, тобто:

3 етап: перевірка сумісності системи обмежень ЗЛП.

На даній ітерації (у таблиці 5.3) ознака несумісності системи обмежень (ознака 1) не виявлено (тобто немає рядка з негативним вільним числом (крім рядка цільової функції), в якому не було б хоча б одного негативного елемента (тобто · негативного коефіцієнта при вільній змінній)).

На даній ітерації (у таблиці 5.3) ознака необмеженості цільової функції (ознака 2) не виявлено (тобто немає колонки з негативним елементом у рядку цільової функції (крім колонки вільних чисел), у якій не було б хоча б одного позитивного елемента) .

Так як знайдене базисне рішення не містить негативних компонентів, воно є допустимим.

6 етап: перевірка оптимальності.

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

Так як знайдене базисне рішення допустиме, то пошук колонки будемо проводити за наступною схемою: визначаємо колонки з негативними елементами в рядку цільової функції (крім колонки вільних чисел). Відповідно до таблиці 5.3 таких колонок дві: колонка « х1і колонка « х2». З таких колонок вибирається та, що містить найменший елемент у рядку цільової функції. Вона і буде вирішальною. Колонка « х2» містить найменший елемент (–3) у порівнянні з колонкою « х1

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

Таблиця 5.4

Вихідна симплекс-таблиця

У таблиці 5.4 найменше позитивне оцінне відношення відповідає рядку « х5», отже, вона буде вирішальною.

Елемент, розташований на перетин роздільної колонки і рядка, приймається як роздільна здатність. У нашому прикладі – це елемент, який розташований на перетині рядка. х5і колонки « х2».

Дозволяючий елемент показує одну базисну і одну вільну змінні, які необхідно поміняти місцями в симплекс-таблиці, для переходу до нового «поліпшеного» базового рішення. У даному випадкуце змінні х5і х2, у новій симплекс-таблиці (таблиці 5.5) їх міняємо місцями.

9.1. Перетворення роздільної здатності елемента.

Роздільний елемент таблиці 5.4 перетворюється таким чином:

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

9.2. Перетворення роздільної здатності.

Елементи роздільної здатності таблиці 5.4 ділимо на роздільний елемент даної симплекс-таблиці, результати вписуються в аналогічні осередки нової симплекс-таблиці (таблиці 5.5). Перетворення елементів роздільної здатності наведено в таблиці 5.5.

9.3. Перетворення роздільної здатності колонки.

Елементи роздільної здатності колонки таблиці 5.4 ділимо на роздільний елемент даної симплекс-таблиці, а результат береться з зворотним знаком. Отримані результати вписуються в аналогічні осередки нової симплекс-таблиці (таблиці 5.5). Перетворення елементів роздільної здатності колонки наведені в таблиці 5.5.

9.4. Перетворення інших елементів симплекс-таблиці.

Перетворення інших елементів симплекс-таблиці (тобто елементів не розміщених у роздільній здатності і колонці) здійснюється за правилом «прямокутника».

Наприклад, розглянемо перетворення елемента, розташованого на перетині рядка « х3» та колонки «», умовно позначимо його « х3». У таблиці 5.4 подумки викреслюємо прямокутник, одна вершина якого розташовується в клітці, значення якої перетворимо (тобто в клітці « х3»), а інша (діагональна вершина) – у клітці з роздільним елементом. Дві інші вершини (другий діагоналі) визначаються однозначно. Тоді перетворене значення клітини х3» дорівнюватиме колишньому значенню даної клітини мінус дріб, у знаменнику якої роздільний елемент (з таблиці 5.4), а в чисельнику добуток двох інших невикористаних вершин, тобто:

« х3»: .

Аналогічно перетворюються значення інших клітин:

« х3 х1»: ;

« х4»: ;

« х4 х1»: ;

« х6»: ;

« х6 х1»: ;

«»: ;

« х1»: .

В результаті даних перетворень отримали нову симплекс-таблицю(Таблиця 5.5).

II ітерація:

1 етап: складання симплекс-таблиці.

Таблиця 5.5

Симплекс-таблицяII ітерації

				Оціночні відносини

2 етап: визначення базового рішення.

В результаті проведених симплекс-перетворень отримали нове базове рішення (таблиця 5.5):

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

Не сумісність системи обмежень відповідно до ознаки 1 у таблиці 5.5 не виявлено.

4 етап: перевірка обмеженості цільової функції.

Необмеженість цільової функції відповідно до ознаки 2 у таблиці 5.5 не виявлено.

5 етап: перевірка допустимості знайденого базисного рішення.

Знайдене базисне рішення відповідно до ознаки 4 не оптимальне, оскільки у рядку цільової функції симплекс-таблиці (таблиця 5.5) міститься негативний елемент: -2 (вільне число даного рядка при розгляді цієї ознаки не враховується). Отже, переходимо до 8 етапу.

8 етап: визначення роздільної здатності елемента.

8.1. Визначення роздільної здатності колонки.

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

8.2. Визначення роздільної здатності рядка.

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

Таблиця 5.6

Симплекс-таблицяII ітерації

				Оціночні відносини
				3/1 = 3 - min

9 етап: перетворення симплекс-таблиці.

Перетворення симплекс-таблиці (таблиці 5.6) виконуються аналогічно, як і попередньої ітерації. Результати перетворень елементів симплекс-таблиці наведено у таблиці 5.7.

III ітерація

За результатами симплекс-перетворень попередньої ітерації складаємо нову симплекс-таблицю:

Таблиця 5.7

Симплекс-таблицяIII ітерації

				Оціночні відносини

2 етап: визначення базового рішення.

В результаті проведених симплекс-перетворень отримали нове базове рішення (таблиця 5.7):

3 етап: перевірка сумісності системи обмежень.

Не сумісність системи обмежень відповідно до ознаки 1 у таблиці 5.7 не виявлено.

4 етап: перевірка обмеженості цільової функції.

Необмеженість цільової функції відповідно до ознаки 2 у таблиці 5.7 не виявлено.

5 етап: перевірка допустимості знайденого базисного рішення.

Знайдене базисне рішення відповідно до ознаки 3 допустиме, оскільки не містить негативних компонентів.

6 етап: перевірка оптимальності знайденого базового рішення.

Знайдене базисне рішення відповідно до ознаки 4 не оптимальне, оскільки у рядку цільової функції симплекс-таблиці (таблиця 5.7) міститься негативний елемент: –3 (вільне число цього рядка при розгляді даної ознаки не враховується). Отже, переходимо до 8 етапу.

8 етап: визначення роздільної здатності елемента.

8.1. Визначення роздільної здатності колонки.

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

8.2. Визначення роздільної здатності рядка.

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

Таблиця 5.8

Симплекс-таблицяIII ітерації

				Оціночні відносини
				5/5 = 1 - min

9 етап: перетворення симплекс-таблиці.

Перетворення симплекс-таблиці (таблиці 5.8) виконуються аналогічно, як і попередньої ітерації. Результати перетворень елементів симплекс-таблиці наведено у таблиці 5.9.

IV ітерація

1 етап: побудова нової симплекс-таблиці.

За результатами симплекс-перетворень попередньої ітерації складаємо нову симплекс-таблицю:

Таблиця 5.9

Симплекс-таблицяIV ітерації

				Оціночні відносини
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

2 етап: визначення базового рішення.

В результаті проведених симплекс-перетворень отримали нове базисне рішення, згідно з таблицею 5.9.

3 етап: перевірка сумісності системи обмежень.

Не сумісність системи обмежень відповідно до ознаки 1 у таблиці 5.9 не виявлено.

4 етап: перевірка обмеженості цільової функції.

Необмеженість цільової функції відповідно до ознаки 2 у таблиці 5.9 не виявлено.

5 етап: перевірка допустимості знайденого базисного рішення.

Знайдене базисне рішення відповідно до ознаки 3 допустиме, оскільки не містить негативних компонентів.

6 етап: перевірка оптимальності знайденого базового рішення.

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

7 етап: перевірка альтернативності рішення.

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

Відповідь: оптимальне значенняцільової функції розглянутої задачі =24, яке досягається при.

Приклад 5.2.Вирішити наведене вище завдання лінійного програмування за умови, що цільова функція мінімізується:

Рішення:

I ітерація:

1 етап: формування вихідної симплекс-таблиці.

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

В отриманій системі рівнянь приймемо як дозволені (базисні) змінні х3, х4, х5, х6, тоді вільними змінними будуть х1,х2. Висловимо базисні змінні через вільні.

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

Призначення сервісу. Сервіс призначений для онлайн рішеннязадач лінійного програмування (ЗЛП) симплекс-методом наступних формахзапису:

• у вигляді симплексної таблиці (метод жерданових перетворень); базовій формізаписи;
• модифікованим симплекс-методом; у стовпцевій формі; у рядковій формі.

Інструкція. Виберіть кількість змінних та кількість рядків (кількість обмежень). Отримане рішення зберігається в файлі Wordта Excel.

Кількість змінних 2 3 4 5 6 7 8 9 10
Кількість рядків (кількість обмежень) 1 2 3 4 5 6 7 8 9 10

При цьому обмеження типу x i ≥ 0 не враховуйте. Якщо в завданні для деяких xi відсутні обмеження, то ЗЛП необхідно привести до КЗЛП, або скористатися цим сервісом. При вирішенні автоматично визначається використання М-методу(симплекс-метод зі штучним базисом) та двоетапного симплекс-методу.

Разом із цим калькулятором також використовують такі:
Графічний метод розв'язання ЗЛП
Розв'язання транспортного завдання
Рішення матричної гри
За допомогою сервісу в онлайн режиміможна визначити ціну матричної гри (нижню та верхню межі), перевірити наявність сідлової точки, знайти рішення змішаної стратегії методами: мінімакс, симплекс-метод, графічний (геометричний) метод, методом Брауна.
Екстремум функції двох змінних
Завдання динамічного програмування
Розподілити 5 однорідних партій товару між трьома ринками так, щоб отримати максимальний дохідвід їхнього продажу. Дохід від продажу кожному ринку G(X) залежить кількості реалізованих партій товару Х і представлений у таблиці.

Обсяг товару Х (у партіях)	Прибуток G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Алгоритм симплекс-методувключає наступні етапи:

1. Складання першого опорного плану. Перехід до канонічної формизадачі лінійного програмування шляхом запровадження невід'ємних додаткових балансових змінних.
2. Перевірка плану на оптимальність. Якщо знайдеться хоча б один коефіцієнт індексного рядка менший за нуль, то план не оптимальний, і його необхідно покращити.
3. Визначення провідних стовпця та рядка. З негативних коефіцієнтів індексного рядка вибирається найбільший за абсолютної величини. Потім елементи стовпця вільних членів сімплексної таблиці ділить на елементи того ж знака провідного стовпця.
4. Побудова нового опорного плану. Перехід до нового плану здійснюється внаслідок перерахунку симплексної таблиці методом Жордана-Гаусса.

Якщо потрібно знайти екстремум цільової функції, то мова йдепро пошук мінімального значення(F(x) → min , див. приклад рішення мінімізації функції) та максимального значення((F(x) → max , див. приклад рішення максимізації функції)

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

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

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

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

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

Примітка 2. Нехай у певній крайній точці всі симплексні різниці невід'ємні D k ³ 0 (k = 1..n+m), тобто. отримано оптимальне рішення і існує такий А k - небазисний вектор, у якого D k = 0. Тоді максимум досягається по Крайній міріу двох точках, тобто. має місце альтернативний оптимум. Якщо ввести в базис цю змінну x k , значення цільової функції не зміниться.

Примітка 3. Розв'язання двоїстої задачі знаходиться в останній симплексній таблиці. Останні m компонент вектора симплексних різниць (у стовпцях балансових змінних) – оптимальне рішення двоїстої задачі. Значення цільових функцій прямої та двоїстої задачі в оптимальних точках збігаються.

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

Якщо задана умова «Необхідно, щоб сировина III виду було витрачено повністю», то відповідна умова є рівною.

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

Основний зміст симплексного методу полягає в наступному:

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

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

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

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

Приклад розв'язання задачі симплексним методом

Приклад 26.1

Розв'язати симплексним методом завдання:

Рішення:

Наводимо завдання до канонічного вигляду.

Для цього в ліву частинупершого обмеження-нерівності вводимо додаткову змінну x 6 з коефіцієнтом +1. У цільову функцію змінна x 6 входить із коефіцієнтом нуль (тобто. не входить).

Отримуємо:

Знаходимо початкове опорне рішення. Для цього вільні (невирішені) змінні прирівнюємо до нуля х1 = х2 = х3 = 0.

Отримуємо опорне рішенняХ1 = (0,0,0,24,30,6) з одиничним базисом Б1 = (А4, А5, А6).

Обчислюємо оцінки розкладів векторівумов за базисом опорного рішення за формулою:

Δ k = C б X k - c k

• C б = (з 1, з 2, ..., з m) - вектор коефіцієнтів цільової функції при базисних змінних
• X k = (x 1k , x 2k , ... , x mk) — вектор розкладання відповідного вектора А до базису опорного рішення
• С к - коефіцієнт цільової функції при змінній х до.

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

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

У останньому рядкутаблиці з оцінками k в стовпці "А 0 " записуються значення цільової функції на опорному рішенні Z(X 1).

Початкове опорне рішення не є оптимальним, оскільки в задачі на максимум оцінки 1 = -2, 3 = -9 для векторів А 1 і А 3 негативні.

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

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

Приріст цільової функції знаходиться за формулою: .

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

Отримуємо θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблиця 26.1).

Знаходимо збільшення цільової функції при введенні в базис першого вектора Z 1 = - 6 * (-2) = 12, і третього вектора Z 3 = - 3 * (- 9) = 27.

Отже, для більш швидкого наближення до оптимального рішення необхідно ввести базис опорного рішення вектор А3 замість першого вектора базису А6, оскільки мінімум параметра θ 03 досягається в першому рядку (l = 1).

Проводимо перетворення Жордана з елементом Х13 = 2, отримуємо друге опорне рішення Х2 = (0,0,3,21,42,0) з базисом Б2 = (А3, А4, А5). (Таблиця 26.2)

Це рішення не є оптимальним, тому що вектор А2 має негативну оцінку Δ2 = - 6. Для покращення рішення необхідно ввести вектор А2 в базис опорного рішення.

Визначаємо номер вектора, який виводиться з базису. Для цього обчислюємо параметр 02 для другого стовпця, він дорівнює 7 при l = 2. Отже, з базису виводимо другий вектор базису А4. Здійснюємо перетворення Жордана з елементом х 22 = 3, отримуємо третє опорне рішення Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблиця 26.3).

Це рішення є єдиним оптимальним, так як для всіх векторів, що не входять до базис оцінки позитивні

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Відповідь: max Z(X) = 201 при Х = (0,7,10,0,63).

Метод лінійного програмування в економічному аналізі

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

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

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

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

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

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

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

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

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

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

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

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