Теоретичні відомості
Алгоритм графічного методу розв’язування задач лінійного програмування
1. Побудова багатокутника розв’язків.
Багатокутник розв’язків будується за системою обмежень та умовою невід’ємності змінних.
Визнчення 1. Багатокутником розв’язк5ів називається така фігура, у якій одночасно задовольняються всі обмеження моделі.
Шукана область (простір) розв’язків показана на мал. 2.1. Умови
невід’ємності змінних x1
0, x 2
0 обмежують область їхніх допустимих
значень першим квадрантом. Інші границі простору розв’язків зображені на
площині
x1ox 2
прямими лініями, які побудовані за рівняннями, які отримані
при заміні знака ≤ на знак = в усіх обмеженнях. Області, у яких виконуються відповідні обмеження у виді нерівностей, указуються стрілками, які направлені у сторону допустимих значень змінних. В такий спосіб отримано багатокутник розв’язків – багатокутник АВСDЕF, який на мал. 1 заштрихований.
20
x2
1 2 3 4 x1
Мал. 1. Обмеження x1
2x 2
6 (1),
2x1
x 2 8
(2),
x1 x 2
1 (3),
x 2 2
(4), x1
0 (5), x 2
0 (6).
У кожній точці, що належить внутрішній області або границям багатокутника розв’язків АВСDЕF, всі обмеження виконуються, тому розв’язки, що відповідають цим точкам, є допустимими.
2. Графічне відображення цільової функції.
Цільову функцію графічно можна представити у вигляді вектора -
градієнта та лінії рівня.
Визначення 2. Вектор–градієнт це вектор, який виходить з початку координат та направлений до точки з координатами, що є частинними похідними цільової функції по змінним. Вектор–градієнт показує напрямок зростання значень цільової функції.
Для нашого прикладу вектор–градієнт напрямлений до точки (3,2)
Визначення 3. Лінія рівня – це лінія, координати будь-якої точки якої при підстановці у цільову функцію визначають рівні значення. Лінія рівня завжди перпендикулярна до вектора-градієнта.
21
Багатокутник розв’язків містить нескінченне число таких точок, але,
незважаючи на це, можна знайти оптимальний розв’язок, якщо з'ясувати, у
якому напрямку зростає цільова функція моделі z
3x1
2x 2 . На мал. 3.2
показано, як здійснюється така операція. На графік наносять ряд паралельних ліній, що відповідають рівнянню цільової функції при декількох довільно обраних і послідовно зростаючих значеннях z, що дозволяє визначити нахил цільової функції і напрям, у якому відбувається її збільшення (тобто зростання загального доходу). На мал. 2 використані наступні значення цільової функції:
z = 6 і z = 9.
x 2
Мал. 2. Функція мети: максимізувати z
3x1
х1
2x 2 .
x 3 1 т; x
1 1 т; z
12 2 тис
ум од
Оптимальний розв’язок : 1 3 2 3
. . .
3
3. Визначення точки (або точок), де знаходиться оптимальний розв’язок задачі.
Щоб знайти оптимальний розв’язок, потрібно переміщувати пряму, що характеризує дохід (цільову функцію), у напрямку зростання цільової функції, тобто у напрямку вектора-градієнта, доти, поки вона не зміститься на межу допустимих і недопустимих розв’язків На мал. 3.2 видно, що оптимальному
22
розв’язку відповідає точка С. Тому що точка С є точкою перетинання прямих
(1) і (2) (див. мал. 3.1). Значення
наступної системи двох рівнянь:
x1 і x 2
в цій точці визначаються розв’язком
x1 2x1
2x 2 6,
x 2 8.
Розв’язок зазначеної системи рівнянь дає наступний результат: x1
10 / 3 ,
x 2 4 / 3 . Отриманий розв’язок означає, що добовий обсяг виробництва плитки
„Зн” повинен дорівнювати 10/3 т, а плитки „Вн” – 4/3 т. Дохід, який
одержуватимуть у цьому випадку, складе:
z 3 10
3
2 4 12 2 òèñ.óì .îä .
3 3
Результати, що отримані при розв’язуванні задач графічним методом, виявили цікаву закономірність – оптимальний розв’язок завжди відповідає одній з допустимих кутових (або екстремальних) точок простору розв’язків (на мал. 3.2 це точки А, В, С, D, Е і F). Яка з цих точок виявиться оптимальною, залежить від нахилу прямої, що представляє цільову функцію (тобто від коефіцієнтів цільової функції). Відмітимо, що навіть для випадків, при яких оптимальний розв’язок досягається не в одній точці, всі альтернативні оптимальні розв’язки знаходяться після того, як визначені всі кутові точки
(вершини багатокутника).