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

Целевая функция (2.21)

Нахождение начального опорного плана задач линейного программирования

Ограничения на переменные

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

Целевая функция

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

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

Построить перпендикулярно к нему в области допустимых решений одну из прямых семейства;

Построить вектор градиента;

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

Пример 3.

Решить задачу из примера 1 графическим способом:

Решение.

Выразим.

Получим

,.

\

1. Пусть в системе ограничений имеется единичный неотрицательный базис. Например, задача ЛП имеет вид:

(2.22)

,. (2.23)

,. (2.24)

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

2. Пусть задача ЛП представлена в симметричном виде, т.е.

(2.25)

(2.26)

,. (2.27)

,. (2.28)

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

(2.29)

(2.30)

,. (2.31)

,. (2.32)

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

,.

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

(2.33)

(2.34)

,. (2.35)

,. (2.36)

Привести задачу к каноническому виду можно, рассматривая целевую функцию с противоположным знаком и вычитая из левых частей системы ограничений балансовые переменные,:

(2.37)

(2.38)

,. (2.39)

,. (2.40)

Тогда начальный план

,.

4. Пусть задача ЛП приведена к каноническому виду, однако система ограничений не имеет единичного неотрицательного базиса:

(2.41)

(2.42)

,. (2.43)

,. (2.44)

Для получения предпочтительного вида вводят неотрицательные искусственные переменные и рассматривают вспомогательную w-задачу:

(2.45)

(2.46)

,,,, (2.47)

,. (2.48)

Ее начальный план будет

,.

Дата добавления: 2013-12-13