Cтраница 2
Следовательно, поскольку оптимальное решение приводит к вырожденному базису, возможны различные оптимальные решения ( г / j, yz), каждое из которых соответствует одному из оптимальных базисных решений. [16]
Доказанная теорема подводит в какой-то мере итог тем оценкам свойств задачи линейного программирования, которые были даны в § 1.1, 1.2, и позволяет утверждать следующее: если задача (1.2) имеет оптимальное решение, то существует хотя бы одно оптимальное базисное решение. [17]
Эта транспортная задача ( поскольку вектор цен неотрицателен) имеет оптимальное базисное решение. Легко видеть, что в этом оптимальном базисном решении все ненулевые потоки целочисленны. [18]
Метод присоединенных целевых функций позволяет находить решения для некоторой последовательности линейных моделей, каждая из которых характеризуется своим собственным критерием эффективности. Машинная программа последовательно оптимизирует каждый из критериев, используя оптимальное базисное решение исходной задачи в качестве начального пробного решения. [19]
Существуют различные методы определения опорных способов производства. В качестве опорных способов в аппроксимационных моделях используются: 1) базисные или оптимальные базисные решения, определенные в результате решения серии экстремальных задач с неагрегированными переменными, параметрами и способами производства; 2) опорные планы, оцененные экспертным путем; 3) статистически обоснованные и имевшие прецедент плановые решения. [20]
Из приведенных теорем вытекает, что рассматриваемая задача линейного программирования обладает специальной структурой. С помощью подходящего начального распределения ( например, ajl / N) можно найти оптимальное базисное решение, которое соответствует оптимальной стационарной стратегии. [21]
Откуда следует, что теорема о базисе справедлива. Доказательство данной теоремы представляется излишним по той простой причине, что симплексный метод дает рецепт фактического построения оптимального базисного решения. [22]
Пусть каждой дуге поставлено в соответствие число, которое является стоимостью перевозки единицы товара по этой дуге. Если нужно перевезти заданное количество товара из источника в сток с минимальными затратами, то ясно, что весь поток надо пропустить по одной цепи, а именно по цепи минимальной стоимости. Это значит, что задача имеет оптимальное базисное решение, которое вырождено. [23]
Пусть дана некоторая основная задача линейного программирования. Предположим, что эта задача имеет оптимальное решение. Тогда существует по крайней мере одно оптимальное базисное решение. [24]
Пусть дана некоторая основная задача линейного программирования. Предположим, что эта задача имеет оптимальное решение. Тогда существует по крайней мере одно оптимальное базисное решение, которое может быть получено симплекс-процессом из любого базисного решения. [25]
Мы предполагаем, что: а) выражение (26.9) имеет конечный оптимум и б) симплексный алгоритм достигнет оптимальной для этой задачи матрицы через конечное число итераций. Как будет показано в следующем параграфе, предположение а) можно опустить, принимая во внимание теорему двойственности. Однако если а) справедливо, то б) легко вытекает из теории возмущений, которой мы пользуемся в связи с симплексным методом. Теория возмущений, с другой стороны, гарантирует, что каждая итерация даст z ( е), которое будет строго меньше, чем его предшественники. Так как в выражении (26.9) мы имеем дело с оптимальным базисным решением, а точнее, с соответствующим множеством базисных векторов, то мы можем быть уверены, что единственное наименьшее г ( е) будет достигнуто через конечное число итераций. [26]
Выбрав генеральный элемент, перейдем к следующей симплекс-таблице. Из формулы ( 28) видно, что при этом значение формы F уменьшится, так как 7у 0 по условию, а р - 0 в силу невырожденности задачи. Тогда, если решение, достигнутое на некотором этапе этого процесса, еще не является оптимальным, то нет никаких препятствий для продолжения этого процесса. В то же время каждый новый шаг приводит к новому допустимому базисному решению, которое по сравнению с предыдущим доставляет меньшее значение формы. Так как различных допустимых базисных решений - конечное число, то весь процесс не может протекать неограниченно и, следовательно, завершится достижением оптимального базисного решения. [27]