Конспект лекцій (стр. 10 )

Оберемо серед усіх відношень найменше і нехай воно відповідає L-й базисній змінній:

Тоді при зростанні першого обертається в нуль змінна при значенні рівному . Інші базисні змінні будуть при цьому невід’ємні. Коефіцієнт називається розв’язуючим елементом.

Таким чином, щоб визначити максимально допустиме значення вільної змінної , ми повинні знайти розв’язуючий елемент .

Далі вільну змінну і базисну змінну міняємо місцями. Вийде новий вибір базисних змінних

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

Приклад №4. Розглянемо розв’язок задачі із застосуванням симплекс – методу використовуючи умови попереднього 3-го прикладу.

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

Обмеження:

Перетворимо систему обмежень, яка задані у вигляді нерівностей, у систему рівностей, увівши додаткові базисні змінні. Якщо знак обмеження «>», то ставиться «-», якщо «<», то ставиться «+»:

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

(14)

Цільова функція прийме вигляд:

(15)

Представимо вирази (14) і (15) у вигляді таблиці. Значення вільних членів рівнянь і коефіцієнтів при змінних записуємо у верхньому лівому куті відповідної ячійки. Таблиця №1.

	Вільний член рівняння	Х1	Х2
F	0 1200	- 4 -4	- 12 4
X3	600 -180	0,6 0,6	1 0,6
X4	-300 300	- 1 РЕ -1	-1 1
X5	- 100 0	0 0	- 1 0

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

9.3.1. Алгоритм знаходження розв’язуючого елементу:

1. Знаходимо перше від’ємне значення в стовпці для вільних членів, окрім рядка F; у нашому випадку, і в цьому рядку обираємо любий від’ємний елемент. Цим визначається розв’язуючий стовпець.

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

Для цих елементів знаходимо відношення вільних членів рівняння до відповідних коефіцієнтів (елементів) розв’язуючого стовпця, які одинакові за знаком з вільним членом свого рядка, окрім рядка F:

3. Обираємо мінімальне значення отриманих відношень, яке визначає розв’язуючий елемент (РЕ).

4. Позначаємо РЕ подвійним кутком.

У даному випадку розв’язуючим елементом є , тому систему перерозв’язуємо відносно та .

9.3.2. Алгоритм перетворення таблиці шляхом заміни вільних і базисних змінних :

1. Розв’язуючий елемент () виділяється в таблиці (позначен подвійним кутком).

2. Визначається відношення і записується в нижньому правому куті ячійки РЕ (-1).

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

4. Всі елементи розв’язуючого стовпця, окрім РЕ, помножуються на (- λ) і результати записуються у нижньому правому куті відповідних ячійок таблиці.

5. У розв’язуючому рядку усі попередні значення, окрім РЕ, та у розв’язуючому стовпці усі нові, окрім РЕ, позначаються кутком.

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

7. Зводиться нова таблиця (таблиця №2) із заміною на , для чого елементи розв’язуючого рядка і стовпця заміняються числами, що знаходяться у нижніх правих кутках ячійок, які записуються у верхніх лівих кутах ячійок нової таблиці.

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

Таблиця №2

	Вільний член рівняння	Х4	Х2
F	1200 800	- 4 0	-8 -8
X3	420 -40	0,6 0	0,4 0,4
X1	300 -100	- 1 0	1 1
X5	- 100 100	0 0	- 1 -1

9.3.3. Алгоритм визначення оптимального розв’язку ОЗЛП:

1. Якщо усі вільні члени в симплекс-таблиці, окрім рядка F, невід’ємні (додатки), а в ряду F усі коефіцієнти, окрім вільного члена, від’ємні, то оптимальний розв’язок досягнуто.

2. Якщо в рядку F є додатний елемент, а в стовпці немає жодного додатного елементу, то цільова функція не обмежена знизу і оптимального розв’язання не існує.

Розв’язуючи приклад далі послідовно застосовуються розглянуті алгоритми.

Вільний член третього рівня (таблиця №2) від’ємний (-100). У цьому рядку є від’ємний елемент .

В розв’язуючому стовпці із відношень

обираємо найменше .

Таким чином, у якості розв’язуючого елемента приймаємо .

Виконуючи алгоритм 9.3.2, одержуємо нове базисне рішення (таблиця №3).

Таблиця №3

	Вільний член рівняння	Х4	Х5
F	1200 + 800 = 2000	- 4 + 0 = -4	-8
X3	420 – 40 = 380	0,6 + 0 = 0,6	0,4
X1	300 – 100 = 200	-1 + 0 = -1	1
X2	100	0	-1

Аналізуючи дані таблиці №3, можна зробити висновки:

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

2. В результаті розрахунку одержали значення оптимальних потужностей КБ:

3. Капітальні вкладення при цьому складають:

грн.

9.4. Питання для самоконтролю:

1. Формулювання ОЗЛП?

2. Що називається областю допустимих рішень?

3. В якому випадку рішення ОЗЛП може бути не єдиним?

4. Сутність симплекс-методу?

5. Алгоритм знаходження розв’язуючого елементу?

6. Алгоритм перетворення таблиці шляхом заміни вільних і базисних змінних?

7. Алгоритм визначення оптимального розв’язку ОЗЛП?

Лекція №10

Транспортна задача.

10.1. Загальні відомості.

Транспортна задача відноситься до задач лінійного програмування. Вона може бути сформована наступним чином:

Маємо m пунктів виробництва однорідного продукту і n пунктів споживання. Задані обсяги виробництва кожного пункту виробництва і розміри споживання кожного пункту споживання. Відома вартість перевезення одиниці продукту з і-го пункту в j-ий.