Линейное программирование

линейное программирование

План

1.  Постановка задачи

2.  Графический метод

3.  Анализ чувствительности

4.  Табличный симплекс-метод

1 Постановка задачи

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

Задача ЛП в общем случае может быть сформулирована следующим образом: найти такие значения переменных х1, х2, ..., хn, для которых целевая функция

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

aij, bi, cj (i = 1, 2, ..., m; j = 1, 2, ..., n) – действительные числа.

На простом примере с двумя переменными рассмотрим основные эле­менты модели ЛП.

Компания Reddy Mikks производит электроизоляционный лак для высокого напряжения и низкого напряжения из сырья двух типов: Ml и М2. Следующая таблица представляет основные дан­ные для задачи.

	Расход сырья (в тоннах) на тонну лака	Максимально возможный ежедневный расход сырья
для высоковольтного лака	для низковольтного лака
Сырье М1	6	4	24
Сырье М2	1	2	6
Доход (в тыс. грн.) на тонну лака	5	4

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

Задача (модель) линейного программирования, как и любая задача исследова­ния операций, включает три основных элемента:

1.  Переменные, которые следует определить.

2.  Целевая функция, подлежащая оптимизации.

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

Определение переменных – первый шаг в создании модели. После определения переменных построение ограничений и целевой функции обычно не вызывает труд­ностей.

В нашем примере необходимо определить ежедневные объемы производства электроизоляционного лака для высокого и низкого напряжений. Обозначим эти объемы как переменные модели:

х1 – ежедневный объем производства лака для высокого напряжения;

х2 – ежедневный объем производства лака для низкого напряжения.

Используя эти переменные, далее строим целевую функцию. Логично предпо­ложить, что целевая функция, как суммарный ежедневный доход, должна возрас­тать при увеличении ежедневных объемов производства красок. Обозначим эту функцию через z (она измеряется в тыс. грн.) и положим, что

z = 5х1 + 4х2 .

В соответствии с целями компании получаем задачу:

z = 5х1 + 4х2 Þ max.

Итак, остался не определенным последний элемент модели – условия (огра­ничения), которые должны учитывать ограниченные возможности ежедневного потребления сырья и ограниченность спроса на готовую продукцию. Другими словами, ограничения на сырье можно записать следующим образом

Из таблицы с данными имеем следующее: (1) используемый объем сырья M1 = 6х1 + 4х2 (т); (2) используемый объем сырья М2 = 1х1 + 2х2 (т).

Так как ежедневный расход сырья М1 и М2 ограничен соответственно 24 и 6 тоннами, получаем следующие ограничения.

6х1 + 4х2 £ 24 (сырье Ml);

х1 + 2х2 £ 6 (сырье М2).

Существует еще два ограничения по спросу на готовую продукцию: (1) максималь­ный ежедневный объем производства лака для низкого напряжения не должен превы­шать 2 т и (2) ежедневный объем производства лака для низкого напряжения не должен превышать ежедневный объем производства лака для высокого напряжения более чем на одну тонну. Первое ограничение простое и записывается как х2 £ 2. Второе можно сформулировать так: разность между ежедневными объемами производства лака для низкого и высокого напряжений не должен превышать одной тонны, т. е. х2 – х1 £ 1.

Еще одно неявное ограничение состоит в том, что переменные х1 и х2 должны быть неотрицательными. Таким образом, к сформулированным выше ограничениям необходимо добавить условие неотрицательности переменных: x1 ³ 0, х2 ³ 0.

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

z = 5х1 + 4х2 Þ max

при выполнении ограничений

6х1 + 4х2 £ 24

х1 + 2х2 £ 6

х2 £ 2

х2 – х1 £ 1.

Любое решение, удовлетворяющее ограничениям модели, является допусти­мым. Например, решение х1 = 3 и х2 = 1 будет допустимым, так как не нарушает ни одного ограничения, включая условие неотрицательности. Чтобы удостовериться в этом, подставьте значения х1 = 3 и х2 = 1 в левые части неравенств системы ограничений и убедитесь, что ни одно неравенство не нарушается. Значение целевой функ­ции при этом решении будет равно z = 5´3 + 4´1 = 19 (тыс. грн.).

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

В предыдущем примере целевая функция и все ограничения были линейными. Свой­ство линейности функций предполагает следующее:

1.  Значения левых частей неравенств ограничений и значение целевой функции пря­мо пропорциональны значениям переменных.

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

2 Графический метод

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

Графический способ решения задачи ЛП состоит из двух этапов:

1.  Построение пространства допустимых решений, удовлетворяющих всем ограни­чениям модели.

2.  Нахождение оптимального решения среди всех точек пространства допустимых решений.

Пример. Мы используем модель, построенную для компании Reddy Mikks, чтобы пока­зать оба этапа графического решения задачи ЛП.

Этап 1. Построение пространства допустимых решений

Сначала проведем оси: на горизонтальной будут указываться значения пере­менной х1, а на вертикальной – х2. Далее рассмотрим условие неотрица­тельности переменных: х1 ³ 0 и х2 ³ 0. Эти два ограничения показывают, что про­странство допустимых решений будет лежать в первом квадранте (т. е. выше оси х1 и правее оси х2).

Чтобы учесть оставшиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получим уравнения прямых, а затем на плоскости провести эти прямые. Например, неравенство 6х1 + 4х2 £ 24 заменяется уравнени­ем прямой 6х1 + 4х2 = 24. Чтобы провести эту линию, надо найти две различные точки, лежащие на этой прямой. Можно положить х1 = 0, тогда х2 = 24/4 = 6. Ана­логично для х2 = 0 находим x1 = 24/6 = 4. Итак, прямая проходит через две точки (0, 6) и (4, 0). Эта прямая обозначена на рис. 1 как линия (1).

Теперь рассмотрим, как графически интерпретируются неравенства. Каждое неравенство делит плоскость (х1, х2) на два полупространства, которые располага­ются по обе стороны прямой, которая, соответствует данному неравенству. Точки плоскости, расположенные по одну сторону прямой, удовле­творяют неравенству (допустимое полупространство), а точки, лежащие по дру­гую сторону, – нет. "Тестовой" точкой, проверяющей, точки какого полупро­странства удовлетворяют неравенству, а какого – нет, может служить точка (0, 0). Например, эта точка удовлетворяет первому неравенству 6х1 + 4х2 £ 24 (здесь 6´0 + 4´0 = 0 £ 24). Это означает, что точки полупространства, содержащего начальную точку (0,0), удовлетворяют этому неравенству. На рис. 1 до­пустимые полупространства показаны стрелочками.

В том случае, когда точка (0, 0) не удовлетворяет неравенству, допустимым по­лупространством будет то, которое не содержит эту точку. Если же прямая проходит через эту точку, следует в качестве "тестовой" взять какую-либо другую точку.

Этап 2. Нахождение оптимального решения

Точки пространства допустимых решений, показанного на рис. 1, удовлетво­ряют одновременно всем ограничениям. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках А, В, С, D, E и F. Любая точка, расположенная внутри или на границе области, ограниченной ломаной ABCDEF, является допустимым решением, т. е. удовлетворяет всем ограничениям.

Виды области допустимых решений:

Посколь­ку пространство допустимых решений содержит бесконечное число точек, необ­ходима некая процедура поиска оптимального решения. Нахождение оптимального решения требует определения направления возрас­тания целевой функции z = 5х1 + 4x2 (напомним, что мы максимизируем функцию z). Мы можем приравнять z к нескольким возрастающим значениям, например 10 и 15. Эти значения, подставленные вместо z в выражение целевой функции, поро­ждают уравнения прямых; для значений 10 и 15 получаем уравнения прямых 5х1 + 4х2 = 10 и 5х1 + 4х2 = 15. На рис. 2 эти прямые показаны штриховыми ли­ниями, а направление возрастания целевой функции – стрелкой. Целевая функция может возрастать до тех пор, пока прямые, соответствующие возрастаю­щим значениям этой функции, пересекают область допустимых решений. Точка пересечения области допустимых решений и прямой, соответствующей макси­мально возможному значению целевой функции, и будет точкой оптимума.

На рис. 2 видно, что оптимальное решение соответствует точке С. Эта точка является местом пересечения прямых (1) и (2), поэтому ее координаты х1 и х2 на­ходятся как решение системы уравнений, задающих эти прямые: 6х1 + 4x2= 24

х1 + 2х2 = 6.

Решением этой системы будет х1 = 3 и х2= 1,5, при этом значение целевой функции равно z = 5´3 + 4´1,5 = 21. Полученное решение означает, что для компании Reddy Mikks оптимальным выбором будет ежедневное производство 3 т лака для высокого напряжения и 1,5 т – для низкого напряжения с ежедневным дохо­дом вгрн.

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

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

В случае, когда область допустимых решений является неограниченной, могут встретиться два варианта:

Покажем, как выбираются направления перемещения целевой функции к max и min.

Дополнительные переменные

В обоих примерах этой главы мы использовали неравенства типа "меньше или равно" (знак неравенства £) и "больше или равно" (знак неравенства ³). В этих примерах также предполагалась неотрицательность всех переменных. В данном разделе мы введем два типа дополнительных неотрицательных переменных (назовем их остаточными и избы­точными), которые связаны с неравенствами типа "£" и "³" соответственно. Введем также понятие свободной переменной, которая может принимать как положительные, так и отрицательные значения (и, конечно, значение 0).

Остаточная переменная. Неравенства типа "£" обычно можно интерпретировать как ограничения на использование некоторых ресурсов (представленных в левой части неравенств переменными модели). В такой интерпретации остаточная переменная по­казывает количество неиспользованных ресурсов. В примере с компанией Reddy Mikks неравенство 6х1 + 4x2 £ 24 связано с использованием сырья Ml. Это неравенство эквива­лентно равенству 6х1 + 4х2 + s1 = 24, где s1 ³ 0. Здесь остаточная переменная s1 (= 24 – 6x1 – 4х2) равна неиспользуемому количеству сырья Ml.

Избыточная переменная. Неравенство типа "³" показывает, что "что-то" должно быть не меньше определенной величины. Избыточная переменная определяет превыше­ние значения левой части неравенства над этой величиной. Например, в модели "диеты" неравенство x1 + х2 ³ 800 показывает, что суточное производство пищевой добавки не должно быть меньше 800 фунтов. Математически это неравенство эквивалентно равен­ству х1 + х2 – S1 = 800, где S1 ³ 0. Положительное значение избыточной переменной S1 показывает превышение суточного производства добавки над минимальным значением в 800 фунтов.

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

3 Анализ чувствительности

Модель линейного программирования является как бы “моментальным снимком” реальной ситуации, когда параметры модели (коэффициенты целевой функции и неравенств ограничений) предполагаются неизменными. Естественно изучить влияние изменения параметров модели на полученное оптимальное решение задачи ЛП. Такое исследование называется анализом чувствительности.

В этом разделе анализ чувствительности основывается на графическом решении за­дачи ЛП. Рассмотрим два случая: (1) изменение коэффициентов целевой функции и (2) изменение значений констант в правой части неравенств ограничений. Хотя проведенное здесь исследование будет элементарным и ограниченным, оно покажет основные идеи методов анализа чувствительности.

3.1 Изменение коэффициентов целевой функции

В общем виде целевую функцию задачи ЛП с двумя переменными можно записать следующим образом:

Максимизировать или минимизировать z = с1х1 + с2х2

Изменение значений коэффициентов с1 и с2 приводит к изменению угла наклона пря­мой 2. Графический способ решения задачи ЛП, показывает, что это может привести к изменению оптимального решения: оно будет достигаться в другой угловой точке пространства решений. Вместе с тем, очевидно, существуют ин­тервалы изменения коэффициентов с1 и с2, когда текущее оптимальное решение сохраня­ется. Задача анализа чувствительности и состоит в получении такой информации. В ча­стности, представляет интерес определение интервала оптимальности для отношения с1/с2 (или, что то же самое, для с2/с1); если значение отношения с1/с2 не выходит за пре­делы этого интервала, то оптимальное решение в данной модели сохраняется неизмен­ным. Следующий пример показывает, как можно получить необходимый результат с по­мощью анализа графического представления модели ЛП.

Пример. На рис. 2 видно, что функция z = 5х1 + 4х2 достигает максимального значения в угловой точке С. При изменении коэффици­ентов целевой функции z = с1х1 + с2х2 точка С останется точкой оптимального ре­шения до тех пор, пока угол наклона линии z будет лежать между углами наклона двух прямых, пересечением которых является точка С. Этими прямыми являются 6 х1 + 4 х2= 24 (ограничение на сырье М1) и х1+ 2 х2 = 6 (ограничение на сырье М2). Алгебраически это можно записать следующим образом:

или

В первой системе неравенств условие c1¹0 означает, что прямая, соответствую­щая целевой функции, не может быть горизонтальной. Аналогичное условие в сле­дующей системе неравенств означает, что эта же прямая не может быть вертикаль­ной. Из рис. 3 видно, что интервал оптимальности данной задачи (он определяется двумя прямыми, пересекающимися в точке С) не разрешает целевой функции быть ни горизонтальной, ни вертикальной прямой. Таким образом, мы получили две сис­темы неравенств, определяющих интервал оптимальности в нашем примере. (Когда с1 и с2 могут принимать нулевые значения, интервал оптимальности для отношения с1/с2 (или с2/с1) необходимо разбить на два множества, где знаменатели не обраща­лись бы в нуль.

Итак, если коэффициенты с1 и с2 удовлетворяют приведенным выше неравен­ствам, оптимальное решение будет достигаться в точке С. Отметим, если прямая z = с1х1 + с2х2 совпадет с прямой х1 + 2х2 = 6, то оптимальным решением будет лю­бая точка отрезка СD. Аналогично, если прямая, соответствующая целевой функ­ции, совпадет с прямой 6х1 + 4х2 = 24, тогда любая точка отрезка ВС будет опти­мальным решением. Однако заметим, что в обоих случаях точка С остается точ­кой оптимального решения.

Приведенные выше неравенства можно использовать при определении интервала оптимальности для какого-либо одного коэффициента целевой функции, если пред­положить, что другой коэффициент остается неизменным. Например, если в нашей модели зафиксировано значение коэффициента с2 (пусть с2 = 4), тогда интервал оп­тимальности для коэффициента с1 получаем из неравенств путем подстановки туда значения с2 = 4. После выполнения элементарных арифметических операций получаем неравенства для коэффициента с1 2£с1£6. Аналогично, если зафиксировать значение коэффициента с1 (например, с1 = 5), тогда из неравенств получаем интервал оптимальности для коэффициента с2: 10/3 £ с2 £ 10.

3.2 Стоимость ресурсов

Во многих моделях линейного программирования ограничения трактуются как условия ограниченности ресурсов. В таких ограничениях правая часть неравенств является верхней границей количества доступных ресурсов. В этом разделе мы изучим чувствительность оптимального решения к изменению ограничений, накладываемых на ресурсы. Такой анализ задачи ЛП предлагает простую меру чувствительности решения, называемую стоимостью единицы ресурса; при изменении количества доступных ресурсов (на единицу) значение целевой функции в оптимальном решении изменится на стоимость единицы ресурса. Про­иллюстрируем этот вид анализа задачи ЛП на следующем примере.

Пример. В модели первые два неравенства представляют собой ограничения на использование сырья М1 и М2 соответствен­но. Определим стоимость единиц этих ресурсов.

Начнем с ограничения для сырья М1. Напомним, что в данной задаче опти­мальное решение достигается в угловой точке С, являющейся точкой пересечения прямых, соответствующих ограничениям на сырье М1 и М2 (рис. 4). При изме­нении уровня доступности материала М1 (увеличение или уменьшение текущего уровня, равного 24 т) точка С оптимального решения "плывет" вдоль отрезка DG. Любое изменение уровня доступности материала М1, приводящее к выходу точки пересечения С из этого отрезка, ведет к неосуществимости оптимального решения в точке С. Поэтому можно сказать, что концевые точки D = (2, 2) и G = (6, 0) от­резка DG определяют интервал осуществимости для ресурса М1. Количество сырья М1, соответствующего точке D = (2, 2), равно 6x1 + 4x2= 6´2+ 4´2 = 20 т. Аналогично количество сырья, соответствующего точке G = (6, 0), равно 6´6 + 4´0 = 36 т. Таким образом, интервал осуществимости для ресурса М1 со­ставляет 20 £ М1 £ 36 (здесь через М1 обозначено количество материала М1). Если мы определим М1 как М1= 24 + D1, где D1 – отклонение количества материала М1 от текущего уровня в 24 т, тогда последние неравенства можно переписать как 20£24+D1£36 или –4£D1£12. Это означает, что текущий уровень ресурса М1 может быть уменьшен не более чем на 4т и увеличен не более чем 12 т. В этом случае гарантируется, что оптимальное решение будет достигаться в точке С – точке пересечения прямых, соответствующих ограничениям на ресурсы М1 и М2.

Теперь вычислим стоимость единицы материала М1. При изменении количест­ва сырья М1 от 20 до 36 тонн, значения целевой функции z будут соответствовать положению точки С на отрезке DG. Обозначив через у1 стоимость единицы ресур­са М1, получим следующую формулу:

Если точка С совпадает с точкой D = (2; 2), то z = 5 ´ 2 + 4 ´ 2 = 18 (тыс. грн.), если же точка С совпадает с точкой G = (6; 0), тогда z = 5´6 + 4´0= 30 (тыс. грн.). Отсюда следует, что

Этот результат показывает, что изменение количества ресурса М1 на одну тон­ну (если общее количество этого ресурса не меньше 20 и не больше 36 тонн) при­водит к изменению в оптимальном решении значения целевой функции на 750 грн.

Теперь рассмотрим ресурс М2. На рис. 5 видно, что интервал осуществимо­сти для ресурса М2 определяется концевыми точками В и H отрезка ВН, где В = (4; 0) и H= (8/3;2). Точка H находится на пересечении прямых ED и ВС. Находим, что количество сырья М2, соответствующего точке В, равно x1 + 2x2= 4+ 2´0 = 4 т, а точке Н – 8/3 +2´2 = 20/3 т. Значение целевой функции в точке В равно 5x1 + 4x2 = 5´4 + 4´0 = 20 (тыс. грн.), а в точке Н – 5´8/3+4´2 = 64/3 (тыс. грн.). Отсюда следует, что количество сырья М2 может изменяться от 4 до 20/3 тонн, а стоимость единицы ресурса М2, обозначенная как у2, равна

4. Табличный симплекс-метод

4.1 Канонический вид ЗЛП

Симплекс-метод, как основной алгоритм решения ЗЛП, можно применять в том случае, когда задача задана в специальном каноническом виде.

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

и удовлетворяли бы условиям-равенствам

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

Переход от любых условий-неравенств к условиям-равенствам осуществляется введением новых дополнительных переменных.

Пример.

Знак «≤» заменяется дополнительной переменной со знаком «+», а знак «≥» – со знаком «–». Количество дополнительных переменных равно количеству ограничений-неравенств, т. е. нам необходимо ввести х4 и х5.

Перед нами поставлена новая задача: найти неотрицательные значения переменных х1, х2, х3, х4, х5 такие, чтобы они удовлетворяли условиям-равенствам и обращали бы в максимум линейную функцию этих переменных

4.2 Идея симплекс-метода

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

Для подготовки исходных данных необходимо выполнить следующие процедуры:

а) привести математическую модель задачи к каноническому виду;

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

в) ввести в исходную симплекс-таблицу следующие параметры, соответствующие начальному базисному решению:

– весовые коэффициенты при переменных хj в целевой функции (строка С);

– переменные, которые входят в текущий базис (столбец Вx);

– базисные переменные (столбец A0));

– элементы || хij ||, i = 1, ... , m,, j = 1, ... , n матрицы условий задачи Am´n (столбцы А1, ..., Аn);

– оценки Dj j = 1, ...,n, соответствующие векторам A1, A2, ..., An,(последняя индексная строка).

Оценки Dj определяются по формуле

. (4.4)

Весовые коэффициенты сj при базисных переменных проставляются слева от таблицы.

Значения целевой функции при текущем базисе заноситься в последнюю строку столбца А0.

Пример. Найти максимум функции

Приведем заданную модель к каноническому виду, введя свободные переменные x3 и x4, превращающие неравенства (4.7) в равенства:

A1 A2 A3 A4 A0

Система ограничений имеет следующую особенность: существуют такие переменные, которые входят только в одно уравнение и имеют коэффициент равный единице. Это х3 и х4. Переменные х1и х2 приравниваем к нулю, тогда х3=2 и х4=6. Тогда начальное допустимое базисное решение будет иметь вид Х=(0; 0; 2; 6).

Таблица 1.1

	C	0	3	2	0	0
	Bx	A0	A1	A2	A3	A4
c3=0	x3	2	1	–1	1	0
c4=0	x4	6	2	1	0	1
	D	0	–3	–2	0	0
			­

Элементы строчки D рассчитываем по формуле (4.4):

Значение функции для данного начального базиса будет равно нулю:

Если Dj ³ 0 для всех j = 1, ..., п, то данный план является оптимальным.

Если имеются Dk < 0 и в столбце Аk все элементы , то функция не ограничена сверху на ОДР.

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

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

Вектор, который нужно вывести из базиса, определяется по отношению

В базис вводим вектор A1, которому соответствует минимальное значение . Из базиса выводим вектор А3, так как минимальное значение q достигается при i = 3. Таким образом, элемент x31 будет направляющим. Строка r (в таблице помечена стрелкой) называется направляющей. Элемент хrk, который стоит на пересечении направляющей строки и столбца, называется направляющим. Таким образом, элемент х11 будет направляющим

Заполняем таблицу, соответствующая новому базисному решению.

Все элементы хij таблицы определяются по следующему рекуррентному соотношению:

(4.5)

i = 1, ..., m + 1, j = 0, ..., n, l – номер итерации.

Приведем расчет элементов таблицы 1.2;

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

Заполняем таблицу 1.2, соответствующую новому опорному плану, пользуясь рекуррентным соотношением (4.5).

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

Результаты второй и третьей итераций приводятся в таблицах 1.3 и 1.4.

Таблиця 1.2

	C	0	3	2	0	0
	Bx	A0	A1	A2	A3	A4
c1=3	x1	2	1	–1	1	0
c4=0	x4	2	0	3	-2	1
	D	6	0	–5	3	0
				­

Таблиця 1.3

	C	0	3	2	0	0
	Bx	A0	A1	A2	A3	A4
c1=3	x1		1	0
c2=2	x2		0	1
	D		0	0
					­

Таблица 1.4

	C	0	3	2	0	0
	Bx	A0	A1	A2	A3	A4
c3=0	x3	8	3	0	1	1
c2=2	x4	6	2	1	0	1
	D	12	1	0	0	2

Так как все , то план, представлений в таблице 1.4, будет оптимальным: Хопт = (0, 6, 8, 0), Fmax = 12.

Если требуется отыскать минимальное значение целевой функции, можно перейти к задаче на максимум, записав Fтах = (–1)´Fmin, и решать ее по приведенному алгоритму. Однако такая процедура не обязательна, так как описанный алгоритм позволяет решать и задачу минимизации. В этом случае оптимальный план будет получен тогда, когда все . Следовательно, если среди оценок начального опорного плана (либо плана, полученного на l-ой итерации) имеются >0 и в столбцах, им соответствующих, есть положительные элементы хij>0, то такой план можно улучшить. Если несколько векторов имеют > 0, то в базис будем вводить тот, у которого оценка больше. Остальная часть алгоритма остается той же.