Програмування побудови двоїстої задачі

Лабораторна робота №3


  Тема.   Програмування   побудови   двоїстої   задачі


  Мета:
    1) Розглянути принцип двоїстості в лінійному програмуванні;
    2) Створити програму побудови двоїстої задачі до заданої у вигляді матриці коефіцієнтів системи обмежень та вектора коефіцієнтів цільової функції;
    3) Пояснити економічний зміст двоїстої задачі та взаємозв’язок вихідної і двоїстої задач;
    4) Створити програму побудови двоїстої задачі, що працює у “дружньому інтерфейсі” з користувачем (введення даних та виведення результатів здійснюється у вигляді стрічок системи обмежень та математичного вигляду цільової функції).


  Завдання для самостійної роботи.
            1. Повторити теоретичний матеріал лекції “Принцип двоїстості в ЛП”.
            2. Розглянути приклади побудови двоїстих задач.
            3. Виконати завдання лабораторної роботи. Завдання виділенні курсивом є додатковими та розрахованими на оцінку “відмінно”.
            4. Провести тестування програми (Додаток 2). Виконати завдання свого варіанту.
            5. Зробити висновок, оформити результат виконання.



    Теоретичні відомості


    Дві задачі лінійного програмування називаються взаємно-двоїстими, якщо виконуються такі умови:

  1) Матриці системи обмежень обох задач є транспонованими, одна по відношенні до другої;
  2) Системи обмежень складаються з нерівностей, які спрямовані в обох задачах в протилежні боки;
  3) Коефіцієнти оптимізуючої форми одної задачі є вільними членами другої і навпаки;
  4) Форми в обох задачах оптимізуються в протилежних смислах (одна на min, друга на max).
  Про побудову двоїстої задачі можна говорити лише тоді, коли вихідна записана в канонічній формі.
    Загальні правила побудови двоїстих задач:
    І. Перевіряємо виконання таких вимог:
    1) В усіх обмеженнях вільні члени знаходяться в правій частині рівності чи нерівності, члени з невідомими – в лівій;
    2) Всі обмеження – нерівності вихідної задачі повинні бути записані так, щоб знаки нерівностей були спрямовані в один бік. Якщо це не так, то нерівність слід помножити