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

Крок 1. Випишемо математичну модель вихідної задачі:

пар взуття – тижневий план випуску моделі №1,

пар взуття – тижневий план випуску моделі №2,

Крок 2. Зведемо математичну модель вихідної задачі до канонічного виду, уводячи додаткові невід’ємні змінні . Помітимо, що кількість додаткових змінних відповідає кількості нерівностей у системі обмежень. Оскільки всі нерівності системи обмежень виражаються знаком «≤», то додаткові змінні в систему обмежень увійдуть з коефіцієнтом «+1». У цільову ж функцію вони ввійдуть з коефіцієнтом «0». Канонічний вид запису даної задачі:

(5)

Крок 3. Побудуємо первинний базис системи обмежень (початковий опорний план задачі).

По-перше, усі вільні елементи системи (5) – невід’ємні. По-друге, основна матриця системи (5)

містить одиничну підматрицю, якій відповідають змінні . Тому ці змінні є базисними, а їхня кількість дорівнює кількості рівнянь системи (5), значить система (5) має первинний базис, який утворено тривимірними одиничними векторами (1; 0; 0), (0; 1; 0), (0; 0; 1), що відповідають базисним змінним . У результаті одержано: кількість основних змінних , базисних ‑ .

Крок 4. Складаємо першу симплексну таблицю.

· Заносимо вихідні дані в таблицю EXEL (див. першу симплексну таблицю на рис. 1.13 і 1.14):

1) у комірки D3:H3 вносимо найменування змінних;

2) у комірки D2:H2 – коефіцієнти цільової функції при відповідних змінних;

3) у комірки D4:H6 – основну матрицю системи (5);

4) у комірки А4:А6 – найменування базисних змінних;

5) у комірки В4:В6 – коефіцієнти цільової функції при базисних змінних;

6) у комірки С4:С6 – стовпець вільних елементів.

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

,

· Заповнюємо комірки С7:Н7:

1) комірка С7 повинна містити значення цільової функції на зазначеному опорному плані:

,

тому вносимо формулу в цю комірку, як показано на рис. 1.14, а на рис. 1.13 бачимо результат обчислення за цією формулою, тобто грн.;

2) комірки D7:H7 повинні містити значення оцінок оптимальності для зазначеного опорного плану:

, ;

тому в комірку D7 вносимо формулу (див. рис. 1.14)

СУММПРОИЗВ($B$4:$B$6;D4:D6)-D2,

у який комірки В4:В6 мають абсолютні значення, з тієї причини, що у формулі для коефіцієнти цільової функції , що містяться в сумі добутків не залежать від . Потім копіюємо формулу з модифікаціями в комірки E7:H7; результати обчислень у цих комірках показані на рис. 1.13.

· Перевірка оптимальності опорного плану. Оцінки оптимальності містять від’ємні значення (див. першу симплексну таблицю на рис. 1.13), тому зазначений опорний план не є оптимальним. Вибираємо серед оцінок оптимальності найбільше за модулем від’ємне значення. У даному випадку це «-70». Стовпець, що відповідає цьому значенню оптимальності, є розв’язувальним стовпцем; виділимо його.

· У комірки I4:I6 вносимо значення оцінних обмежень. Для ^го рядка оцінне обмеження дорівнює , де ‑ вільний елемент цього рядка, а ‑ елемент матриці, що знаходиться в розв’язувальному стовпці ^го рядка (див. рис. 1.14). Якщо =0 або , то оцінне обмеження такого рядка не розглядаємо. Серед додатних оцінних обмежень вибираємо найменше. У даному випадку – це «400» (див. рис. 1.13). Рядок, що відповідає цьому значенню, єрозв’язувальним рядком; виділимо його. Елемент, що стоїть на перетині розв’язувального рядка і розв’язувального стовпця, називається розв’язувальним елементом.

Крок 5. Побудова наступної симплексної таблиці. У загальному випадку, якщо розв’язувальний стовпець має номер , а розв’язувальний рядок ‑ , то подальший алгоритм полягає в наступному.

По-перше, змінну вводимо до базису замість змінної .

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

· елементи розв’язувального рядка ділимо на розв’язувальний елемент і записуємо у відповідному за номером рядку нової таблиці:

, , при ; (*)

· усі інші елементи нової таблиці розраховуємо за формулами:

, при . (**)

Тут ‑ розв’язувальний елемент, він міститься в обох формулах (*) і (**) незалежно від чи , тому йому потрібно привласнити абсолютне значення, тобто після його введення натиснути функціональну клавішу F4. Формула (**) містить для усіх , тому цьому елементу також привласнюється абсолютне значення.

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

· Заповнюємо таблицю EXEL (див. другу симплексну таблицю на рис. 1.13 і 1.14):

1) перші два рядки симплексної таблиці не змінюються;

2) змінну вводимо до базису замість змінної ;

3) у комірках В11:В13 поміщаємо коефіцієнти при базисних змінних;

4) для заповнення комірок С11:Н13 формулами (див. рис. 1.14) відповідно до співвідношень (*) і (**) вносимо спочатку формули у комірки С11:С13 і копіюємо їх з модифікаціями.

Зауважимо, що в комірки С14:Н14 можна внести як формули, аналогічні коміркам С11:Н11 чи С12:Н12 (див. рис. 1.14), так і формули, аналогічні С7:Н7. Результат буде той самий.

· Опорний план, що відповідає другій симплекс-таблиці:

,

а значення цільової функції на ньому грн.

· Аналогічно першій симплексній таблиці в другій симплексній таблиці вибираємо розв’язувальний стовпець, що відповідає найбільшій за модулем від’ємній оцінці оптимальності (див. другу симплексну таблицю рис. 1.13). Потім обчислюємо оцінні обмеження, за якими вибираємо розв’язувальний рядок.

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

,

а значення цільової функції на ньому грн. – максимальним.

Відповідь. Для одержання максимального тижневого прибутку, що складає 34200 грн., фабрика повинна випускати 180 пар взуття моделі №1 і 360 пар взуття моделі №2 за тиждень.

Рис. 1.13‑ Результати розрахунків симплексним методом

Рис.1.14‑ Формули розрахунку симплексного методу в таблицях EXCEL

2. ДВОЇСТА ЗАДАЧА

Дата добавления: 2014-12-08