Зміст

 

Вступ

1. Двовимірне завдання лінійного програмування

2. Графічний метод рішення

3. Приклад 1

4. Табличний симплекс-метод

5. Приклад 2

Література

Вступ

Тема контрольної роботи «Завдання лінійного програмування».

Мета виконання роботи: навчитися формалізувати та вирішувати двовимірні завдання лінійного програмування, а саме:

- двовимірне завдання лінійного програмування;

- методи рішення.

Моделі прийняття оптимальних рішень можна класифікувати як завдання мінімізації (максимізації) критерію ефективності, компоненти якого задовольняють системі обмежень (рівностей й/або) нерівностей.

Їх можна розділити на:

-    прийняття рішень в умовах визначеності - вихідні дані - детерміновані;

-    прийняття рішень в умовах невизначеності - вихідні дані - випадкові величини.

А за критерієм ефективності:

-    одноцільове прийняття рішень (один критерій ефективності);

-    багатоцільове прийняття рішень (декілька критеріїв ефективності).

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

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

 

1.  Двовимірне завдання лінійного програмування

Двовимірне завдання лінійного програмування - завдання лінійного програмування, кількість змінних якої дорівнює 2.

Змінні прийнято позначати x1 й x2. Розглянуте раніше завдання лінійного програмування є двовимірним.

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

Визначити значення змінних x1 та x2, при яких лінійна цільова функція F досягає максимуму (мінімуму)

F=з1x1+з2x2 → max (min) (1.1)

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

(1.2)

Серед обмежень можуть одночасно зустрічатися знаки >= , <= й =.

Коефіцієнти aij, bi, cj, i=1..m, j =1,2 будь-які дійсні числа (можливо й 0).

 

2. Графічний метод рішення

Двовимірні завдання лінійного програмування звичайно вирішуються графічно.

Алгоритм рішення задачи двумірного лінійного програмування графічним методом:

1. Будуємо область припустимих рішень функції F.

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

2. ............