Глава I. Линейное программирование

1.1. Примеры задач линейного программирования.

Пример 1. Пусть малое предприятие «Стакан» продает два вида прохладительных напитков, скажем, «Колокольчик» и «Буратино». Оба напитка изготавливаются тут же на месте из имеющихся запасов газированной воды, фруктового сиропа, лимонной кислоты и льда. Нормы расхода сырья на одну порцию готовой продукции и его запасы приведем для удобства в виде таблицы.

Допустим, что одна проданная порция «Колокольчика» приносит предприятию 5 рублей прибыли, порция «Буратино» - 6 рублей. Также предположим, что нет никаких проблем с изготовлением необходимого количества порций напитков и, что спрос перекрывает предложение.

Возникает вполне естественный вопрос - сколько порций того и другого напитка следует произвести из имеющегося сырья, чтобы получить максимальную прибыль?

Составим математическую модель данной задачи.

Во-первых, введем переменные. Пусть - количество порций «Колокольчика», которое следует произвести, а - количество порций «Буратино».

Во-вторых, введем оптимизируемую целевую функцию, в данном случае прибыль: F .

Тот факт, что следует найти максимум, функции запишем следующим образом:

F (1)

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

(2)

Добавим сюда тривиальные (очевидные) ограничения:

(3)

Условие (1) вместе с ограничениями (2), (3) и дают требуемую математическую модель, которая является частным случаем задачи линейного программирования (см. п. 1.2.).

Как мы увидим позже, модель примера №1 является однородной задачей линейного программирования (см. п. 1.3.).

Дадим обобщение примера №1.

Пример 2. Пусть предприятие выпускает к-типов продукции, используя т-видов ресурсов. При этом расход i-го вида ресурса на единицу j-го вида продукции составляют ; всего имеется объем запаса i-го вида ресурса; реализация единицы продукции j-го вида дает условных денежных единиц прибыли. Требуется составить оптимальный план выпуска продукции.

Модель задачи имеет в этом случае вид:

F

где - объемы планируемого выпуска продукции.

1.2. Постановка задачи линейного программирования. Основные понятия.

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

Определение 2. Зависящая от переменных функция называется линейной, если она имеет вид: где - некоторые фиксированные вещественные коэффициенты.

Пусть

и

.

Тогда

где

- скалярное произведение векторов в n-мерном арифметическом пространстве . Напомним, что n-мерным арифметическим пространством называется множество всех упорядоченных наборов n вещественных чисел ( ) с операциями умножения на числа и сложения, определенными по-координатно:

Элементы пространства ⁿ называются векторами, а само пространство – векторным или линейным.

Определение 3. Ограничения вида:

или

или

называются линейными.

Если положить , то можно записать эти ограничения в векторном виде:

или

или

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

Определение 4. Ограничения вида: или

- называются тривиальными.

Эти ограничения записывают обычно в конце системы ограничений задачи линейного программирования (ЛП). Все остальные ограничения называются нетривиальными.

Таким образом, общая задача ЛП может быть представлена в виде:

(1)

Здесь запись означает, что следует найти экстремум, то есть максимум (max) или минимум (min), функции F.

Определение 5. Оптимизируемая в задаче ЛП функции F называется целевой функцией этой задачи.

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

Обозначение: Для сокращения записи будем далее писать если для всех

В векторном виде задача (1) имеет вид:

(2)

где и - некоторые непересекающиеся подмножества множества индексов

Определение 6. Матрица А= , составленная из коэффициентов системы ограничений, называется матрицей системы ограничений, а столбец - столбцом свободных членов.

Заметим, что матрица А имеет размеры m n , то есть состоит из m строки n столбцов, а вектор состоит из одного столбца. Отметим, что вектор переменных состоит из одной строки (или столбца).

Определение 7. Вектор называется возможным решением задачи ЛП, если он удовлетворяет всем нетривиальным ограничениям.

Определение 8. Вектор называется допустимым решением задачи ЛП, если он удовлетворяет всем ограничениям задачи ЛП, включая тривиальные.

Определение 9. Множество всех допустимых решений образует область допустимых решений (ОДР) задачи ЛП.

Определение 10. Вектор коэффициентов при переменных целевой функции F называется вектором роста целевой функции:

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

Ясно, что

Определение 12. Допустимое решение называется оптимальным, если целевая функция F достигает на своего экстремума (максимума или минимума) в области допустимых решений.

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

по переменной , считая остальные переменные постоянными, то конечно получим :

(3)

Как известно из анализа, градиент функции указывает направление максимального роста функции в данной точке. Из (3) видно, что в линейном случае это направление не зависит от точки и совпадает с направлением вектора .

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

,

где с – некоторая произвольная константа.

1.3. Различные формы задачи ЛП

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

Определение 1. Задача ЛП называется однородной, если все ограничения имеют вид неравенства.

Частными случаями однородной задачи являются задача о ресурсах (или производственная):

(1)

и задача об издержках:

(2)

В первом случае требуется найти максимум функции F («прибыли») при ограниченных «ресурсах» , во втором – минимум издержек F при заданных «нормах потребления» , Более подробно, эти типы задачи ЛП будут рассмотрены в следующих параграфах.

Определение 2. Задача ЛП называется канонической, если все нетривиальные ограничения имеют вид равенства и на все переменные наложены тривиальные ограничения.

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

Таким образом, каноническая задача ЛП может быть записана в виде:

(3)

или в координатной форме:

(4)

Определение 3. Каноническая задача ЛП называется симплексной, если:

1) система линейных ограничений имеет разрешенный вид, то есть матрица системы содержит единичную матрицу ;

2) столбец свободных членов неотрицателен:

3) целевая функция F зависит только от свободных переменных.

Разъясним смысл некоторых терминов, встречающихся в этом определении. Во-первых, напомним, что матрица размера т´т называется единичной (и обозначается Е=Е ), если:

1)

2)

Например, единичными называются матрицы:

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

и называются базисными.

Определение 4. Переменные, соответствующие базисным столбцам, называются также базисными, а остальные переменные – свободными.

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

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

1) перестановка строк;

2) умножение строки на число ;

3) замена одной из строк ее суммой с другой строкой, умноженой на некоторое произвольное число .

Как правило, базисными будем считать последние т столбцов матрицы системы.

Замечание: Далее слова «матрица системы А содержит единичную подматрицу» будут означать, что матрица системы А после перестановки столбцов содержит единичную подматрицу Е размера т т, где т – число строк матрицы А.

Определение 5. Решение системы (4) называется базисным, если все свободные переменные равны нулю.

Определение 6. Допустимое базисное решение называется опорным решением.

Напомним, что вектор называется допустимым решением, если он удовлетворяет как нетривиальным ограничениям, в данном случае системе уравнений (4), так и тривиальным:

Таким образом решение системы (4) оказывается допустимым, если все его компоненты неотрицательны.

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

1.4. Связь между различными типами задачи ЛП.

Покажем, что общая задача ЛП может быть сведена как к однородной задаче ЛП, так и к канонической.

I. Вначале сведём общую задачу к однородной. В соответствии с определением 1 п.1.3 для этого достаточно каждое ограничение вида равенства:

,

заменить на равносильную систему неравенств:

Все ограничения задачи будут иметь вид неравенства и задача станет однородной. При этом число ограничений, конечно же, увеличится.

II. Теперь сведем общую задачу ЛП к канонической. Для этого следует, во-первых, представить каждое неравенство в виде равенства и, во-вторых, добиться того, чтобы все переменные задачи были неотрицательны. Для каждого неравенства системы ограничений вида «меньше»

,

добавим новую (балансовую) переменную , определяемую равенством:

.

Для каждого неравенства системы ограничений вида «больше»

введем переменную , определяемую равенством:

Ясно, что так определенные балансовые переменные неотрицательны. Таким способом все неравенства могут быть заменены на равенства.

Для каждой переменной , на которую не наложено тривиальное ограничение, положим: где и

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

Пример 1. Пусть дана задача ЛП

(1)

Требуется преобразовать исходную общую задачу ЛП к другим формам задачи ЛП.

1. Сведем эту задачу к однородной форме.

Заменяя равенство из (1) на систему неравенств получим соответствующую однородную задачу:

(2)

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

Заменим переменную :

Тогда получим каноническую задачу:

(3)

фактически равносильную исходной.

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

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

Укажем на один частный случай сведения однородной задачи ЛП к симплексной форме. Пусть дана задача о ресурсах, то есть однородная задача ЛП вида:

(4)

причем все

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

(5)

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

1.5. Графический метод решения задачи ЛП.

Рассмотрим графический метод решения однородной двумерной задачи ЛП на конкретном примере.

Пример №1.

Решение. Найдем вначале область допустимых решений (ОДР). Решим графически первое неравенство:

(1)

Для этого построим вначале прямую линию, соответствующую уравнению:

. (1¹)

Поскольку, если то то прямая (1¹) проходит через точку М₁(0;8). Аналогично, если то и прямая (1¹) проходит также через точку М₂ (8;0). Проведем через эти две точки прямую линию и отметим ее с помощью 1 (см. рис. 1). Эта линия делит плоскость на две полуплоскости, которые мы условно назовем верхней и нижней полуплоскостями. Так как координаты точки (0;0) удовлетворяют неравенству (1), то этому неравенству соответствует нижняя полуплоскость, которая содержит эту точку. Этот факт мы изобразим на рис. 1 штрихами, направленными вниз от линии 1 .

Теперь решим графически второе неравенство:

(2)

Ему соответствует прямая, заданная уравнением:

(2¹)

Ее мы построим несколько иначе. Перепишем уравнение (2¹) в виде:

Тогда при оказывается , что дает точку М₃ (0;3) искомой прямой. Угловой коэффициент этой прямой Но угловой коэффициент любой прямой равен где - угол наклона прямой к оси 0х: . Если теперь мы отложим три единицы вправо от точки М₃ (0;3) и затем две единицы вверх, то получим другую точку М₄ (3;5) которая также лежит на прямой (2¹). Через точки М₃ и М₄ мы проводим прямую 2 (рис.1). Начало координат (0;0) удовлетворяет (2) и лежит ниже графика линии 2 , поэтому соответствующая полуплоскость является «нижней», что мы и отмечаем штрихами, направленными вниз от прямой 2 (рис.1). Аналогично строим прямую 3.

Уравнение

(3)

заменяем на уравнение

,

Ясно, что прямая проходит через т. М₅ (5;0), и имеет угловой коэффициент к = 2. При этом самому неравенству

соответствует верхняя полуплоскость, отмеченная штрихами вверх от прямой (3).

Тривиальному неравенству соответствует правая полуплоскость координатной плоскости, то есть полуплоскость, лежащая справа от вертикальной оси Ее отмечаем штрихами, направленными вправо от оси 0 Наконец неравенству соответствует верхняя полуплоскость координатной плоскости, отмеченная штрихами, направленными вверх от оси 0 . Пересечение всех указанных полуплоскостей определяет ОДР данной задачи. На рисунке 1 это область, ограниченная выпуклым пятиугольником ОАВСD.

Изобразим на рисунке 1 вектор роста целевой функции . Это вектор началом в т. (0;0) и концом в точке М (4;3), поскольку .

Построим теперь линию уровня . Она определяется уравнением:

(3)

Мы взяли здесь константу С =11, для того чтобы точки пересечения прямой (3) с осями имели целые координаты. Действительно, если то и, если то что дает две точки М₁ (0;4) и М₂ (3;0) линии уровня (3). Через них проводим пунктиром соответствующую линию уровня (рис. 1). Она оказывается перпендикулярна вектору роста . Отрезок пересекается с ОДР и в каждой его точке х значение целевой функции равно 11:

.

Мы знаем, что значение функции F увеличивается в направлении вектора роста . Чтобы найти максимальное значение на ОДР будем параллельно перемещать линию уровня в направлении вектора роста до тех пор, пока, она будет иметь хотя бы одну точку пересечения с ОДР задачи. Из рисунка 1 ясно, что последнее пересечение смещенной линии уровня (3) будет точка

Рисунок 1. Графическое решение задачи ЛП.

На этой линии очевидно и будет достигаться максимальное значение целевой функции F в ОДР, поскольку при дальнейшем движении линии уровня в направлении вектора роста, она перестает пересекаться с ОДР. Итак, максимальное значение функция F(х) имеет в точке . Так как точка является пересечением прямых 1 и 3, то ее координаты находятся из системы:

(4)

Чтобы решить эту систему, сложим оба уровня. Тогда получим, что или .

Из первого уравнения находим, что

Итак, координаты точки С найдены – С (6;2). Найдем максимальное значение функции:

Задача решена

Ответ: максимальное значение целевой функции F достигается в точке С (6;2) и равно 29:

.

1.6. Выпуклые множества на плоскости и в пространстве.

Определение 1. Множество А Rⁿ называется выпуклым, если с любыми своими двумя точками А оно содержит целиком отрезок их соединяющий:

А А. (1)

Пусть два вектора на плоскости х О у и пусть точка лежит на отрезке . Тогда вектор колинеарен вектору , направлен в одну сторону с ним и не превосходит его по длине. Эти условия могут быть записаны в виде равенства:

, (2)

где

Векторное равенство (2) равносильно системе:

(3)

Система (3) может быть преобразована в равносильную систему:

(4)

где Обозначим Тогда (4) примет вид:

(5)

где

В векторном виде система (5) примет вид:

где (6)

Определение 2. Выпуклой (линейной) комбинацией векторов называется выражение вида:

где все и

Равенство (6) показывает, что каждая точка отрезка является выпуклой комбинацией векторов

Теорема 1. Пересечение любого числа выпуклых множеств является выпуклым множеством.

Доказательство. Пусть - любое семейство выпуклых множеств. Пусть А – их пересечение:

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

для всех А_i.

Но, отсюда, очевидно, следует, что каждая точка отрезка (а значит и сам отрезок) принадлежит пересечению множеств , то есть множеству А. Итак, А – выпуклое множество. Что и требовалось доказать.

Определение 3. Выпуклой оболочкой множества называется такое выпуклое множество , что:

1) ,

2) - выпукло .

Лемма 1. Выпуклая оболочка множества А совпадает с пересечением всех выпуклых множеств, содержащих А.

Доказательство. Пусть В₀ – пересечение всех выпуклых множеств, содержащих А. Тогда очевидно В₀, содержит А. С другой стороны по теореме 1 множество В₀ само выпукло. Отсюда следует, что В₀= VA, поскольку выполнены свойства 1) и 2).

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

Доказательство. Пусть , то есть множество А состоит из двух элементов . Отрезок является выпуклым множеством и содержит А. С другой стороны каждое выпуклое множество В, содержащее А, содержит по определению выпуклости и весь отрезок . Тем самым показано, что ч т.д.

Лемма 3. Если выпуклое множество содержит векторы , то оно содержит и любую их выпуклую комбинацию:

где

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

Пусть где

Пусть

и .

Тогда

и

где По предположению индукции Так как и то . Лемма доказана.

Теорема 2. Выпуклая оболочка VA множества А Rⁿ совпадает с множеством всех выпуклых комбинаций, состоящих из конечного числа векторов множества А.

Доказательство: Пусть В₀ – множество всех таких комбинаций векторов множества А. Как следует из леммы 3 множество В₀ содержится в любом выпуклом множестве В, содержащем А. Осталось показать, что само В₀ – выпукло.

Пусть - два вектора множества В₀. Тогда , , , .

Пусть - где и Достаточно показать, что , то есть что вектор сам является выпуклой комбинацией векторов из А_0. Но это верно, поскольку:

- выпуклая комбинация векторов - так как и ч.т.д.

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

Определение. Выпуклая оболочка точки в - мерном линейном пространстве называется симплексом.

Предполагается, что точки лежат в общем положении, то есть не содержатся ни в какой гиперплоскости.

Рассмотрим некоторую точку Возможны следующие случаи расположения точки относительно множества В.

Первый случай. На каждой прямой l , проходящей через , можно найти отрезок , лежащий целиком в В и содержащий внутри себя:

1)

2) . (7)

Второй случай. Существует содержащая прямая , на которой не существует отрезка , удовлетворяющего (7).

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

Третий случай.

Определение. Пусть точка и ни для одной прямой l содержащей , не существует отрезка , удовлетворяющего (7). В этом случае называется угловой точкой множества В.

Другими словами любой отрезок, содержащий угловую точку внутри себя, обязательно «высовывается» из множества В.

Замечание.

Условие 2) Из (7) можно заменить в предыдущих рассуждениях на условие: , - то есть можно считать, без ограничения общности, что точка является серединой отрезка , действительно, если существует отрезок, содержащий внутри себя, то существует в нем меньший отрезок, для которого точка является серединой.

Определение. Множество называется замкнутым, если оно содержит все свои граничные точки.

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

Теорема 3. Замкнутое выпуклое множество является выпуклой оболочкой своих угловых точек.

1.7. Геометрическая интерпретация однородной задачи линейного программирования.

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

Каждому ограничению вида неравенства:

, (1)

- соответствует замкнутая полуплоскость границей, которой является прямая линия , определяемая соответствующим уравнением:

. (2)

Системе ограничений однородной задачи:

(3)

- соответствует пересечение полуплоскостей Тривиальным ограничениям:

и , (4)

- также соответствуют полуплоскости и

При этом называют, обычно, верхней (координатной) полуплоскостью, а - правой (координатной) полуплоскостью.

Таким образом, ОДР однородной задачи ЛП на плоскости представляет из себя пересечение конечного числа замкнутых полуплоскостей.

Очевидно, каждая полуплоскость является выпуклым множеством. По теореме 1 п. 1.5. их пересечение также выпукло.

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

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

В примере №1 п.1.4. это замкнутый выпуклый пятиугольник ОАВСД.

Целевой функции.

(5)

соответствует вектор роста и линии уровня

(6)

На рисунке 1. п 1.4. это линии (А) и (В).

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

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

В трехмерном пространстве R³ каждому линейному неравенству

(7)

Соответствует одно из замкнутых полупространств, на которые делит все пространство R³ плоскость p_i , определенная уравнением:

(8)

Соответственно вектор роста перпендикулярен каждой поверхности уровня целевой функции, задаваемой уравнением:

, (9)

где С – некая произвольная константа.

Определение 2. Область, которая являеться пересечением конечного числа замкнутых полупространств в R³ называется выпуклой многогранной областью. Ограниченная выпуклая многогранная область называется выпуклым многогранником.

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

Заметим, что при этом поверхность уровня представляет из себя плоскость, определяемую уравнением (9). Вектор роста является вектором нормали этой плоскости.

Соответствующая формулировка в n – мерном пространстве Rⁿ фактически совпадает с данной. Единственное отличие состоит в том, что уравнение поверхности уровня:

(10)

задает не плоскость, а гиперплоскость в Rⁿ.

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

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

Рассмотрим однородную задачу ЛП из примера №1 п. 1.5.:

(1)

Добавив к левым частям системы неравенств соответствующие балансовые переменные преобразуем задачу (1) в каноническую форму:

(2)

Для удобства и единообразия запишем определение целевой функции в виде уравнения:

(3)

Запишем (2) и (3) в виде первой симплекс таблицы:

	- 2						(4)
		- 1
	- 4	- 3				- 1

Первые три строки таблицы (4) содержат по сути расширенную матрицу системы линейных уравнений (2), к которой слева приписан столбец переменной . Последняя строка, называемая индексной, содержит уравнение (3). Буквой , как обычно, обозначен столбец свободных членов. Отметим, что таким образом составленная таблица (4) называется симплексной, поскольку задача (2) имеет симплексную форму. Напомним, что это означает, что во-первых, матрица системы (и таблица (4)) содержат т базисных столбцов (столбцы ), где т - число уравнений (в данном случае ); во-вторых, все элементы столбца свободных членов неотрицательны (это числа 8, 9 и 10), кроме, возможно, элемента индексной строки; в- третьих, целевая функция зависит только от свободных переменных ( и ). Последнее верно, поскольку в базисных столбцах ( ) в индексной строке находятся только нули. Первая симплекс-таблица (4) определяет первое опорное решение. Напомним, что опорное решение является допустимым базисным решением, и, следовательно, свободные переменные и равны нулю: и .

Далее, переменная определяется первой строкой таблицы (4), которая является сокращённой записью первого уравнения системы (2). При оно принимает вид:

Вторая строка таблицы определяет переменную

Третья строка определяет :

Значение целевой функции определяем по индексной строке:

В дальнейшем мы покажем, что оптимальное решение канонической задачи ЛП является опорным, и, следовательно, его следует искать среди опорных решений. Симплекс-таблица (4) и дает одно из таких решений. Как проверить, является ли оно оптимальным? Оказывается, просто. Как мы увидим далее, если коэффициенты целевой функции канонической задачи ЛП неположительные: ,- и функция зависит только от свободных переменных, то соответствующее опорное решение является оптимальным.

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

Мы видим, что в таблице (4) условие неотрицательности всех элементов индексной строки (разумеется, кроме правой части , стоящей в столбце свободных членов) не выполнено. Более того, оба столбца свободных переменных и содержат в индексной строке отрицательные элементы: - 4 и -3, - соответственно.

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

Дата добавления: 2014-10-14; просмотров: 722; Нарушение авторских прав

Мы поможем в написании ваших работ!