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

ЗМІСТ

ВСТУП.. 4

ЛАБОРАТОРНА РОБОТА № 1 РІШЕННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ ГРАФІЧНИМ СПОСОБОМ І СИМПЛЕКС-МЕТОДОМ.. 5

1.1 Теоретичні зведення. 5

1.1.1 Математичне формулювання задачі лінійного програмування. 5

1.1.2 Графічне рішення задачі ЛП.. 5

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

1.1.4 М-метод. 9

1.1.5 Двоетапний симплекс-метод. 10

1.2 Завдання на виконання лабораторної роботи. 11

1.3 Контрольні питання. 25

ЛАБОРАТОРНА РОБОТА № 2 ДВОЇСТИЙ СИМПЛЕКС-МЕТОД І АНАЛІЗ ЧУТЛИВОСТІ 26

2.1 Теоретичні зведення. 26

2.1.1 Двоїстий симплекс-метод. 26

2.1.2 Узагальнений симплекс-метод. 27

2.1.3 Аналіз чутливості 27

2.2 Завдання на виконання лабораторної роботи. 30

2.3 Контрольні питання. 36

ЛАБОРАТОРНА РОБОТА № 3 ТРАНСПОРТНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ 37

3.1 Теоретичні зведення. 37

3.1.1 Транспортні задачі 37

3.1.2 Математична постановка транспортної задачі 37

3.1.3 Методи знаходження опорного плану. 39

3.2 Завдання на виконання лабораторної роботи. 43

3.2.1 Постановка задачі 43

3.2.2 Порядок виконання роботи. 43

3.3 Контрольні питання. 53

ЛАБОРАТОРНА РОБОТА № 4 РІШЕННЯ ЗАДАЧ цілочисельного ПРОГРАМУВАННЯ 54

4.1 Теоретичні зведення. 54

4.1.1 Метод гілок і меж для вирішення задач ДП.. 54

4.2 Завдання на виконання лабораторної роботи. 56

4.3 Контрольні питання. 61

СПИСОК РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ.. 62

ВСТУП

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

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

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

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

ЛАБОРАТОРНА РОБОТА № 1
РІШЕННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ ГРАФІЧНИМ СПОСОБОМ І СИМПЛЕКС-МЕТОДОМ

 

1.1 Теоретичні зведення

1.1.1 Математичне формулювання задачі лінійного програмування

Необхідно визначити максимум (мінімум) лінійної цільової функції:

 

(1.1)

 

При обмеженнях:

 

(1.2)

1.1.2 Графічне рішення задачі ЛП

 

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

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

 

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

 

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

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

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

 

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

1. Всі обмеження перетворюються в рівності з невід'ємної правою частиною.

2. Всі змінні невід'ємні.

2. Нерівності будь-якого типу (зі знаками нерівностей "≥" або "≤") можна перетворити в рівності шляхом додавання в ліву частину нерівностей додаткових змінних.

Для нерівності типу "≤" в ліву частину нерівності вводиться невід'ємна додаткова змінна з коефіцієнтом 1. Для нерівності типу "≤" аналогічно вводиться додаткова змінна з коефіцієнтом -1.

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

Математичне формулювання задачі ЛП у канонічній формі:

Необхідно визначити максимум (мінімум) лінійної цільової функції:

 

При обмеженнях:

(1.3)

 

(1.4)

 

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

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

Симплекс метод працює з так званою симплекс-таблицею. Симплекс-таблиця має наступну структуру:

 

 

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

Перший рядок симплекс таблиці чисто інформативний. У ньому записані заголовки стовпчиків. Другий рядок – це z-рядок. У ньому записані коефіцієнти при змінних в цільової функції.

 

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

1. Завдання лінійного програмування записується в канонічній формі.

2. Визначається початкове допустиме базисне рішення.

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

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

5. Обчислюється нове базисне рішення методом Гауса-Жордана. Перерахунок симплекс-таблиці виконується у 3 етапи:

5.- всі елементи ведучого стовпця приймають значення 0. Ведучий елемент - значення 1;

5.- всі елементи ведучого рядка діляться на ведучій елемент;

5.- всі інші елементи обчислюються за наступною формулою: Модифікований елемент = елемент мінус коефіцієнт у ведучому стовпці помножений на модифікований коефіцієнт у ведучому рядку.

6. Перехід до кроку 3.

6.

1.1.4 М-метод

Розглянутий раніше метод можна використовувати тільки в тому випадку, якщо всі обмеження є нерівностями типу ≤ з невід'ємними правими частинами. У всіх інших випадках крок знаходження початкового допустимого базисного розв'язку не такий простий. Найпростіший спосіб отримання початкового допустимого базисного розв'язку – це використання штучних змінних.

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

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

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

Після узгодження переходимо до 3-го кроку алгоритму звичайного симплекс-методу.

 

1.1.5 Двоетапний симплекс-метод

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

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

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

1.2 Завдання на виконання лабораторної роботи

 

1. Розв’язати задачу лінійного програмування графічним способом.

Таблиця 1.1 Варіанти завдань
№ варіанту	Модель

 

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

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

Потрібно:

1. побудувати математичну модель задачі;

2. привести завдання до канонічної форми;

3. вирішити задачу симплекс-методом;

4. проаналізувати результати рішення;

4.

Варіант 1

Продукція Сировина	А	В	С	Запаси сировини, од.
I			-
II	-
III			-
Прибуток, грош. од.

 

Необхідно, щоб сировину II виду було витрачено повністю.

 

Варіант 3

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I
II		-	-
III		-
Прибуток, грош. од.

 

Необхідно, щоб сировину I виду було витрачено повністю.

 

Варіант 5

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I	-
II			-
III	-
Прибуток, грош. од.

 

Необхідно, щоб сировину II виду було витрачено повністю.

 

Варіант 7

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I			-
II			-
III	-
Прибуток, грош. од.

 

Необхідно, щоб сировину III виду було витрачено повністю.

 

Варіант 9

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I	-
II			-
III			-
Прибуток, грош. од.

 

Необхідно, щоб сировину I виду було витрачено повністю.

 

Варіант 11

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I			-
II			-
III		-
Прибуток, грош. од.

 

Необхідно, щоб сировину III виду було витрачено повністю.

 

Варіант 13

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I			-
II
III	-		-
Прибуток, грош. од.

 

Необхідно, щоб сировину II виду було витрачено повністю.

 

Варіант 15

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I			-
II	-
III	-
Прибуток, грош. од.

 

Необхідно, щоб сировину I виду було витрачено повністю.

 

Варіант 17

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I		-
II		-
III			-
Прибуток, грош. од.

 

Необхідно, щоб сировину III виду було витрачено повністю.

 

Варіант 19

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I		-	-
II
III			-
Прибуток, грош. од.

 

Необхідно, щоб сировину II виду було витрачено повністю.

 

Варіант 21

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I
II	-	-
III		-
Прибуток, грош. од.

Необхідно, щоб сировину I виду було витрачено повністю.

 

Варіант 23

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I	-
II			-
III	-
Прибуток, грош. од.

 

Необхідно, щоб сировину II виду було витрачено повністю.

 

Варіант 25

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I			-
II			-
III		-
Прибуток, грош. од.

Необхідно, щоб сировину III виду було витрачено повністю.

 

Варіант 27

 

Продукція Сировина	А	В	С	Запаси сировини, од.
I			-
II	-
III			-
Прибуток, грош. од.

Необхідно, щоб сировину II виду було витрачено повністю.

 

Варіант 29

Необхідно, щоб сировину III виду було витрачено повністю.   Парні варіанти. Постановка задачі. З двох видів сировини необхідно скласти суміш, до складу якої має входити не менше…

Варіант 2

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А
В
С	-
Ціна 1 кг сировини, грош. од.

 

Варіант 4

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А	-
В
С
Ціна 1 кг сировини, грош. од.

 

 

Варіант 6

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А
В
С		-
Ціна 1 кг сировини, грош. од.

 

 

Варіант 8

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А
В
С		-
Ціна 1 кг сировини, грош. од.

 

 

Варіант 10

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А		-
В
С
Ціна 1 кг сировини, грош. од.

 

 

Варіант 12

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А
В
С	-
Ціна 1 кг сировини, грош. од.

 

 

Варіант 14

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А
В
С	-
Ціна 1 кг сировини, грош. од.

 

 

Варіант 16

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А
В		-
С
Ціна 1 кг сировини, грош. од.

 

 

Варіант 18

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А
В		-
С
Ціна 1 кг сировини, грош. од.

 

 

Варіант 20

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А
В	-
С
Ціна 1 кг сировини, грош. од.

 

 

Варіант 22

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А	-
В
С
Ціна 1 кг сировини, грош. од.

 

 

Варіант 24

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А	-
В
С
Ціна 1 кг сировини, грош. од.

 

 

Варіант 26

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А
В		-
С
Ціна 1 кг сировини, грош. од.

 

 

Варіант 28

 

Речовина	Кількість од. речовини, що міститься в 1 кг сировини кожного виду	Мінімальний вміст речовини, од.
I	II
А	-
В
С
Ціна 1 кг сировини, грош. од.

 

 

Варіант 30

  1.3 Контрольні питання 1. Канонічна форма задачі лінійного програмування?

Метод найменшого елементу

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

Метод Фогеля

Алгоритм виконання методу. 1. У кожному рядку і кожному стовпці транспортної таблиці обчислюється… 2. Серед всіх виявлених різниць Cij обирається максимальна і виділяється відповідний стовпець (рядок).

Ітераційний алгоритм розв'язання транспортної задачі

Знайдене вихідне опорне рішення перевіряється на оптимальність методом потенціалів за наступним критерієм: якщо опорне рішення транспортної задачі є… Числа ui і vj називають потенціалами. В транспортну таблицю додають рядок vj і… Потенціали ui і vj знаходять з рівності uivj = cij, справедливого для зайнятих клітин. Одному з потенціалів дається…

ДО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ

З ДИСЦИПЛІНИ “МАТЕМАТИЧНІ МЕТОДИ
ДОСЛІДЖЕННЯ ОПЕРАЦІЙ”

 

для студентів напряму підготовки 6. 050101 "Комп’ютерні науки"

 

Укладачі: Телятніков Олександр Олегович, доцент

Ченгар Ольга Василівна, асистент