Начальное допустимое базисное решение

Cтраница 1

Пространство решений для упражнения 1. [1]

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

Находится начальное допустимое базисное решение. [3]

В этой задаче начальное допустимое базисное решение всегда имеется и легко находится. Дальнейшие вычисления можно проводить двумя путями: сохраняя искусственные переменные до конца ( вводя строку коэффициентов при gz или задавая для конкретных задач достаточно большое реальное gz) или первоначально решив вспомогательную задачу минимизации суммы искусственных переменных. [4]

Рассмотрим стандартные приемы получения начального допустимого базисного решения. [5]

Наиболее общим способом построения начального допустимого базисного решения задачи ЛП является использование искусственных переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются. Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: М - метод5 и двухэтапный метод. [6]

Выше было рассмотрено, как от начального допустимого базисного решения ( опорный план) перейти к оптимальному. Однако симплекс-метод позволяет найти и начальное допустимое решение, причем без необходимости предварительного вычисления ранга, и, в процессе нахождения этого решения, ответить на вопрос о совместности исходной системы ограничений. Достигается это введением искусственных переменных. [7]

В табл. 6.17 приведены исходные данные и начальное допустимое базисное решение, найденное диагональным методом. Требуется найти для этого решения потенциалы пунктов отправления и назначения. [8]

Пусть переменные xs, x6, х7 и хв составляют начальное допустимое базисное решение. Определите, какую из переменных текущего базисного решения следует исключить из базиса так, чтобы все переменные остались неотрицательными. [9]

Оптимальное базисное решение, полученное на первом этапе, используется как начальное допустимое базисное решение исходной задачи. [10]

Таким образом, для решения транспортной задачи распределительным методом необходимо знать некоторое начальное допустимое базисное решение. [11]

В задачах с большим числом уравнений и неизвестных представляет значительные трудности получение начального допустимого базисного решения. [12]

Здесь start - процедура подготовки данных для вычислений ( начальное заполнение массивов, построение начального допустимого базисного решения и др.), new - процедура проверки решения на оптимальность ( optimum решение оптимально) и выработки вводимой в базис переменной при optimum false, work - процедура нахождения выводимой из базиса переменной и изменения записи в соответствии с новым базисом, fin - процедура оформления в нужном виде окончательного решения. [13]

В этой модифицированной задаче переменные Л, R2 и xt можно использовать в качестве начального допустимого базисного решения. В результате получим следующую симплекс-таблицу. [14]

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

Страницы: 1 2