Свойства задач линейного программирования
Раздел II. ЗАДАЧИ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
В этом разделе показано применение различных методов решения задач математического программирования (задач линейного программирования, транспортных задач). Для каждого метода приводится подробное решение примеров, аналогичных 2-му, 3-му и 4-му заданиям контрольной работы.
Литература: [1,8-10,14]
§1 Основные сведения из теории линейного программирования.
Задача математического программирования (3) (или (4)) называется задачей линейного программирования (ЛП), если целевая функция f есть линейная функция, а множество допустимых решений Х задается с помощью линейных неравенств или линейных уравнений:
max f(x)=c1x1+c2x2+…+cnxn (1)
при ограничениях
a11x1+a12x2+…+a1nxn≤b1
a21x1+a22x2+…+a2nxn≤b2 (2)
…………………………
ak1x1+ak2x2+…+aknxn≤bk
x1≥0,…, xn≥0 (3)
(1)-(3) - это стандартная постановка задачи ЛП (в общем случае в ограничениях (2) могут быть различные соотношения вида “≥”, “≤”, “=”). Здесь c1,…,cn - коэффициенты при целевой функции, a11,...,ann - коэффициенты при ограничениях, b1,…,bk - свободные члены при ограничениях. Все они являются известными числами (заданы); Неизвестными являются переменные x1,…,xn
В задачах (1) - (3) требуется найти такие значения переменных x1*,...,xn* (точку максимума), чтобы:
1) Эти переменные удовлетворяли воем ограничениям (2) и (3) (условие допустимости);
2) В точке х* = ( х1*,...,xn* ) целевая функция f принимала максимальное значение f(x*) (условие оптимальности).
Аналогично ставится задача на минимум.
Свойства задач линейного программирования
1. Допустимое множество задачи ЛП либо пусто, либо является выпуклым многогранником в Rn (как пересечение полупространств, описываемых неравенствами (2)-(3)). Оно может быть кfк ограниченным, так и неограниченным; в любом случае это замкнутый многогранник.
2. Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации - ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение.
3. Оптимальные решения задачи ЛП (если они существуют) всегда находятся на границе допустимого множества. Точнее, если существует единственное оптимальное решение, то им является какая-либо вершина многогранника допустимых решений; если две или несколько вершин являются оптимальными решениями, то любая их выпуклая комбинация также является оптимальным решением (т.е. существует бесконечное множество точек максимума или минимума).
Методами решения задач ЛП являются: графический метод (в случае двух переменных), симплекс-метод или его разновидности (в общем случае).
§2. Решение задачи ЛП графическим методом :
Пример 1, (случаи единственного оптимального решения). Используя графический метод, найти решение следующей задачи ЛП:
max f(x) = x1- x2
при ограничениях
(1) 3х1+2х2 ≤14,
(2) x1 – 4x2 ≤ 0,
|
(3) 3x1 – x2 ≥ 0,
(4) –x1 + x2 ≤ 2
(5) x1 ≥ 0,
(6) x2 ≥ 0.
Решение. На плоскости R2 построим допустимое множество, описываемое шестью неравенствами. Это будет пересечение шести полуплоскостей (каждое неравенство-ограничение задает на R2 полуплоскость). Например, первую полуплоскость 3x1+2х2≤14 строим так. Проводим прямую 3x1+2х2=14, которая является границей этой полуплоскости. Чтобы определить, какую из полуплоскостей, лежащих по обе стороны от прямой 3x1+2х2=14, описывает неравенство 3x1+2х2≤14, достаточно поставить в это неравенство координаты начала координат, т.е. (0,0). Если неравенство выполняется, то берем ту полуплоскость, которая содержит начало координат, если не выполняется, то берем полуплоскость, не содержащую начала координат. В нашем случае 3*0 + 2*0≤14. На рис. 1 в кружочках написаны номера линий (границ полуплоскостей), а полуплоскости обозначены стрелками. В результате пересечения построенных шести полуплоскостей получаем многогранник ОАВС. который и является допустимым множеством нашей задачи. Можно проверить, что любая точка этого многогранника удовлетворяет всем шести неравенствам, а для любой точки вне этого многогранника хотя бы одно неравенствоиз шести будет нарушено.
Таким образом, геометрически наша задача свелась к тому, чтобы в пределах многогранника ОАВС найти точку х* = (x1*,x2*). в которой целевая функций f(x) = x1-x2 получит максимальное значение.
Благодаря свойству 3 (см. выше) мы заранее знаем, что точкой максимума нашей целевой функции является одна или некоторые из вершин О,А,В или С.
Для того, чтобы определить эту вершину, проведем какую-либо линию уровня целевой функции, т.е. проведем прямую f(x)=с1, где с-const. Для простоты возьмем с=0, тогда линия уровня есть x1-x2=0. Увеличивая правую часть этого уравнения (например, x1-x2=1, x1-x2=3 и т.д.), мы обнаружим параллельное смещение линии уровня вниз, причем, чем больше правая часть, тем дальше. Если же уменьшим правую часть (например, x1-x2=-1, x1-x2=-2 и т.д.), то наблюдаем смещение вверх.
Отсюда понятно, что, смещая линию уровня в сторону возрастания целевой функции, мы найдем ту вершину многогранника ОАВС, которая соответствует точке максимума. Как видно из рисунка 1, это есть точка С.
Чтобы сразу определить направление возрастания функции t, вычисляют ее градиент Ñf. Для линейной функции градиент всегда равен вектору, составленному из коэффициентов этой функции.
Для нашей целевой функции f(x)= x1-x2 градиент Ñf = (1,-1) (см. рис, 1). Известно, что градиент перпендикулярен линии уровня и показывает направление возрастания функции, а антиградиент, т.е. вектор -Ñf показывает направление убывания функции.
Итак, "двигая" линию уровня x1-x2=0 в сторону вектора Ñf, находим точку максимума С.
Координаты точки С найдем решая совместно уравнения линий 1 и 2, пересекающихся в точке С:
3x1+2x2=14
x1-4x2=0
Ответ: х*=(4,1) - точка максимума,
f(x*) = 3 - максимальное значение целевой функции.
Отсюда получаем алгоритм графического метода:
1) построить на плоскости допустимое множество,
2) построить линию уровня целевой функции,
3) построить градиент (в задаче на максимум) или антиградиент (в задаче на минимум) целевой функции,
4) найти и вычислить координаты точки максимума или минимум,
|
5) вычислить значение целевой функции в найденной точке.
Пример 2. (Случай бесконечного множества оптимальных решений):
min f(x)=--x1-2x2
при ограничениях
x1+2x2≤7
2x1+x2≤8
x2≤3
x1,x2≥0
Как видно из рис. 2, наиболее удаленным в сторону антиградиента -Ñf=(1,2) местом касания линии уровня f(x)=с с допустимым множеством OABCD является грань ВС (т.е. выпуклая оболочка вершин B=(l, 3) и С=(3,2)). Поэтому любая точка грани ВС является точкой минимума целевой функции.
Ответ: х*=a(1,3)+(1-a)(3,2)=(3-2a,2+a) для любого aÎ[0, 1] - точка минимума,
f(x*)=-7 - минимальное значение целевой функции.
Пример 3. (Случай отсутствия оптимального решения ввиду неограниченности целевой функции на допустимом множестве):
min f(x) == -x1-2x2
при ограничениях:
x1+x2³1
2x1-x2³-1
x1-2x2≤0
x1,x2≥0
|
Допустимое множество этой задачи представляет собой неограниченный многогранник (рис. 3).
При параллельном переносе линии уровня f(x)=с вдоль антиградиента -Ñf=(1,2) она всегда пересекает допустимое множество, т.е. нет "наиболее удаленной точки касания", а целевая функция неограниченно убывает.
Ответ: Точки минимума нет; целевая функция неограниченна снизу.
Пример 4. (Случай отсутствия оптимального решения ввиду пустоты допустимого множества):
max f(x)=x1+x2
при ограничениях
-x1+x2≤-1
|
-x1-x2≤-1
x1,x2≥0
Как показано на рис, 4, полуплоскости, образованные первыми двумя неравенствами, не пересекаются (система не совместна); Поэтому нет ни одной допустимой точки.
Графический метод применяется и в том случае, когда в задаче ЛП число линейно независимых ограничений-неравенств (каноническая форма) ровно на два меньше числа переменных. Об этом подробно можно почитать, например, в [8, стр. 49].
§3. Решение задачи ЛП симплекс-методом.
Пример 5. (Решение Задачи ЛП данной в канонической форме):
min f(x)=x1+9x2 + 5x3 + 3x4+4x5+14x6 (4)
при ограничениях
(5)
xi≥0, i=1,…,6.
Говорят, что задача ЛП имеет каноническую форму, если все ограничения (кроме условий неотрицательности переменных) имеют вид строгих равенств, а все свободные члены неотрицательны.
Идея симплекс-метода заключается в следующем. Сначала надо найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение - н.д.б.р.). Затем надо проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности числа ограничений задачи ЛП) за конечное число "шагов" мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).
Таким образом, идея симплекс-метода основывается на трех свойствах задачи ЛП (см. §1).
Решение. Чтобы найти начальное допустимое базисное решение (н.д.б.р.), т.е. чтобы определить базисные переменные, систему (5) нужно привести к "диагональному виду". Применяя метод Гаусса (метод последовательного исключения неизвестных), получаем из (5):
(7)
Следовательно, базисными являются переменные x2, x4, x5, x6, им придаем значения, равные свободным членам соответствующих строк: x2=40, x4=20, x5=10, x6=30. Переменные x1 и x3 являются небазисными x1=0, x3=0.
Построим начальное допустимое базисное решение:
x0=(0, 40, 0, 20, 10, 30) (8)
Для проверки на оптимальность найденного решения x0 нужно из целевой функции исключить базисные переменные (с помощью системы (7)) и построить специальную таблицу (таково требование симплекс-метода).
После исключения переменных целевую функцию удобно написать в виде:
f(x)+7x1-14x3=880 (9)
Теперь при помощи (7),(8),(9) составляем начальную симплекс-таблицу:
Таблица 1
| x1 | x2 | x3 | x4 | x5 | x6 | - шапка таблицы | ||
| f | - нулевая строка | |||||||
| x2 | ||||||||
| x4 | … | |||||||
| x5 | -1 | -1 | ||||||
  x6
| - четвертая строка |
первый столбик … шестой столбик
нулевой столбик
базисный столбик
В нулевую строчку записаны коэффициенты соответствующих переменных при целевой функции. Так как все переменные в (4), неотрицательны, то целевая функция тем меньше, чем меньше эти коэффициенты. Отсюда критерий оптимальности: д.б.р. (х0) оптимально, если в нулевой строчке нет ни одного строго положительного числа (не считая значения целевой функции (880)). Это правило отражается и на следующие итерации (таблицы). Элементы нулевой строки будем называть оценками столбцов.
Так, что н.д.б.р. (8) неоптимально: 7>0, 14>0.
В нулевом столбике записаны значения базисных переменных. Они обязательно должны быть неотрицательными (см. условие (6)). От первой по четвертую строки написаны коэффициенты переменных из системы (7).
Так как x0 неоптимально, то надо перейти к другой вершине многогранника допустимых решений (построить новое д.б.р.). Для этого нужно найти ведущий элемент и провести симплексное преобразование (таково требование симплекс-метода).
Ведущий элемент таблицы стоит в пересечении ведущего столбика (столбец с наибольшей положительной оценкой) и ведущей строки (строки, соответствующей минимальному соотношению элементов нулевого столбика к соответствующим элементам (строго положительным) ведущего столбика.
В таблице 1 ведущий столбик - третий столбик, и ведущая строка - четвертая строка(min {40/1, 30/1}=30/1) обозначены стрелками, а ведущий элемент — кружочком. Ведущий элемент показывает, что базисную переменную x6 нужно заменить на небазисную x3. Тогда новыми базисными переменными будут x2, x3, x4, x5, а небазисными – x1, x6. Это и означает переход к новой вершине х00 многогранника допустимых решений. Чтобы найти значения координат д.б.р. х00, нужно строить новую симплекс-таблицу и провести в ней элементарные преобразования:
а) все элементы ведущей строки поделить на ведущий элемент, превратив этим самым ведущий элемент в 1 (для простоты выкладок);
б) с помощью ведущего элемента (равного 1) все элементы ведущего столбика превратить в нули (аналогично методу исключения неизвестных);
В результате в нулевом столбце получены значения новых базисных переменных x2, x3 ,x4, x5 (см. таблицу 2) - базисные компоненты новой вершины х00 (небазисные компоненты x1=0, x6=0).
Таблица 2
| x1 | x2 | x3 | x4 | x5 | x6 | ||
| f | -14 | ||||||
 x2
| (1) | 1 | -1 | ||||
| x4 | |||||||
| x5 | -1 | ||||||
| x3 |
Как показывает таблица 2 новое базисное решение x00=(0,10, 30, 20, 40, 0) неоптимально (в нулевой строке есть неотрицательная оценка 7), Поэтому с ведущим элементом 1 (см. таблицу 2) строим новую симплекс-таблицу, т.е. строим новое д.б.р. (таблица З):
Таблица 3
| x1 | x2 | x3 | x4 | x5 | x6 | ||
| f | -7 | -7 | |||||
| x1 | .1 | ||||||
| x4 | -1 | ||||||
| x5 | |||||||
| x3 |
Таблице 3 соответствует д.б.р.
x000 = (10, 0 ,30. 10, 50,0),
и оно оптимально, т.к. в нулевой строчке нет положительных оценок. Поэтому
f(x000) = 390
есть минимальное значение целевой функции.
Ответ: х000 =(10, 0, 30, 10, 50, О) - точка минимума
f(x000) = 390
Пример 6. (Решение задачи ЛП, не имеющей каноническую форму):
min f(x) = x1 – x2 – x3 (8)
при ограничениях
(9)
x1,x2,x3≥0 (10)
Умножая обе части (9) на -1 и прибавляя в левые части системы дополнительные (или слабые) переменные x4≥0, x5≥0, x6≥0, получаем, каноническую форму (слабые переменные на целевую функцию не влияют):
(11)
x1,…,x6≥0
Так как все слабые переменные входят со знаком "+'', то их можно взять в качестве базисных и составить н.д.б.р. х0=(0, 0, 0, 1, 2, 5). В данном случае исключать базисные переменные из целевой функции нет надобности (т, к. они в ней отсутствуют), поэтому целевую функцию записываем сразу в виде
f(x)-x1+x2+3x3=0 (12)
(требование симплекс-метода). С помощью н.д.б.р. х0 и выражений (11) и (12) составим начальную симплекс-таблицу (здесь f(x0)=0).
| x1 | x2 | x3 | x4 | x5 | x6 | ||
| f | -1 | ||||||
| x4 | -1 | (1) | |||||
| x5 | -4 | -1 | |||||
| x6 |
Так как x0 неоптимален (в нулевой строке есть положительные числа 1 и 3), то с обозначенным ведущим элементом строим новое д.б.р. И так далее. На четвертой итерация (шаге) получаем таблицу:
| x1 | x2 | x3 | x4 | x5 | x6 | ||
| f | -46/3 | -19/3 | -11/3 | -1/3 | |||
| x3 | е | ||||||
| x2 | 11/3 | -1/3 | 1/3 | 2/3 | |||
| x1 | 1/3 | -1/2 | -1/3 | 1/3 |
В качестве упражнения проверьте правильность вычисления элементов этой таблицы, выполнив пропущенные две итерации (таблицы).
Как видно из последней таблицы, оптимальным решением задачи является
x0000=(l/3,1l/3,4) и f(x0000)=-46/3
Как итог рассмотрения двух примеров, приведем алгоритм симплекс-метода:
1) Привести задачу к канонической форме;
2) Привести систему ограничений к диагональной форме и определить базисные переменные;
3) исключить базисные переменные из целевой функции;
4) достроить симплекс-таблицу;
5) проверить найденное д.б.р. на оптимальность: если оно оптимально, то решение закончить; если нет, то идти к пункту 6;
6) вычислить ведущий элемент таблицы;
7) провести симплексное преобразование;
8) Построить новое д.б.р. и идти к пункту 5
П р и м е ч а н и я к симплекс-методу.
1. Если в ведущем столбике нет ни одного строго положительного элемента, то задача не имеет оптимального решения, а целевая функция неограничена снизу (в задаче на минимум) или неограничена сверху (в задаче на максимум).
2. Несовместимость системы ограничений (в канонической форме) обнаруживается при построении начального д.б.р. (оно не существует).
3. Если в последней (оптимальной) таблице оценка какой-либо небазисной переменной (число в нулевой строке) равна нулю, то задача, имеет бесконечное множество оптимальных решений.
4. Симплекс-метод за конечное число итераций либо приводит к оптимальному решению, либо устанавливает неразрешимость задачи (см. пп. 1.2,3).
5. На каждой итерации симплекс-метод сохраняет допустимость базисного решения, т.е. неотрицательность элементов нулевого столбика - следствие правила выбора ведущей строки.
6. На каждой итерации целевая функция убывает (в задаче на минимум) или возрастает (в задаче на максимум); это свойство нарушается только в случае зацикливания (см. примечания 11,12).
7. В качестве ведущего столбика можно выбирать любой столбик с положительной оценкой (в задаче на минимум), однако, максимальность оценки ведущего столбика ведет к сокращению числа итераций (целевая функция быстро убывает).
8. Слабые переменные со знаком "+" (вводимые для канонизации неравенств вида “≤”) можно использовать в качестве базисных переменных, и слабые переменные со знаком “-” (вводимые для канонизации неравенств вида “≥”) - нет.
9. Структуру симплекс-таблицы можно упростить, если на каждой итерации исключать из таблицы столбики для базисных переменных. При этом сокращается объем вычислений.
10. При решении симплекс-методом задачи на максимум изменяется только правило выбора ведущей строки (столбик с минимальной отрицательной оценкой) и критерий оптимальности (отсутствие в нулевой строке отрицательных оценок).
11. Д.б.р., в котором одна или несколько базисных переменных равны нулю, называется вырожденным д.б.р. Появление такого д.б.р. в процессе решения может привести к зацикливанию, т.е. к повторному вхождению переменной в базис (геометрически: возвращение к предыдущей вершине многогранника). Предвестником зацикливания является, неоднозначное определение ведущей строки.
12. Для выхода из зацикливания: в критерии определения ведущей строки вместо элементов 0-го столбика применяют элементы 1-го столбика; если и здесь ведущая строка неоднозначна, то применяют элементы 2-го столбика и так далее, пока ведущая строка не будет определена однозначно.
§4. Решение задачи ЛП двухфазным симплекс-методом
Двухфазный симплекс-метод (или. метод искусственного базиса) применяется в тех случаях, когда и задаче ЛП в канонической форме затруднительно определить н.д.б.р. с помощью эквивалентных преобразований (привести систему ограничений к диагональному виду).
Пример 7. Следующую задачу ЛП решить двухфазным симплекс-методом:
min f(x)=x1-x2+1 (13)
при ограничениях
(14)
x1, x2, x3≥0 (15)
Первая фаза (цель: при- помощи искусственного базиса и симплекс-метода определить базисные переменные из числа исходных переменных).
В систему (14) вводим искусственные переменные x3≥0, x5≥0, x6≥0 (предварительно умножив обе части второго неравенства на -1), новую целевую функцию как сумму всех искусственных переменных, а старую присоединяем к ограничениям:
min z(x) = x4 + x5 + x6 (16)
при ограничениях
(17)
Искусственные переменные x4, x5, x6 выбираем в качестве базисных, а все остальные x1, x2, x3 - небазисных. По правилу симплекс-метода исключаем базисные переменные из целевой функции (16) (при помощи уравнений системы (17), содержащих эти переменные):
z(x)= -2 x1 - 15 x2 - 5 x3 + 15
или, что все равно
z(x)+2x1+15 x2+5 x3=15 (19)
Начальное д.б.р.
x0=(x10, x20, x30, x40, x50, x60)=(0, 0, 0, 1, 3,11)
называется искусственным базисом. При помощи этого базиса, и выражений (19), (17) строим начальную симплекс-таблицу I-ой фазы.
 |
| x1 | x2 | x3 | x4 | x5 | x6 | ||
| z | |||||||
| f | -1 | ||||||
 x4
| (1) | ||||||
| x5 | -1 | -1 | |||||
| x3 |
До конца I фазы роль нулевой строки играет строка для z, все остальное как в симплекс-методе (см. примеры 5,6). Следует только заметить, что строка для f не участвует в выборе ведущей строки.
Из (16) видно, что min z(x) = 0 и достигается при x4= x5 = x6=0, те, задача (16)-(18) будет решена, если все искусственные переменные будут вытеснены из базиса, а z=0. Это и будет означать конец первой фазы и переход ко второй фазе.
Обратите внимание, что в первой таблице ведущей может быть любая из последних трех строк (предвестник зацикливания). В таких случаях можно выбрать любой из них - выберем первую строку.
Так как искусственная переменная x4 выходит из базиса, то соответствующий столбик в дальнейшем можно исключить.
В результате соответствующих преобразований получим вторую симплекс-таблицу.
| x1 | x2 | x3 | x4 | x5 | ||
| z | -28 | -40 | ||||
| f | -3 | -3 | ||||
| x2 | ||||||
| x5 | -7 | -10 | ||||
| x6 | -21 | -30 |
Из таблицы следует, что min z достигнут, однако искусственные переменные x5 и x6 еще не выведены из базиса. В такой ситуации правила симплекс-метода "не работают" (т.к. ввиду отсутствия в нулевой строке положительных оценок нельзя выбрать ведущий столбик). Задача здесь одна - вывести оставшиеся искусственные переменные из базиса. Выведем сначала x5. Умножим все элементы этой строки на -1 (что допустимо, т.к. в нулевом столбике стоит 0). Введем в базис вместо x5 переменную x1. С этой целью строку для x5 поделим на 7 и с "ведущим элементом" 1 выполним элементарные преобразования (как в симплекс-методе). В результате получим таблицу:
| x1 | x2 | x3 | x6 | ||
| z | |||||
| f | 9/7 | ||||
| x2 | 1/7 | ||||
| x1 | 10/7 | ||||
| x6 |
Остается в базисе еще x6. Ее из числа базисных вывести нельзя, так как все элементы таблицы равны нулю, кроме 1 в столбике для x6. Это говорит о том, что в системе (14) третье уравнение было "лишним" и потому последнюю строку таблицы можно вычеркнуть. Действительно, третье уравнение в (14) является линейной комбинацией первых двух (оно получается вычитанием второго уравнения, умноженного на 3, из первого уравнения, умноженного на 2),
Вычеркивая столбик для x6 и строку для z приходим к таблице,
| x1 | x2 | x3 | ||
| f | 9/7 | |||
| x2 | 1/7 | |||
| x1 | 10/7 |
содержащей только элементы исходной задачи (13)-(15) и с базисными переменными изчисла исходных переменных.
Таким образом, задача I фазы выполнена.
Вторая фаза (цель: применяя обычный симплекс-метод к полученной в результате I фазы таблице, получить оптимальное решение исходной задачи).
Д.б.р. для последней таблицы есть
x0=(0, 1, 0)
Заметим, что это вырожденное д.б.р., так как в нем базисная переменная x1 - 0. То есть здесь мы можем получить зацикливание.
В качестве упражнения II фазу предлагается сделать самостоятельно.
Теперь можно привести алгоритм двухфазного симплекс-метода:
1) привести задачу ЛП к канонической форме;
2) ввести в ограничения искусственные переменные и составить новую целевую функцию z;
3) исключить из новой целевой функции все искусственные переменные;
4) используя искусственные переменные в качестве базисных, построить начальную симплекс-таблицу;
5) использовать симплекс-метод, исключая из таблиц столбики для искусственных переменных по мере их выхода из базиса до тех пор, пока min z=0 и все искусственные переменные не будут выведены из базиса;
6) вычеркнуть строчку для z и перейти ко второй фазе;
7) во второй фазе, к таблице, полученной в результате первой фазы, применить симплекс-метод до тех пор, пока не найдется оптимальное решение исходной задачи или не выявится его отсутствие.
П р и м е ч а н и я к двухфазному симплекс-методу
1. Если в результате первой фазы окажется, что min z > 0, то система ограничений исходной задачи (в канонической форме) несовместна. Во всех остальных случаях первая фаза разрешима.
2. Если min z= 0 и в таблице остались искусственные переменные, то, используя элементарные преобразования, эти переменные следует вывести из числа базисных, а вместо них ввести исходные переменные (см. пример 7).
3. Пусть каноническая форма задачи ЛП получена с помощью слабых переменных. Применение двухфазного симплекс-метода упростится, если искусственные переменные ввести только в те ограничения, ж которых слабая переменная либо отсутствует (исходное ограничение-равенство), либо не может войти в базис (введена в ограничение со знаком минус).
§5. Решение транспортной задачи методом потенциалов.
Существует большое число задач, сводимых к моделям транспортных задач (см., например, задачи в разделе I). Условие классической транспортной задачи (ТЗ) дано в §4 раздела I, а ее математическая модель - в том же разделе формулами (5)-(8).
Обозначим через P1,...,Pn пункты производства (или хранения) продукции, а через M1,...,Mm -пункты ее потребления. В модели (5)-(8);.
cij - стоимость перевозки единицы продукции по маршруту (Pi, Mj);
xij - объем перевозок по маршруту (Pi, Mj);
ai - предложение в пункте Pi;
bj - спрос в пункте Mj
Известными являются следующие данные: (a1,...,am) - вектор предложений, b=(b1,...,bn) - вектор спроса,
- матрица транспортных издержек.
Неизвестными являются перевозки xij, т.е. матрица (или план) перевозок
В задаче (5) - (8) требуется найти такой план перевозок X*, чтобы:
1) Элементы этой матрицы удовлетворяли всем ограничениям (6) - (8) (условие допустимости).
2) Элементы этой матрицы соответствовали минимальному значению целевой функции (5) (условие оптимальности).
Такой план называется оптимальным планом перевозок. Метод решения ТЗ называется методом потенциалов.
Если пункты производства P1,...,Pm трактовать как филиалы одной фирмы, то в ТЗ лицом принимающим решение (планирующим органом), является эта фирма.