нь. Насамперед, необхідно повністю задовольнити потребу заводу в сировині:. Крім того, очевидно, що, i=1,2, ... n. Нарешті, за змістом задачі величини xi? 0, i=1,2, ... n.
Таким чином, потрібно знайти найменше значення цільової функції (мінімізувати цільову функцію) при дотриманні вищевказаних умов.
При невеликому числі змінних завдання ЛП має простий геометричний зміст. Наприклад, візьмемо для нашої задачі n=3 і конкретизуємо значення вихідних даних:
L=
=
?? 3, 0?? 8, 0?? 5
Враховуючи перша умова, висловимо x3 через x1 і x2 і підставимо в цільову функцію: L=(*) при обмеженнях 0?? 3, 0?? 8, 5?? 10
Обмеження задають на площині якусь многокутну область S. Очевидно, що при кожному значенні L, рівність (*) для цільової функції являє собою пряму на площині. При цьому зміни L відповідає паралельний перенесення прямій. Через одну з вершин багатокутника S пройде якраз та пряма, на якій досягається цікавий для нас мінімум. У нашому випадку це точка з координатами x1=3, x2=7. При цьому x3=0, L=27.
Довільна завдання ЛП може бути сформульована подібно розглянутої в наступному вигляді: наприклад, мінімізувати цільову функцію
L=
, j=1,2, ... n
xi? 0
При m=2 обмеження, як і в прикладі, визначають опуклу многокутну область на площині (або пусте безліч, якщо обмеження несумісні), при m=3 - опуклу багатогранну область в просторі. При цьому рішення задачі, якщо воно існує, досягається на кордоні цієї області, більш точно - в деякій її вершині. У разі довільного m також говорять, що обмеження визначають опуклу багатогранну область в m-мірному координатному просторі. Такі поняття, як «опуклість», «межа області», «вершина», можуть бути визначені і в цьому випадку. Якщо завдання ЛП має рішення, то воно досягається у вершині багатогранної області, певної обмеженнями, зазначеними вище.
На цьому загальному затвердження грунтуються різні методи мінімізації, зокрема, і найбільш відомий з них - симплекс-метод. У згаданому методі проводиться спрямований перебір вершин, такий, що при переході від однієї вершини до наступної значення цільової функції в нашому випадку зменшується. Перебір закінчується, коли буде досягнутий мінімум цільової функції.
.3 Наближені обчислення за допомогою методу найменших квадратів
Висловлені в § 4 Глави 1 міркування про найменшій відстані від вектора до підпростору лежать в основі багатьох різновидів відомого в математиці «методу найменших квадратів».
Даний метод можна проілюструвати на прикладі, що відноситься до серії популярних завдань на суміші і сплави.
Плавильщик розпорядженні три сплавами: латунню, бронзою і мельхіором. Процентний вміст міді, цинку, олова і нікелю в цих сплавах вказано в наступній таблиці:
Метал ЛатуньБронзаМельхіорНовий сплав Мідь 60808070 Цинк 400 010 Олово 020 010 Нікель 002 010
Мета плавильника - отримати новий сплав, в якому перераховані чотири металу становлять відповідно 70, 10, 10, 10 відсотків. Здійсненна чи така мета, а якщо ні, то наскільки близько можна підійти до бажаного складу нового сплаву?
Нехай x1, x2, x...
