Рассмотрим задачу ЛП в канонической форме (Pk). Множество допустимых точек в задаче является выпуклым многогранником в пространстве . Нетрудно видеть, что экстремуму линейной функции, если он существует, достигается в крайней (угловой) точке выпуклого многогранника.
Точка выпуклого множества называется крайней (угловой), если не существует точек и числа , таких что .
У многогранников крайние точки – вершины. Число вершин многогранника, образованного конечным числом линейных равенств и неравенств, является конечным. Поэтому для решения задачи ЛП достаточно перебрать значения функции во всех угловых точках множества .
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление