Двоїстий симплексний метод заснований на теорії подвійності (див. Рішення двоїстої завдання) і використовується для вирішення завдань лінійного програмування, вільні члени яких bi можуть приймати будь-які значення, а система обмежень задана нерівностями сенсу «≤», «≥» або рівністю «=».
Інструкція для вирішення завдань двоїстим симплекс-методом. Виберіть кількість змінних і кількість рядків (кількість обмежень), натисніть Далі. Отримане рішення зберігається в файлі Word (див. Приклад рішення двоїстим симплекс-методом). При цьому обмеження типу xi ≥ 0 не зважайте.
Разом з цим калькулятором також використовують такі:
Рішення матричної гри
За допомогою сервісу в онлайн режимі можна визначити ціну матричної гри (нижню і верхню межі), перевірити наявність сідлової точки, знайти рішення змішаної стратегії методами: минимакс, симплекс-метод, графічний (геометричний) метод, методом Брауна.
Завдання динамічного програмування
Розподілити 5 однорідних партій товару між трьома ринками так, щоб отримати максимальний дохід від їх продажу. Дохід від продажу на кожному ринку G (X) залежить від кількості реалізованих партій товару Х і представлений в таблиці.
Обсяг товару Х (в партіях)
В P-методі оптимальний план виходить в результаті руху по псевдопланам. Псевдоплан - план, в якому умови оптимальності задовольняються, а серед значень базисних змінних xi є негативні числа. Алгоритм двоїстого симплекс-методу включає наступні етапи:- Складання псевдоплан. Систему обмежень вихідної задачі призводять до системи нерівностей сенсу «# 8804».
- Перевірка плану на оптимальність. Якщо в отриманому опорному плані не виконується умова оптимальності, то завдання вирішується симплексним методом.
- Вибір провідних рядки і стовпці. Серед негативних значень базисних змінних вибираються найбільші за абсолютною величиною. Рядок, що відповідає цьому значенню, є провідною.
- Розрахунок нового опорного плану. Новий план виходить в результаті перерахунку симплексной таблиці методом Жордана-Гаусса. Далі перехід до етапу 2.
Приклад. Підприємству необхідно випустити за планом продукції А1 одиниць, А2 одиниць, А3 одиниць. Кожен вид вироби може проводитися на двох машинах.
Як розподілити роботу машин, щоб загальні витрати часу на виконання плану були мінімальні? Дана матриця витрат і ресурс часу кожної машини. Записати модель досліджуваної операції у формі, що допускає використання P-методу.
Завдання. Вирішити завдання, використовуючи алгоритм двоїстого симплекс-методу.
Наведемо систему обмежень до системи нерівностей сенсу ≤, помноживши відповідні рядки на (-1).
Визначимо мінімальне значення цільової функції F (X) = 4x1 + 2x2 + x3 при наступних умовах-обмежень.
- x1 - x2 ≤-10
2x1 + x2 - x3 ≤8
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної формі).
У першому нерівності сенсу (≤) вводимо базисну змінну x4. У другому нерівності сенсу (≤) вводимо базисну змінну x5.
-1x1 -1x2 + 0x3 + 1x4 + 0x5 = -10
2x1 + 1x2 -1x3 + 0x4 + 1x5 = 8
Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:
Вирішимо систему рівнянь щодо базисних змінних:
x4. x5,
Вважаючи, що вільні змінні дорівнюють нулю, отримаємо перший опорний план:
X1 = (0,0,0, -10,8)
ітерація №1
1. Перевірка критерію оптимальності.
План 0 в симплексній таблиці є псевдопланом, тому визначаємо провідні рядок і стовпець.
2. Визначення нової вільної змінної.
Серед негативних значень базисних змінних вибираємо найбільший по модулю.
Провідною буде перший рядок, а змінну x4 слід вивести з базису.
3. Визначення нової базисної змінної. Мінімальне значення # 952; відповідає 2-му стовпцю, тобто змінну x2 необхідно ввести в базис.
На перетині провідних рядки і стовпці знаходиться дозволяє елемент (РЕ), рівний (-1).
4. Перерахунок симплекс-таблиці. Виконуємо перетворення симплексной таблиці методом Жордана-Гаусса.
Уявімо розрахунок кожного елемента у вигляді таблиці:
ітерація №2
1. Перевірка критерію оптимальності.
План 1 в симплексній таблиці є псевдопланом, тому визначаємо провідні рядок і стовпець.
2. Визначення нової вільної змінної.
Серед негативних значень базисних змінних вибираємо найбільший по модулю.
Провідною буде другий рядок, а змінну x5 слід вивести з базису.
3. Визначення нової базисної змінної. Мінімальне значення # 952; відповідає третьому стовпчику, тобто змінну x3 необхідно ввести в базис.
На перетині провідних рядки і стовпці знаходиться дозволяє елемент (РЕ), рівний (-1).
4. Перерахунок симплекс-таблиці. Виконуємо перетворення.
Або більш докладно:
У базисному стовпці всі елементи позитивні. Переходимо до основного алгоритму симплекс-методу.
ітерація №3
1. Перевірка критерію оптимальності.
Серед значень індексного рядка немає позитивних. Тому ця таблиця визначає оптимальний план завдання.
Оптимальний план можна записати так: x1 = 0, x2 = 10, x3 = 2
F (X) = 2 • 10 + 1 • 2 = 22
Правила введення даних
Поставити свої запитання або залишити побажання або зауваження можна внизу сторінки в розділі Disqus.
Можна також залишити заявку на допомогу у вирішенні своїх завдань у наших перевірених партнерів (тут або тут).