Главная | Обратная связь | Поможем написать вашу работу!

Загальна і основна задачі лінійного програмування

У попередньому параграфі були розглянуті приклади задач лінійного програмування. У всіх цих задачах було потрібно знайти максимум або мінімум лінійної функції за умови, що її змінні приймали невід’ємні значення і задовольняли деякій системі лінійних рівнянь або лінійних нерівностей або системі, що містить як лінійні нерівності, так і лінійні рівняння. Кожна із цих задач є частковим випадком загальної задачі лінійного програмування.

Визначення1.1. Загальною задачею лінійного програмування називається задача, що полягає у визначенні максимального (мінімального) значення функції

при умовах

де , , – задані постійні величини і .

Визначення 1.2. Функція (8) називається цільовою функцією (або лінійною формою) задачі (8) - (11), а умови (9) - (11) – обмеженнями даної задачі.

Визначення 1.3. Стандартною (або симетричною) задачею лінійного програмування називається задача, що полягає у визначенні максимального значення функції (8) при виконанні умов (9) і (11), де і .

Визначення 1.4. Канонічною (або основною) задачею лінійного програмування називається задача, що полягає у визначенні максимального значення функції (8) при виконанні умов (10) і (11), де і .

Визначення 1.5. Сукупність чисел Х= (х₁, х₂,... х_п), щозадовольняють обмеженням задачі (9)-(11), називається припустимим розв’язком (або планом).

Визначення 1.6. План Х*= (х₁*, х₂*,..., х_п*),при якому цільова функція задачі (8) приймає своє максимальне (мінімальне) значення, називається оптимальним.

Значення цільової функції (8) при плані X будемо позначати через F (X). Отже, X* – оптимальний план задачі, якщо для будь-якого X виконується нерівність F (X)≤ F (X*)[відповідно F (X)≥ F (X*)].

Зазначені вище три форми задачі лінійного програмування еквівалентні в тому розумінні, що кожна з них за допомогою нескладних перетворень може бути переписана у формі іншої задачі. Це означає, що якщо є спосіб знаходження розв’язок однієї із зазначених задач, то тим самим може бути визначений оптимальний план кожної із трьох задач.

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

У тому випадку, коли потрібно знайти мінімум функції F=c₁x₁ + c₂x₂+... + c_nx_n,можна перейти до знаходження максимуму функції F= –F= –c₁x₁ – c₂x₂–... – c_nx_n,оскільки min F= –max (– F).

Обмеження-нерівність вихідної задачі лінійного програмування, що має вигляд «≤», можна перетворити в обмеження-рівність додаванням до його лівої частини додаткової невід’ємної змінної, а обмеження-нерівність виду «≥» – в обмеження-рівність відніманням від його лівої частини додаткової невід’ємної змінної. Таким чином, обмеження-нерівність

a_i1x₁ + a_i2x₂ +... + a_inx_n ≤ b_i

перетвориться в обмеження-рівність

a_i1x₁ + a_i2x₂ +... + a_inx_n+x_n₊₁=b_i (x_n₊₁ ≥ 0) (12)

а обмеження-нерівність

a_i1x₁ + a_i2x₂ +... + a_inx_n ≥ b_i

– в обмеження-рівність

a_i1x₁ + a_i2x₂ +... + a_inx_n–x_n₊₁=b_i (x_n₊₁ ≥ 0) (13)

У той же час кожне рівняння системи обмежень

a_i1x₁ + a_i2x₂ +... + a_inx_n = b_i

можна записати у вигляді нерівностей:

Число додаткових невід’ємних змінних, що вводяться, при перетворенні обмежень-нерівностей в обмеження-рівності дорівнює числу нерівностей, що перетворюються.

Додаткові змінні, що вводяться, мають цілком певний економічний зміст. Так, якщо в обмеженнях вихідної задачі лінійного програмування відображається витрата і наявність виробничих ресурсів, то числове значення додаткової змінної в плані задачі, записаної у формі основної, дорівнює об’єму відповідного ресурсу, що не використовується.

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

⇐ Предыдущая 123 4 5 6 7 8 9 10 Следующая ⇒