Выпуклые множества и их свойства. Для того, чтобы изучить свойства ЗЛП, необходимо дать строгое определение выпуклого множества. Ранее выпуклое множество определялось как множество, которое вместе с любыми двумя своими точками содержит отрезок, их соединяющий.

Обобщением понятия отрезка для нескольких точек является их выпуклая линейная комбинация.

Точка Х называетсявыпуклой линейной комбинацией точек , если выполняются условия

Множество точек являетсявыпуклым, если оно вместе с лю­быми своими двумя точками содержит их произвольную выпуклую, линейную комбинацию.

Можно доказать следующую теорему о представлении выпуклого многогран­ника.

Теорема 1.1. Выпуклый п-мерный многогранник является выпук­лой линейной комбинацией своих угловых точек.

Из теоремы 1.1 следует, что выпуклый многогранник порождается своими угловыми точками или вершинами: отрезок – двумя точками, треугольник – тремя, тетраэдр – четырьмя точками и т.д. В то же время выпуклая многогранная область, являясь неограниченным множеством, не определяется однозначно своими угловыми точками: любую ее точку нельзя представить в виде выпуклой линейной комбинации угловых точек.

Свойства задачи линейного программирования. Ранее были рассмотрены различные формы задачи линей­ного программирования и показано, что любая задача линейного программирования может быть представлена в виде общей или канонической задачи.

Для обоснования свойств задачи линейного программирования и методов ее решения целесообразно рассмотреть еще два вида записи канонической задачи.

Матричная форма записи:

Здесь С – матрица-строка, А – матрица системы, Х – матри­ца-столбец переменных, В – матрица-столбец свободных членов:

Векторная форма записи:

где векторы соответствуют столбцам коэффициентов при неизвестных.

Выше была сформулирована, но не доказана в общем виде следующая теорема.

Теорема 1.2. Множество всех допустимых решений системы ог­раничений задачи линейного программирования является выпуклым.

Доказательство: Пусть - два допустимых решения ЗЛП, заданной в матричной форме. Тогда и . Рассмотрим выпуклую линейную комбинацию решений , т.е.

и покажем, что она также является допустимым решением систе­мы (1.3). В самом деле

т.e. решение X удовлетворяет системе (1.3). Но так как , то и Х >0, т.е. решение удовлетворяет условию неотрицательности.

Итак, доказано, что множество всех допустимых решений задачи линейного программирования является выпуклым, а точнее, представляет выпуклый многогранник или выпуклую многогранную область, которые в дальнейшем будем называть одним термином – многогранником решений.

Ответ на вопрос, в какой точке многогранника решений воз­можно оптимальное решение задачи линейного программирова­ния, дается в следующей фундаментальной теореме.

Теорема 1.3. Если задача линейного программирования имеет оп­тимальное решение, то линейная функция принимает максимальное значение в одной из угловых точек многогранника решений. Если ли­нейная функция принимает максимальное значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек.

Доказательство: Будем полагать, что многогранник решений является огра­ниченным. Обозначим его угловые точки через , а оптимальное решение - через X* . Тогда F(X*) ³ F(X) для всех то­чек Х многогранника реше­ний. Если X* – угловая точка, то первая часть тео­ремы доказана.

Предположим, что X* не является угловой точкой, тогда на основании теоре­мы 1.1 X* можно предста­вить как выпуклую линей­ную комбинацию угловых точек многогранника ре­шений, т.е.

Так как F(X) – линейная функция, получаем

В этом разложении среди значений выбе­рем максимальное. Пусть оно соответствует угловой точке X k (1 £ k £ р) ; обозначим его через М, т.е. . Заменим в выражении (1.5) каждое значение этим максимальным значением М. Тогда

По предположению Х * – оптимальное решение, поэтому, с одной стороны, ,но, с другой стороны, доказано, что
F(X*) £ М, следовательно, , где X k – угловая точка. Итак, существует угловая точка X k , в которой линейная функция принимает максимальное значение.

Для доказательства второй части теоремы допустим, что целевая функция принимает максимальное значение более чем в одной угловой точке, например, в точках , где , тогда

Пусть Х – выпуклая линейная комбинация этих угловых точек, т.е.

В этом случае, учитывая, что функция F(X) – линейная, полу­чим

т.е. линейная функция F принимает максимальное значение в произвольной точкеХ , являющейся выпуклой линейной комбинацией угловых точек.

Замечание. Требование ограниченности многогранника решений в теореме является существенным, так как в случае неограниченной многогранной области, как отмечалось в теореме 1.1, не каждую точку такой области можно представить выпуклой линейной комбинацией ее угловых точек.

Доказанная теорема является фундаментальной, так как она указывает принципиальный путь решения задач линейного про­граммирования. Действительно, согласно этой теореме вместо исследования бесконечного множества допустимых решений для нахождения среди них искомого оптимального решения необхо­димо исследовать лишь конечное число угловых точек много­гранника решений.

Следующая теорема посвящена аналитическому методу нахождения угловых точек.

Теорема 1.4. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение.

Доказательство: Пусть – допустимое базисное решение системы ограничений ЗЛП (1.4), в котором первые т компонент - основные переменные, а остальные п - т компо­нент – неосновные переменные, равные нулю в базисном реше­нии (если это не так, то соответствующие переменные можно перенумеровать). Покажем, что Х

Предположим противное, т.е. что Х не является угловой точ­кой. Тогда точку Х можно представить внутренней точкой отрез­ка, соединяющего две различные, не совпадающие с X, точки

другими словами, – выпуклой линейной комбинацией точек многогранника решений, т.е.

где (полагаем, что , ибо в противном случае точка Х совпадает с точкой Х 1 или Х 2).

Запишем векторное равенство (1.6) в координатной форме:

Т.к. все переменные и коэффициенты неотрицательны, то из последних п-т равенств следует, что , т.е. в решениях Х 1 , Х 2 и Х системы уравнений (1.4) значения п - т компонент равны в данном случае нулю. Эти компоненты можно считать значениями неосновных переменных. Но значения неосновных переменных однозначно определяют значения основных, следовательно,

Таким образом, все п компонент в решениях Х 1 , Х 2 и Х совпада­ют, и значит, точки Х 1 и Х 2 сливаются, что противоречит допуще­нию. Следовательно, X – угловая точка многогранника решений.

Докажем обратное утверждение. Пусть – угловая точка многогранника решений и первые ее т координат положительны. Покажем, что Х – допустимое базис­ное решение. не является угловой точкой, что противоречит условию. Следовательно, наше допуще­ние неверно, т.е. векторы линейно независимы и Х – допустимое базисное решение задачи (1.4).

Из теорем 1.3 и 1.4 непосредственно вытекает важное следст­вие: если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допусти­мых базисных решений.

Итак, оптимум линейной функции задачи линейного программиро­вания следует искать среди конечного числа ее допустимых базисных решений.

Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x1, x2, …, xn, удовлетворяющие m условиям - равенствам

и обращающие в максимум линейную функцию этих переменных

Для простоты предположим, что все условия (1) линейно независимы (r=m), и будем вести рассуждения в этом предположении.

Назовём допустимым решением ОЗЛП всякую совокупность неотрицательных значений x1, x2, …, xn, удовлетворяющую условиям (1).Оптимальным назовём то из допустимых решений, которое обращает в максимум функцию (2). Требуется найти оптимальное решение.

Всегда ли эта задача имеет решение? Нет, не всегда.

ЗЛП неразрешима (не имеет оптимального решения):

Из-за несовместности системы ограничений. Т.е. система не имеет ни одного решения, как показано на рисунке 1.

Рисунок 1 - Несовместность системы ограничений

Из-за неограниченности целевой функции на множестве решений. Другими словами при решении ЗЛП на max значение целевой функции стремится к бесконечности, а в случае ЗЛП на min - к минус бесконечности, как показано на рисунке 2.

Рисунок 2 - Неограниченность целевой функции на множестве решений

ЗЛП разрешима:

Множество решений состоит из одной точки. Она же и является оптимальной, как показано на рисунке 3.

Рисунок 3 - Множество решений состоит из одной точки

Единственное оптимальное решение ЗЛП. Прямая, соответствующая целевой функции в предельном положений пересекается с множеством решений в одной точке, как показано на рисунке 4.

Рисунок 4 - Единственное оптимальное решение

Оптимальное решение ЗЛП не единственно. Вектор N перпендикулярен к одной из сторон множества решений. В этом случае оптимальной является любая точка на отрезке АВ, как показано на рисунке 5.

Рисунок 5 - Оптимальное решение не единственно

Решение задач линейного программирования симплекс-методом

Симплекс-метод - алгоритм решения задачи ЛП, реализующий перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции С. Симплекс-метод является основным в линейном программировании.

Использование этого метода в дипломном проекте для решения задачи ЛП обусловлено следующими факторами:

Метод является универсальным, применимым к любой задаче линейного программирования в канонической форме;

Алгоритмический характер метода позволяет успешно программировать и реализовать его с помощью технических средств.

Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если «да», то задача решена. Если «нет», то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции .

Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен, то возможно выбрать неизвестных, которые выражают через остальные неизвестные. Для определенности обычно полагают, что выбраны первые, идущие подряд, неизвестные. Эти неизвестные (переменные) называются базисными, остальные свободными. Количество базисных переменных всегда равно количеству ограничений.

Присваивая определенные значения свободным переменным, и вычисляя значения базисных (выраженных через свободные), получают различные решения системы ограничений. Особый интерес представляют решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Оно соответствует всем ограничениям.

Имея систему ограничений, находят любое базисное решение этой системы. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому допустимому базисному решению.

Симплексный метод гарантирует, что при этом новом решении линейная форма если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным.

Если первое найденное базисное решение окажется недопустимым, то с помощью симплексного метода осуществляется переход к другим базисным решениям, пока на каком-то шаге решения базисное решение окажется допустимым, либо можно сделать вывод о противоречивости системы ограничений.

Таким образом, применение симплексного метода распадается на два этапа:

Нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности;

Нахождение оптимального решения в случае совместности системы ограничений.

Алгоритм перехода к следующему допустимому решению следующий:

В строке коэффициентов целевой функции выбирается наименьшее отрицательное число при отыскании максимума. Порядковый номер коэффициента - . Если такового нет, то исходное базисное решение является оптимальным;

Среди элементов матрицы с номером столбца (этот столбец называется ведущим, или разрешающим) выбираются положительные элементы. Если таковых нет, то целевая функция неограничена на области допустимых значений переменных и задача решений не имеет;

Среди выбранных элементов ведущего столбца матрицы выбирается тот, для которого величина отношения соответствующего свободного члена к этому элементу минимальна. Этот элемент называется ведущим, а строка, в которой он находится - ведущей;

Базисная переменная, отвечающая строке ведущего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу ведущего элемента, вводится в число базисных. Строится новое решение, содержащее новые номера базисных переменных.

Условие оптимальности плана при решении задачи на максимум: среди коэффициентов целевой функции нет отрицательных элементов .

Оптимизация линейных моделей в MS Excel производится симплекс-методом - целенаправленным перебором опорных решений задачи линейного программирования. Алгоритм симплекс-метода сводится к построению выпуклого многогранника в многомерном пространстве, а затем к перебору его вершин с целью поиска экстремального значения целевой функции .

Эффективные средства линейного программирования лежат в основе и целочисленного и нелинейного программирования для решения более сложных задач оптимизации. Эти методы, однако, требуют более длительного времени для вычислений.

В последующих лекциях будут подробно разобраны примеры решения типичных задач оптимизации и принятия управленческих решений с помощью надстройки MS Excel " Поиск решения". Задачи, которые лучше всего решаются данным средством, имеют три основных свойства:

• имеется единственная цель, функционально связанная с другими параметрами системы, которую нужно оптимизировать (найти ее максимум, минимум или определенное числовое значение);
• имеются ограничения, выражающиеся, как правило, в виде неравенств (например, объем используемого сырья не может превышать запасов сырья на складе, или время работы станка за сутки не должно быть больше 24 часов минус время на обслуживание);
• имеется набор входных значений-переменных, влияющих на оптимизируемые величины и на ограничения.

Параметры задач ограничиваются такими предельными показателями:

• количество неизвестных – 200;
• количество формульных ограничений на неизвестные – 100;
• количество предельных условий на неизвестные – 400.

Алгоритм поиска оптимальных решений включает в себя несколько этапов:

• подготовительные работы;
• отладка решения;
• анализ решения .

Последовательность необходимых подготовительных работ , выполняемых при решении задач экономико-математического моделирования с помощью MS Excel , приведена на блок-схеме рисунка 1.6 .

Рис. 1.6.

Из приведенных пяти пунктов плана подготовительных работ только пятый пункт является формализуемым. Остальные работы требуют творчества - и разными людьми они могут быть выполнены по -разному. Кратко поясним сущность формулировок пунктов плана.

При постановке задачи известны целевые коэффициенты и нормированные коэффициенты . В предыдущем примере коэффициентами, формирующими целевую функцию, служили значения нормированной прибыли на одну полку типа () и одну полку типа (). Нормированными коэффициентами служили нормы расхода материала и машинного времени на одну полку каждого типа. Матрица имела следующий вид:

Кроме того, всегда известны значения ресурсов . В предыдущем примере это был недельный запас досок и возможности использовать машинное время: , . Часто в задачах значения переменных требуется ограничить. Поэтому нужно определить нижний и верхний пределы области их изменений.

Таким образом, в диалоговом окне оптимизационной программы " Поиск решения" мы должны задать следующий целевой алгоритм :

Целевая функция равна произведению вектора искомых значений переменных на вектор целевых коэффициентов

Нормированных коэффициентов на вектор искомых значений переменных не должен превышать значения заданного вектора ресурсов

Значения переменной должны находиться в заданных пределах число исходных элементов системы

Число исходных элементов системы

Число заданных видов ресурсов

Отладка решения необходима в случае, когда программа выдает сообщение об отрицательных результатах (рисунок 1.7):

Рис. 1.7.

• если не получено допустимое решение, то выполнить корректировку модели исходных данных;
• если не получено оптимальное решение , то ввести дополнительные ограничения.

Программа выдает оптимальное решение только для модели реальной проблемы, а не решение самой проблемы. При построении модели были сделаны различные упрощающие допущения реальной ситуации. Это позволило формализовать процесс, приближенно отобразив реальные количественные зависимости между параметрами системы и целью. А если реальные параметры будут отличаться от тех, которые заложены в модели, то как изменится решение? Чтобы узнать это, перед принятием управленческого решения проводят анализ решения модели.

Анализ оптимального решения , встроенный в программу, представляет собой заключительный этап математического моделирования экономических процессов. Он позволяет осуществить более глубокую проверку соответствия модели процессу, а также надежности оптимального решения. Он основывается на данных оптимального решения и отчетов, которые выдаются в "Поиске решения". Но он не исключает и не заменяет традиционного анализа плана с экономических позиций перед принятием управленческого решения.

Экономический анализ ставит перед собой следующие цели :

• определение возможных последствий в системе в целом и ее элементах при изменении параметра модели;
• оценка устойчивости оптимального плана к изменению отдельных параметров задачи: если он не устойчив к изменению большинства параметров, снижается гарантия его выполнения и достижения рассчитанного оптимума;
• проведение вариантных расчетов и получение новых вариантов плана без повторного решения задачи от исходного базиса с помощью корректировки.

Возможные методы анализа представлены в схеме на рисунке 1.8 .

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

Учитывая ответственность принятия экономического управленческого решения , руководитель должен убедиться, что полученный оптимальный план является единственно верным. Для этого надо на основе модели получить ответы на следующие вопросы:

• "что будет, если…"
• "что надо, чтобы…"

Анализ с целью ответа на первый вопрос называется вариантным анализом ; анализ с целью ответа на второй вопрос называется решениями по заказу.

Вариантный анализ бывает следующих видов:

• Параметрический - анализ, который заключается в решении задачи при различных значениях некоторого параметра.
• Структурный анализ - когда решение задачи оптимизации ищется при различной структуре ограничений.
• Многокритериальный анализ - это решение задачи по разным целевым функциям.
• Анализ при условных исходных данных - когда исходные данные, используемые при решении задачи, зависят от соблюдения дополнительных условий.

После проведения анализа следует представить результаты в графической форме и составить отчет с рекомендациями о принятии решения с учетом конкретной экономической ситуации.

В настоящие дни в образовательную программу специальностей, связанных с экономикой, финансами и менеджментом, входит дисциплина с названием «Методы оптимальных решений». В рамках данной дисциплины студенты изучают математическую сторону оптимизации, исследования операций, принятия решений и моделирования. Главная особенность данной дисциплины определяется совместным изучением математических методов с их приложением к решению экономических задач.

Задачи на оптимизацию: общие сведения

Если рассматривать общий случай, то смысл задачи на оптимизацию заключается в нахождении так называемого оптимального решения, которое максимизирует (минимизирует) целевую функцию при некоторых условиях-ограничениях.

В зависимости от свойств функций задачи на оптимизацию можно разделить на два вида:

• задача линейного программирования (все функции линейны);
• задача нелинейного программирования (хотя бы одна из функций не является линейной).

Частными случаями задач на оптимизацию являются задачи дробно-линейного, динамического и стохастического программирования.

Наиболее изученными задачами на оптимизацию являются задачи линейного программирования (ЗЛП), решения которых принимают только целочисленные значения.

ЗЛП: формулировка, классификация

Задача линейного программирования в общем случае состоит в нахождении минимума (максимума) линейной функции при некоторых линейных ограничениях.

Общей ЗЛП называют задачу вида

при ограничениях

где — переменные, — заданные действительные числа, — целевая функция, — план задачи, (*)-(***) — ограничения.

Важной особенностью ЗЛП является то, что экстремум целевой функции достигается на границе области допустимых решений.

Практическое экономическое приложение методы оптимальных решений находят при решении задач следующих видов:

• задачи о смесях (т.е. планирование состава продукции);
• задачи оптимального распределения ресурсов в производственном планировании;

ЗЛП: примеры

Задача о смесях

Решение задачи о смесях состоит в отыскании наиболее дешевого набора, состоящего из определенных исходных материалов, которые обеспечивают получение смеси с заданными свойствами.

Задача о распределении ресурсов

Предприятие осуществляет выпуск n различных изделий, для производства которых требуется m различных видов ресурсов. Запасы используемых ресурсов ограничены и составляют соответственно b 1 , b 2 ,…, b m у.е. Кроме того, известны технологические коэффициенты a ij , которые показывают какое количество единиц i -го ресурса необходимо для производства одной единицы изделия j -го вида (). Прибыль, которую получает предприятие при реализации изделия j -го вида, составляет c j ден.ед. Необходимо составить план выпуска продукции, прибыль предприятия при реализации которого будет наибольшей.

Условия задач о смесях и распределении ресурсов часто записываются в виде таблиц.

Ресурсы	Потребности			Запасы
	B 1	…	B n
A 1				b 1
…				…
A m				b m
Прибыль	c 1	…	c n

Задачи о смесях и распределении ресурсов можно решить несколькими способами:

• графический метод (в случае малого числа переменных в математической модели);
• симплекс-метод (в случае числа переменных в математической модели больше двух).

К транспортной задаче относится класс задач, которые имеют определенную специфическую структуру. Простейшей транспортной задачей является задача о перевозках продукта в пункты назначения из пунктов отправления при минимальных затратах на перевозку всех продуктов.

Для наглядности и удобства восприятия условие транспортной задачи принято записывать в таблицу следующего вида:

В общем случае решение транспортной задачи выполняется в несколько этапов:

• I этап: построение первоначального опорного плана;
• II этап: проверка опорного плана на оптимальность;
• III этап: уточнение опорного плана, если он не является оптимальным.

Существует несколько методов получения первоначального опорного плана, например, метод северо-западного угла, метод Фогеля, метод минимальных стоимостей.

Проверка плана на оптимальность выполняется с применением метода потенциалов:

— для занятых клеток,
— для незанятых клеток.

Если план не является оптимальным, то выполняется построение цикла и перераспределение перевозок.

Заключение

В рамках одной статьи нет возможности охватить всю теорию и практику методов оптимальных решений, поэтому рассмотрены только некоторые моменты, позволяющие дать общее представление о данной дисциплине, задачах и методах их решения.

Кроме того, неплохо отметить, что для проверки полученных решений задач оптимизации можно очень эффективно применять надстройку «Поиск решения» пакета MS Excel. Но это уже другая история, собственно, как и подробное рассмотрение методов решения задач на оптимизацию.

Приведем несколько учебников для изучения методов оптимального решения:

1. Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и связь, 1989. – 176 с.
2. Кремер Н.Ш. Исследование операций в экономике: Учеб. пособие для вузов /Н.Ш. Кремер, БА. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. – М.: ЮНИТИ, 2005. – 407 с.

Решение методов оптимизации на заказ

Мы можем помочь вам с решением любых задач по методам оптимальных решений. Заказать решение задач можно у нас на сайте. Достаточно лишь указать срок и прикрепить файл с заданием. вашего заказа можно бесплатно.

Линейным программированием называется раздел математики, в котором изучаются методы нахождения минимума или максимума линейной функции конечного числа переменных, при условии, что переменные удовлетворяют конечному числу ограничений, имеющих вид линейных уравнений или линейных неравенств.

Таким образом, общая задача линейного программирования (ЗЛП) может быть сформулирована следующим образом.

Найти такие значения действительных переменных , для которых целевая функция

принимает минимальное значение на множестве точек, координаты которых удовлетворяют системе ограничений

Как известно, упорядоченная совокупность значений n переменных , , … представляется точкой n-мерного пространства . В дальнейшем эту точку будем обозначать Х =( , , … ).

В матричном виде задачу линейного программирования можно сформулировать так:

, A – матрица размера ,

Точка Х =( , , … ), удовлетворяющая всем условиям, называется допустимой точкой . Множество всех допустимых точек называется допустимой областью .

Оптимальным решением (оптимальным планом) задачи линейного программирования называется решение Х =( , , … ), принадлежащее допустимой области и при котором линейная функция Q принимает оптимальное (максимальное или минимальное) значение.

Теорема . Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

Множество точек называется выпуклым , если оно вместе с любыми своими двумя точками содержит их произвольную выпуклую линейную комбинацию.

Точка Х называется выпуклой линейной комбинацией точек если выполняются условия

Множество всех допустимых решений задачи линейного программирования представляет собой выпуклую многогранную область, которую в дальнейшем будем называть многогранником решений .

Теорема . Если ЗЛП имеет оптимальное решение, то целевая функция принимает максимальное (минимальное) значение в одной из вершин многогранника решений. Если целевая функция принимает максимальное (минимальное) значение более чем в одной точке, то она принимает это значение в любой точке, являющейся выпуклой линейной комбинацией этих точек.

Среди множества решений системы m линейных уравнений, описывающих многогранник решений, выделяют так называемые базисные решения.

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все n-m неосновных переменных равны нулю. В задачах линейного программирования такие решения называют допустимыми базисными решениями (опорными планами).

Теорема . Каждому допустимому базисному решению задачи линейного программирования соответствует вершина многогранника решений, и наоборот, каждой вершине многогранника решений соответствует допустимое базисное решение.

Из приведенных теорем вытекает важное следствие:

Если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений.

Следовательно, оптимум линейной функции цели задачи линейного программирования необходимо искать среди конечного числа ее допустимых базисных решений.