Контрольная работа: Завдання лінійного програмування
При x2 =0, x1 =800 (800; 0)
Побудуємо дані прямі (на малюнку вони відповідно позначені (1') і (2')).
Тепер знайдемо на кресленні такі напівплощини, які відповідають нерівностям (1) і (2).
Пряма (1') 3x1 +4x2 =1700 ділить координатну площину на дві напівплощини. Одна напівплощина розташована вище прямої, друга нижче. Щоб знайти ту напівплощину, що відповідає нерівності (1), необхідно взяти будь яку крапку яка належить одній з напівплощин і підставити її координати в нерівність. Якщо нерівність буде вірною, то дана напівплощина є шуканою.
Наприклад, візьмемо крапку з координатами (0; 0) і підставимо її координати в нерівність (1) 3x1 +4x2 <=1700 або 0+0<=1700.
Виходить 0<=1700 - дана нерівність є вірною, отже, нерівності (1) задовольняє напівплощина, що лежить нижче прямої (1').
Аналогічно, надійдемо для нерівності (2) 2x1 +5x2 <=1600. Візьмемо крапку з координатами (0; 0).
Виходить 0<=1600 - дана нерівність вірна. Нерівності (2) задовольняє напівплощина, розташована нижче прямій (2').
Стрілки на кожній границі, з якої сторони прямої виконані обмеження. З огляду на, те що x1 й x2 є ненегативними, одержуємо, що чотирикутник ОАВС є областю, що містить крапки, для яких виконані умови, укладені у фігурні дужки.
Точки, що лежать усередині й на границі цієї області є припустимими рішеннями, але нам потрібні, тільки ті, при яких функція F буде приймати максимальне значення.
Побудова прямої рівня.
Візьмемо довільну крапку, що належить області припустимих рішень - чотирикутнику ОАВС, наприклад, крапку М с координатами (100; 100). Підставимо координати крапки М у функцію F.
F(100; 100)=2*100+4*100=600.
Пряма рівня буде мати такий вигляд: 2x1 +4x2 =600
Побудуємо отриману пряму. Для цього необхідно знайти координати двох довільних крапок цієї прямої. Одна крапка в нас уже є - це крапка М(100; 100). Знайдемо ще одну крапку. Нехай x2 =0, тоді x1 =300. Отже, координати додаткової крапки (300; 0). Відзначимо отримані крапки й побудує пряму рівня (на малюнку 1 вона позначена (3')).
Значення функції F будуть зростати в міру того, як пряма рівня віддаляється від початку координат у позитивному квадранті. Напрямок зростання функції F буде збігатися з вектором, координати якого є коефіцієнтами при змінних x1 й x2 функції F. На малюнку - це вектор a{2; 4}, відкладений від крапки М.
Треба звернути увагу, що вектор a, який визначає напрямок зростання функції F, завжди буде перпендикулярний прямій рівня.
Рис.1.Максимізація цільової функції F.
Для знаходження крапки, у якій функція F досягне свого максимального значення, необхідно переміщати пряму рівня по напрямку вектора a до перетинання цієї прямої із граничною крапкою області припустимих рішень. На нашому малюнку - це крапка В.
Знайдемо координати крапки B.
Дана крапка розташована на перетинанні двох прямих (1') і (2'), тому, щоб знайти її координати необхідно вирішити наступну систему рівнянь:
Із другого рівняння виразимо x1
І підставимо отримане значення в перше рівняння.
(300; 200) - крапка, що відповідає оптимальному рішенню завдання, отже, максимальне значення становить 2*300+4*200=1400 умовних одиниць. Виходить, щоб дістати максимальний прибуток, необхідно випускати в тиждень триста одиниць моделі А и двісті одиниць моделі В.
4. Табличний симплекс-метод