Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Розв’язання задач лінійного програмування симплексним методом
Крок 1. Випишемо математичну модель вихідної задачі: пар взуття – тижневий план випуску моделі №1, пар взуття – тижневий план випуску моделі №2, Крок 2. Зведемо математичну модель вихідної задачі до канонічного виду, уводячи додаткові невід’ємні змінні . Помітимо, що кількість додаткових змінних відповідає кількості нерівностей у системі обмежень. Оскільки всі нерівності системи обмежень виражаються знаком «≤», то додаткові змінні в систему обмежень увійдуть з коефіцієнтом «+1». У цільову ж функцію вони ввійдуть з коефіцієнтом «0». Канонічний вид запису даної задачі: (5) Крок 3. Побудуємо первинний базис системи обмежень (початковий опорний план задачі). По-перше, усі вільні елементи системи (5) – невід’ємні. По-друге, основна матриця системи (5) містить одиничну підматрицю, якій відповідають змінні . Тому ці змінні є базисними, а їхня кількість дорівнює кількості рівнянь системи (5), значить система (5) має первинний базис, який утворено тривимірними одиничними векторами (1; 0; 0), (0; 1; 0), (0; 0; 1), що відповідають базисним змінним . У результаті одержано: кількість основних змінних , базисних . Крок 4. Складаємо першу симплексну таблицю.
,
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.
Крок 5. Побудова наступної симплексної таблиці. У загальному випадку, якщо розв’язувальний стовпець має номер , а розв’язувальний рядок , то подальший алгоритм полягає в наступному. По-перше, змінну вводимо до базису замість змінної . По-друге, робимо перетворення, за яких нова матриця буде мати й стовпець, що містить нулі на всіх місцях, окрім го. Для цього елементи нової симплексної таблиці , виражаємо через елементи , попередньої симплексної таблиці за формулами:
, , при ; (*)
, при . (**) Тут розв’язувальний елемент, він міститься в обох формулах (*) і (**) незалежно від чи , тому йому потрібно привласнити абсолютне значення, тобто після його введення натиснути функціональну клавішу F4. Формула (**) містить для усіх , тому цьому елементу також привласнюється абсолютне значення. Відповідно до зазначеного алгоритму будуємо другу симплексну таблицю.
1) перші два рядки симплексної таблиці не змінюються; 2) змінну вводимо до базису замість змінної; 3) у комірках В11: В13 поміщаємо коефіцієнти при базисних змінних; 4) для заповнення комірок С11: Н13 формулами (див. рис. 1.14) відповідно до співвідношень (*) і (**) вносимо спочатку формули у комірки С11: С13 і копіюємо їх з модифікаціями. Зауважимо, що в комірки С14: Н14 можна внести як формули, аналогічні коміркам С11: Н11 чи С12: Н12 (див. рис. 1.14), так і формули, аналогічні С7: Н7. Результат буде той самий.
, а значення цільової функції на ньому грн.
Ітераційний процес симплексного методу продовжуємо доти, поки оцінки оптимальності () містять від’ємні елементи. У даному випадку вже четверта симплексна таблиця не містить від’ємних оцінок оптимальності, тому опорний план, що відповідає їй, є оптимальним: , а значення цільової функції на ньому грн. – максимальним. Відповідь. Для одержання максимального тижневого прибутку, що складає 34200 грн., фабрика повинна випускати 180 пар взуття моделі №1 і 360 пар взуття моделі №2 за тиждень. Рис. 1.13 Результати розрахунків симплексним методом
|