Мета роботи. Метою роботи є вивчення методів побудова математичних моделей з використанням лінійного програмування

Метою роботи є вивчення методів побудова математичних моделей з використанням лінійного програмування.

4.2. Завдання до лабораторної роботи

4.2.1. Вивчення методів лінійного програмування.

4.2.2. Розробити алгоритм вирішення транспортної задачі.

4.2.3. Розробити програму по п. 4.2.2.

4.2.4. Перевірити роботу програми на конкретних даних наданих викладачем.

4.3. Основні теоретичні положення

4.3.1. Ставлення задачи лінійного програмування.

Прикладом задачи лінійного програмування може служити транспортна задача. У пунктах А1,…,Аn знаходяться склади, де храняться товари у кількості Х1,…,Хn. У пунктах В1,…,Вm знаходяться споживачі, яким треба поставити ці товари у кількості Y1,…,Ym відповідно. Будемо роздивляти випадок, коли на складі Ai знаходиться товар Xi. Дij – вартість перевезення одиниці вантажа між пунктами Аi та Вj. Дослідим операцію перевезення товару споживачам у кількостях для того, щоб задовольнити потреби споживачів. Позначимо через хij кількість товару, перевозимого з Аi у Вj. Щоб задовольнити необхідні запити треба, щоб хij задовольняло нерівності:

(4.1)

Але зі складу номер i ми не можемо вивезти продукта більш, ніж там є. Це означає, що шукані величини повинні задовольняти ще одній системі нерівностей:

(4.2)

Задовольнити умовам (4.1) та (4.2) та виконати план перевезеннь, забезпечуючий запити, можна чісленою кількістю способів. Для того, щоб дослідник операцій зміг вибрати визначене рішення, повинно бути сформульоване деяке правило відбору, визначаєме за допомогою критерія, який відображає наше суб’єктивне представлення цілі. При цьому ми отримаємо одну з можливих оцінок обраного рішення. Проблема критерію вирішується незалежно від досліджуваної операції, тобто критерій повинен бути задан оперуючою стороною. Уданій задачі одним з критеріїв буде вартість перевезень, яка визначається:

(4.3)

Задачу о перевезеннях можна слідуючим чином: визначити хij, задовольняюче обмеженням (4.1) та (4.2) та забезпечуюче мінімальне значення функції (4.3). Обмеження (4.2) – умова балансу або закон зберігання, тобто умова фізичного типу. Умова (4.1) називається метою операції. Ці дві умови складають модель операції, Реалізація операції буде залежати від критеріїв. Тобто необхідними посиланнями задачи лінійного програмування є система рівняннь, які називаються обмеженнями, та цільова функція, відображаюча крітерій дослідження.

4.3.2. Опис алгоритму вирішення задач лінійного програмування.

Оскільки у задачах лінійного програмування число змінних більш числа рівнянь (n>m), то маємо нескінчену множину рішень. Іншими словами, маємо множину наборів змінних, х1,х2,х3,…, xn, які в принципі задовольняють усім заданим умовам та кожний такий набір можна вважати рішенням. Так як усі xi є які то фізичні величини, вони не можуть бути <0, отже існують додаткові обмеження: хi>=0…хn>=0.

Частіше за усе у задачах лінійного програмування усі або декілька обмежень мають вид нерівностей, але такі нерівності, легко перетворити у рівняння, вводячи додаткову змінну: Xn+k. Тобто у загальному вигляді система рівнянь буде мати такий вигляд:

(4.4)