16-8. Выбор исходного допустимого решения

Допустим, задача линейного программирования записана в виде

где b≥0; C=||c₁, c₂, ...,c_n||. Исходный базис считается найденным, если ограничения, содержащиеся в задаче (16-40), записаны так

где b_v≥0, так как положив не базисные переменные x_m+k = 0 (k = 1, 2, ..., n - m), получим значения x_v = b_v≥0, которые являются допустимыми и соответствуют одной из вершин.

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

Для каждого ограничения вводим вспомогательную переменную z_i ( i = 1, ..., m). Тогда ограничения системы (16-40) будут выглядеть как

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

т. е. за базис взят вектор z.

На первом шаге минимизируется функция цели при ограничениях (16-41). Непосредственно из этих ограничений следует, что если минимум функции Σz_j является положительной величиной, то система (16-41) не имеет неотрицательных решений, для которых x₁,...,z_m =0, так как в противном случае minΣz_j = 0. Это означает, что исходная система (16-41) не имеет неотрицательных решений. Если minΣz_j =0, т. е. z_j = 0 для всех j, то вектор z является базисным. Отправляясь от этого базиса, мы стремимся прийти к базису, не содержащему ни одной вспомогательной переменной

где b_v≥0. Полагая в системе (16-41) z_j = 0, придем к системе

которая равносильна исходной (16-40). Но здесь x₁, x₂,...,x_m - базисные переменные. Следовательно, задача нахождения базиса решена. Может получиться, что при переходе от базиса z₁, z₂,...,x_m к следующему эти переменные будут оставаться в следующем базисе. Тогда необходимо постепенно их перевести в не базисные.

Если среди неизвестных x₁, x₂,...,x_mимеется такая переменная, например x₁ которая входит только в одно уравнение, например в первое, причем коэффициент при этой переменной a₁₁ имеет тот же знак, что и свободный член b₁ тогда не имеет смысла вводить для первого уравнения искусственную переменную, так как x₁ сразу войдет в базис. Действительно, первое уравнение можно представить в виде

где b₁ = b₁/a₁₁≥0. Если таких неизвестных несколько, то все их можно сразу включить в базис.

Пример 16-4. Дана система

рассмотренная в примере 16-2. Так как x₃, x₅, x₆ входят каждая только в одно ограничение и коэффициенты при них имеют тот же знак, что и соответствующие свободные члены, включаем их сразу в базис. Для оставшегося ограничения вводим искусственную переменную z₁. В итоге получаем:

С помощью симплекс-метода требуется минимизировать форму L₁=z₁=8-(x₁+4x₂-x₄) при ограничениях (16-43). Составляем симплекс-таблицу на первом шаге (табл. 16-6).

Симплекс-таблица

Таблица 16-6

Необходимо минимизировать L. Опорный элемент выбираем на пересечении строки х₃ и столбца x₁ После первого шага получаем базис (x₁, x₅, x₆, z₁). На втором шаге опорный элемент выбирается на пересечении строки z₁ и столбца х⁴, поэтому искусственная переменная z₁ выводится из базиса. При этом L₁ = 0. Таким образом, базис найден и состоит из х¹, х², х⁵, х⁶: