Практичне заняття № 6

Тема: Системи лінійних нерівностей і лінійне програмування.

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

Література:

1. Тевяшев А.Д., Литвин О.Г. Вища матемактика. Загальний курс: Збірник задач та вправ. 2-е вид. – Х.: Рубікон, 1999., ст. 196-200.

2. Шипачев В.С. Высшая математика. Учеб. для ВУЗов. – 4-е изд. – М.: Высш. школа, 1998., стр. 179-184.

При виконанні практичної роботи учень повинен

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

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

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

1. Обирається направляючий стовпець j^* з максимальної за абсолютною величиною від’ємною оцінкою (при розв’язанні задачі на максимум), або за максимальною оцінкою (при рішенні задачі за мінімумом) рядка *Big M. На певному етапі розв’язку задачі рядок *Big M повинен зникнути (він існує доти, поки в „Базис” входять штучні змінні), тоді стовпчик вибирається аналогічно по оцінках рядка C(j)-Z(j).

2. Обирається направляючий рядок i* за мінімальною часткою від ділення елементів стовпчика вільних членів B_i на додатні елементи направляючого стовпчика A_ij*. Якщо у направляючому стовпчику немає додатних елементів, то задача не має рішення. На перетині направляючого стовпчика і направляючого рядка знаходиться генеральний елемент A_i*j*.

3. Заповнюється нова симплексна таблиця.

3 .1. Змінна, яка стоїть у направляючому рядку, виводиться із Базису, а змінна, що стоїть у направляючому стовпці, вводиться у Базис, інші змінні залишаються на своїх місцях.

3.2. Заповнюється рядок нової таблиці, який стоїть на місці направляючого. Для цього елементи направляючого рядка діляться на генеральний елемент

.

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

3.4. Інші елементи нової таблиці розраховуються за правилом прямокутника:

3.5. Стовпчик, що відповідає штучній змінній, не розраховується з того моменту, як ця змінна виводиться з „Базису”.

4. Перевіряється умова оптимальності: задача має оптимальне рішення, коли в індексному рядку C(j)-Z(j) не існує від’ємних елементів при рішенні задач на максимум, не існує додатних елементів при рішенні задач на мінімум. Якщо умова оптимальності не виконується, слід перейти до пункту 1.

Загальна постановка транспортної задачі:

Для запису моделі транспортної задачі приймємо такі позначення:

а_і – наявність вантажу у постачальників A₁, A₂, … , A_m (i = 1,2,3,…, m);

b_j– кількість вантажу, необхідне споживачу B₁, B₂, … , B_h (j = 1,2,3,…, h);

Х_ij – кількість вантажу, перевезеного від і–го постачальника до j–го споживача;

C_ij – вартість перевезення одиниці вантажу від і–го постачальника до j–го споживача або відстань між пунктами перевезення.

Задача зводиться до того, щоб відшукати невід’ємні значення Х_іj, при яких цільова функція F(Х) прийме мінімальне значення.

За умовою:

1) (кількість вантажу, призначеного для доставки від i-го постачальника всім споживачам, дорівнює запасу вантажу у цього постачальника).

2) ( кількість вантажу, призначеного для B_j-го споживача, завезеного від будь якого постачальника, дорівнює потребі у вантажу цього пункту призначення).

Рішення транспортної задачі можливо тільки при дотриманості рівності загальних запасів та потреб. Така модель задачі називається закритою.

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

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

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

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

• я кщо це пункт призначення, то потреба його визначається за правилом: Х_ij = a_i - вивезений вантаж з A_i;

• якщо це пункт відправлення, то запаси його визначається за правилом: Х_ij = b_j - завезений вантаж в B_j.

Так заповнюються всі клітини таблиці з Х₁₁ по Х_mh (це заповнення має вигляд східців по діагоналі таблиці).

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

U_i +V_j =C_ij

де: C_ij – оцінка клітинки; i – рядки (i = 1, 2, … , m), j – стовпчики ( j = 1, 2, … , h); U_i - оцінка i-го рядка (i = 1, 2, ... m); V_j – оцінка j-го стовпця (j = 1, 2, ... h).

Тобто, якщо відомий потенціал U_i , то V_j=C_ij – U_i, а якщо відомий V_j, то U_i=C_ij – V_{j .} При цьому один з рядків або один з стовпчиків отримує довільну оцінку, а оцінки останніх рядків і стовпчиків треба розрахувати за вказаними формулами.

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

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

Клітини, які ввійшли до фігури перерахунку позначаються по черзі знаками “+”, “–”,”+”, “–”, ... , починаючи з клітини перерахунку.

Заповнюється нова транспортна таблиця:

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

• для клітин фігури перерахунку: кількість вантажу в клітинках зі знаком “+” збільшується, а в клітинках зі знаком “-“ зменшується на одну і ту ж величину, а саме, на найменшу кількість вантажу у клітинках, позначених знаком “–“.

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