Определение начального допустимого решения

В задаче, представленной в стандартной форме, количество переменных обычно больше, чем количество ограничений. Так, в стандартной форме для примера 2.1 имеются три ограничения (m= 3) и пять переменных (k= 5). Для определения начального решения k-m переменных принимаются равными нулю. Тогда в системе из mравенств остается m переменных (неизвестных); в этом случае их значения можно определить однозначно. Эти значения используются в качестве начального решения задачи. Переменные, значения которых принимаются равными нулю, называются небазисными, остальные – базисными. Количество базисных переменных (переменных, составляющих базис), всегда равно количеству ограничений (т).

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

Такой способ определения начального базиса наиболее удобен при решении задач, для которых математическая модель состоит только из ограничений «меньше или равно». В таких задачах после приведения к стандартной форме в каждом ограничении имеется переменная, входящая в данное ограничение с коэффициентом, равным единице, и не входящая ни в одно из других ограничений. Эти переменные - остаточные переменные, введенные при приведении задачи к стандартной форме. Эти переменные принимаются в качестве базисных. Все остальные переменные (т.е. переменные, входившие в исходную математическую модель задачи), принимаются в качестве небазисных, т.е. равных нулю. Таким образом, в качестве начального допустимого решения (начальной угловой точки ОДР) принимается начало координат, т.е. решение, в котором все исходные переменные математической модели равны нулю: х₁=х₂=…=х_n=0.

Если базисные переменные присутствуют не во всех ограничениях задачи, то решение х₁=х₂=…=х_n=0 обычно оказывается недопустимым (не соответствует системе ограничений). В этом случае начало координат не может использоваться в качестве начального допустимого решения (начальной угловой точки ОДР). Для поиска начального допустимого решения в таких случаях используются специальные методы (см. лабораторную работу № 3). Обычно это требуется для задач, в которых имеются ограничения «не меньше» или «равно». Найдем начальное допустимое решение для примера 2.1. Для задачи, приведенной к стандартной форме, в качестве базисных переменных следует выбрать переменные х₃, х₄, х₅, так как каждая из них входит только в одно ограничение с коэффициентом, равным единице, и не входит в другие ограничения.

Базисные переменные имеются во всех ограничениях задачи. Переменные х₁, х₂ принимаются равными нулю, т.е. небазисными. Таким образом, начальное решение задачи следующее: х₁=0,х₂=0, х₃=200, х₄=250, х₅=500.

Это решение является допустимым, так как значения х₁=х₂=0 соответствуют системе ограничений (2.1). Таким образом, в качестве начальной угловой точки ОДР выбрано начало координат.

Выбранное решение явно не является оптимальным, так как целевая функция Е=100х₁+300х₂ при этом равна нулю. По своему смыслу это решение означает, что никакие изделия не выпускаются.

Дата добавления: 2015-07-21