Курсовая работа: Економічні задачі лінійного програмування і методи їх вирішення

4. Постановка завдання і формування оптимізаційної моделі.

5. Розрахунок і аналіз результатів оптимізації прибутку.

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

1. ТЕОРЕТИЧНИЙ РОЗДІЛ

1.1 ТЕОРЕТИЧНІ ОСНОВИ лінійного програмування

Лінійне програмування – математична дисципліна, присвячена теорії та методам розв'язання задач про екстремуми лінійних функцій на множинах n‑мірного векторного простору, що задаються системами лінійних рівнянь і нерівностей [13].

Лінійне програмування є окремим випадком математичного програмування. Одночасно воно – основа декількох методів вирішення завдань цілочисельного і нелінійного програмування.

Вперше постановка задачі лінійного програмування у вигляді пропозиції щодо складання оптимального плану перевезень, що дозволяє мінімізувати сумарний пробіг, дана в роботі радянського математика А.Н. Толстого (1930). У 1931 р. угорський математик Б. Егерварі розглянув математичну постановку і вирішив завдання, що має назву «проблема вибору», метод вирішення якої отримав назву угорський метод. У 1939 р. радянський учений Л.В. Канторович вказав загальний метод (метод розв’язувальних множників) вирішення завдань, пов'язаних зі складанням оптимального плану при організації виробничих процесів (у зв'язку з вирішенням задачі оптимального розподілу роботи між верстатами фанерного тресту в Ленінграді). Він же спільно з М.К. Гавуріним в 1949 р. розробив метод потенціалів, який використовується при вирішенні транспортних задач. У наступних роботах Л.В. Канторовича, М.М. Моісеєва, В.С. Немчинова, В.В. Новожилова, А.Л. Лур'є, О.Г. Аганбегяна, Є. Г. Гольдштейна, Д.Б. Юдіна та інших математиків і економістів отримали подальший розвиток як математична теорія лінійного і нелінійного програмування, так і додаток її методів до дослідження різних економічних проблем.

У 1949 р. американським математиком Дж. Данцигом (GB Dantzig) був опублікований симплекс-метод - основний метод рішення задач лінійного програмування. Термін «лінійне програмування» вперше з'явився в 1951 р. в роботах Дж. Данцига і Т. Купманса.

При всьому різноманітті змісту конкретних завдань рішення кожної задачі проходить послідовно наступні основні етапи:

1. Постановка завдання.

2. Побудова (складання) математичної моделі.

3. Вибір методу рішення і рішення задачі.

4. Перевірка отриманого рішення на його адекватність досліджуваного явища і коректування моделі у разі потреби.

5. Реалізація знайденого рішення на практиці.

Зупинимося докладніше на другому етапі.

Математична модель є абстрактним відображенням реального процесу (явища) і в міру своєї абстрактності може його характеризувати більш-менш точно.

У побудові математичної моделі можна виділити наступні моменти:

1. Вибір невідомих величин Х = (х1, ..., хn), впливаючи на які можна змінювати поведінку досліджуваного процесу. Їх називають змінними, керованими параметрами, планом, стратегією.

2. Необхідно виділити мету (максимізація прибутку, мінімізація витрат та інше) функціонування досліджуваного процесу і записати її у вигляді математичної функції від обраних змінних. Така функція називається цільовою (функція мети, критерій оптимальності, критерій якості, показник ефективності) і дозволяє, змінюючи значення керованих параметрів x1, ..., xn, вибрати найкращий варіант з безлічі можливих. Будемо позначати функцію мети Z = f (X).

3. Запис у вигляді математичних співвідношень (рівнянь, нерівностей) умов, що накладаються на змінні. Ці співвідношення називають обмеженнями, вони можуть витікати, наприклад, через обмеженість ресурсів. Сукупність усіх обмежень складає область допустимих рішень (ОДР). Будемо позначати її буквою D (XD) [14].

За таких позначень модель задачі математичного програмування буде мати вид:

Або в розгорнутому виді

знайти план який доставляє екстремальне значення цільової функції Z, тобто

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