Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Государственный экономико-технологический университет транспорта

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

T_1-10.doc

Скачиваний:

Добавлен:

20.02.2016

Размер:

4 Мб

Скачать

☆

<<< < Предыдущая 1 2 34 / 134 5 6 7 8 9 10 11 12 13 > Следующая >>>

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

Симплекс-метод застосовується для розв’язання задач, записаних в канонічній формі.

Припустимо, що система виробничих обмежень зведена до одиничного базису і при цьому усі невід’ємні (). Наприклад, при переході від стандартної до канонічної форми запису, якщо усіневід’ємні, ми отримаємо ЗЛП саме в такому вигляді. Базисні розв’язки називають ще опорними планами. Геометрично кожен базисний розв’язок відповідає вершині гіпермногогранника. Тому оптимальний розв’язок ЗЛП необхідно шукати серед базисних розв’язків.

,,,

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

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

Крок 1.

Записуємо вихідну симплекс таблицю.

…

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

Базисний розв’язок:

Крок 2.

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

, (2.4)

з яких видно, що оцінки базисних змінних дорівнюють нулю.

Крок 3.

Перевіряємо отриманий розв’язок на оптимальність:

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

Крок 4.

Знаходимо розв’язувальний елемент.

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

Далі, знаходимо відношення елементів стовпчика В до відповідних додатніх елементів розв’язувального стовпчика. Рядок, для якого це відношення найменше, називають розв’язувальним.

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

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

Крок 5.

Симплекс – перетворення

Елементи розв’язувального рядка ділимо на розв’язувальний елемент

, , (2.5)

а всі інші елементи розраховуємо за формулами прямокутників:

, . (2.6)

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

Після цього повертаємось до кроку 2.

…

….

…

Приклад 2.3. Розв’язати ЗЛП симплекс-методом

Розв’язання. Задача записана в стандартній формі. Зведемо її до канонічної. Для цього додамо до лівих частин кожної нерівності невід’ємні фіктивні змінні і знак «» замінюємо на «=».

Записуємо вихідну симплекс-таблицю.

648

540

Змінні є базисними, а – вільними. Поклавши вільні змінні рівними нулю, отримаємо

Вихідний опорний план -

Перевіряємо отриманий розв’язок на оптимальність.

Значення цільової функції та оцінки розраховуємо за формулами (2.4):

Оцінки базисних змінних .

Серед оцінок вільних змінних є від’ємні. Найменша від’ємна оцінка . Серед елементів 1-го стовпчика, який знаходиться над нею, є додатні, то наш розв’язок не є оптимальним.

						B	C	X
648	540	0	0	0	0	0
1 8 6 0	0 4 8 2	1 0 0 0	0 1 0 0	0 0 1 0	0 0 0 1	5 44 48 8	0 0 0 0		5/1=5 44/8=5,5 48/6=8 -
-648	-540	0	0	0	0	0

Знаходимо розв’язувальний елемент.

Стовпчик буде розв’язувальним, оскільки він знаходиться над найменшою від’ємною оцінкою. Розглянемо відношення елементів стовпчика В до відповідних додатніх елементів розв’язувального стовпчика. Оскільки найменше відношення =5/1=5, то розв’язувальним буде перший рядок. Отже, розв’язувальний елемент - .

Зауваження 2.4. Оскільки елемент не є додатнім, то навпроти нього в останньому стовпчику таблиці ставимо «-».

Проводимо симплекс-перетворення.

Елементи першого рядка ділимо на 1. Стовпчики залишаємо базисними. Інші елементи підраховуємо за формулами прямокутників (2.6).

Елементи 2-го стовпчика ():

Елементи 3-го стовпчика ():

Знаходимо елементи стовпчика

Зауваження 2.5. Можна побачити, що якщо в розв’язувальному рядку стоїть 0, то елементи відповідного стовпчика не змінюються. Дійсно, елементи стовпчика після симплекс-перетворення не змінились. Аналогічно, якщо в розв’язувальному стовпчику стоїть 0, то не змінюються елементи відповідного рядка (в нашому випадку це четвертий рядок).

Записуємо новий опорний план (новий базисний розв’язок): і повертаємось до кроку 2

Елементи оціночного рядка:

Зауваження 2.6. Елементи оціночного рядка можна також підраховувати за формулами прямокутників.

						B	C	X
648	540	0	0	0	0	0
1 0 0 0	0 4 8 2	1 -8 -6 0	0 1 0 0	0 0 1 0	0 0 0 1	5 4 18 8	648 0 0 0		- 4/4=1 18/8=2.25 8/2=4
0	-540	648	0	0	0	3240

Знову отриманий розв’язок не є оптимальним, оскільки є від’ємна оцінка . Розв’язувальним буде стовпчик . Розглянемо відношення елементів стовпчика В до відповідних додатніх елементів розв’язувального стовпчика. Найменше відношення =4/4=1, то розв’язувальним буде другий рядок. Розв’язувальний елемент - .

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

						B	C	X
648	540	0	0	0	0	0
1 0 0 0	0 1 0 0	1 -2 10 4	0 1/4 -2 -2/4	0 0 1 0	0 0 0 1	5 1 10 6	648 540 0 0		5/1=5 - 10/10=1 6/4=1,5
0	0	-432	135	0	0	3780

не є оптимальним. Розв’язувальним стає стовпчик . Розв’язувальний елемент -

						B	C	X
648	540	0	0	0	0	0
1 0 0 0	0 1 0 0	0 0 1 0	2/10 -3/20 -2/10 3/10	-1/10 2/10 1/10 -4/10	0 0 0 1	4 3 1 2	648 540 0 0
0	0	0	48,6	43,2	0	4212

Всі оцінки вільних змінних додатні, тому розв’язок є оптимальним, причому єдиним. Оскільки змінні фіктивні, то ми їх відкидаємо.;, що співпадає з результатом, отриманим графічно (див. приклад 2.1).

Відповідь.

Зауваження 2.7. При розв’язуванні ЗЛП симплекс-методом таблиці зручно записувати одна під одною.

						B	C	X
648	540	0	0	0	0	0
1 8 6 0	0 4 8 2	1 0 0 0	0 1 0 0	0 0 1 0	0 0 0 1	5 44 48 8	0 0 0 0		5/1=5 44/8=5,5 48/6=8 -
-648	-540	0	0	0	0	0
1 0 0 0	0 4 8 2	1 -8 -6 0	0 1 0 0	0 0 1 0	0 0 0 1	5 4 18 8	648 0 0 0		- 4/4=1 18/8=2.25 8/2=4
0	-540	648	0	0	0	3240
1 0 0 0	0 1 0 0	1 -2 10 4	0 1/4 -2 -2/4	0 0 1 0	0 0 0 1	5 1 10 6	648 540 0 0		5/1=5 - 10/10=1 6/4=1,5
0	0	-432	135	0	0	3780
1 0 0 0	0 1 0 0	0 0 1 0	2/10 3/20 -2/10 3/10	-1/10 2/10 1/10 -4/10	0 0 0 1	4 3 1 2	648 540 0 0
0	0	0	135	0	0	3780

Приклад 2.4. Розв’язати ЗЛП симплекс-методом

Розв’язання. Запишемо ЗЛП в канонічній формі.

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