На головну

Взаємно двоїсті задачі лінійного програмування і їх властивості

  1. CLIPS як багатофункціональне середовище програмування (інженерії знань)
  2. I. ЗАВДАННЯ АРТИЛЕРІЇ
  3. I. Мета і завдання дисципліни
  4. II. Основні завдання та їх реалізація
  5. VII. Шматки ТА ЗАВДАННЯ
  6. XI. Пристосування ТА ІНШІ ЕЛЕМЕНТИ, властивості. Здібностей та обдарувань АРТИСТА
  7. А. Умова завдання

Розглянемо формально два завдання I і II лінійного програмування, представлені в табл. 6.1, абстрагуючись від змістовної інтерпретації параметрів, що входять в їх економіці-математичні моделі.

Ці два завдання мають такі властивості:

1. В одному завданню шукають максимум лінійної функції, в іншій - мінімум.

2. Коефіцієнти при змінних в лінійній функції однієї задачі є вільними членами системи обмежень в інший.

3. Кожна із завдань задана в стандартній формі, причому в задачі максимізації все нерівності виду "  ", А в задачі мінімізації все нерівності виду"  ".

4. Матриці коефіцієнтів при змінних в системах обмежень обох завдань є транспоновану один до одного:

для завдання I ,

для завдання II .

5. Число нерівностей в системі обмежень однієї задачі збігається з числом змінних в іншому завданні.

6. Умови невід'ємності змінних є в обох завданнях.

Дві завдання I і II лінійного програмування, що володіють вказаними властивостями, називаються симетричними взаємно подвійними завданнями. Надалі для простоти будемо називати їх просто подвійними завданнями.

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

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

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

3. Знайти матрицю  , Транспоновану до матриці А1.

4. Сформулювати двоїсту задачу на підставі отриманої матриці и умови невід'ємності змінних.

Приклад 6.1.Скласти задачу, двоїсту наступної задачі:

 при обмеженнях

.

Рішення.1. Так як вихідна задача на максимізацію, то наведемо все нерівності системи обмежень до виду "  ", Для чого обидві частини першого і четвертого нерівності помножимо на -1. Отримаємо

2. Складемо розширену матрицю системи

.

3. Знаходимо матрицю  , Транспоновану до А

.

4. Формулюємо двоїсту задачу:

 при обмеженнях

.

 



Попередня   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   Наступна

Геометричний сенс рішень нерівностей, рівнянь і їх систем | ГЛАВА 4. ГЕОМЕТРИЧНИЙ МЕТОД ВИРІШЕННЯ ЗАВДАНЬ лінійного програмування | Геометрична інтерпретація симплексного методу | Відшукання максимуму лінійної функції | Відшукання мінімуму лінійної функції | при обмеженнях | Особливі випадки симплексного методу | II. Проблема виродженого базисного рішення | сімплексні таблиці | Поняття про М-методі (методі штучного базису) |

© um.co.ua - учбові матеріали та реферати