48)Каноническая форма задачи линейного планирования.

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

 (5.8)

   (5.9)

   (5.10)

 (5.11)

Канонической формой записи ЗЛП называют задачу

 (5.12)

 (5.13)

 (j = 1,…,n). (5.14)

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

Итак,   . То же самое имеет место и в случае функции многих переменных (n):  .

Преобразуем систему ограничений к каноническому виду. Введем m дополнительных неотрицательных переменных     . Для того чтобы неравенства типа ≤ (5.9) преобразовались в равенства, к их левым частям прибавим дополнительные переменные     , после чего система неравенств (5.9) примет вид:

 . (5.15)

Для того чтобы неравенства типа ≥ (5.10) преобразовать в равенства, из их левых частей вычтем дополнительные переменные     . Получим

 (5.16)

Дополнительные переменные     в целевую функцию вводятся с коэффициентами, равными нулю. Целевую функцию умножаем на минус единицу. Получим задачу:

 (5.17)

 (5.18)

 (5.19)

       (5.20)

Задача (5.17) – (5.20) имеет каноническую форму. Задачи (5.8)-(5.11) и (5.17) –(5.20) тесно связаны между собой.

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

Ответ: 1)Оптимальное решение, если оно существует, располагается на границе области допустимых решений. 2)Оптимальное решение может быть не единственным, если линия уровня располагается параллельно одной из сторон многоугольника, на которой достигается оптимальное решение. 3)Если область допустимых решений в направлении убывания целевой функции, то задача решения не имеет. 4)Оптимальное решение всегда достигается в одной из вершин многоугольника допустимых решений. Все остальные решения называются опорными точками.

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

Ответ: Для решения ЗЛП в аналитической форме применяют один из методов решения – симплекс метод (метод последовательного улучшения решения), который предполагает: 1) умение находить начальный опорный план; 2)наличие признака оптимальности плана; 3) умение переходить к не худшему опорному плану. Для построение начального опорного плана исходные данные задачи должны быть представлены в канонической форме. Пусть ЗЛП представлена системой ограничений в каноническом виде:  , b_i ≥ 0 (i = 1, m). Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при не отрицательности правой части (в_i ≥ 0) левая часть ограничения содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения – равенства – с коэффициентом, равным нулю. Если каждое ограничение-равенство ЗЛП в каноническом виде содержит переменную, входящую в левую часть с коэффициентом, равным единице, а во все остальные с коэффициентом, равным нулю (при не отрицательности правых частей), то говорят, что система ограничений представлена в предпочтительном виде. В этом случае легко найти ее опорное решение (базисное с не отрицательными координатами): все свободные переменные нужно приравнять нулю, тогда базисные переменные (БП) будут равны свободным членам. Если полученный план будет иметь не более m отличных от нуля координат, то он будет опорным.

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

 , b_i ≥ 0 (i = 1, m). Приведем систему к каноническому виду

 , b_i ≥ 0 (i = 1, m), которая имеет предпочтительный вид.

Следовательно, начальный опорный план примет вид: Х₀ = (0;0;……0; b₁;b₂; …….b_m). В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю.

Пусть система ограничений имеет вид  , b_i ≥ 0 (i = 1,… m). Приведем систему к каноническому виду  , b_i ≥ 0 (i = 1,.. m),

которая не имеет предпочтительный вид, так как дополнительные переменные x_n+iвходят в левую часть (при b_i ≥ 0) с коэффициентом -1. Поэтому, базисный план Х₀ = (0;0;...0; -b₁; -b₂;… -b_m) является недопустимым. В практических задачах всегда имеются условия ограничений, которые в каноническом виде преобразуются из соотношений (х.х7), поэтому можно перейти к улучшенному решению. Приведем последовательность шагов при решении задачи оптимизации: 

шаг первый: Приводим задачу к канонической форме Z = c₀ – (   ) → min;  -БП;   - свободные переменные.

шаг второй: Находим начальный опорный план, приравняв   , тогда Z = c₀ ,   .

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

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

шаг четвертый: Переход к новой вершине ОДР, в которой значение целевой функции меньше начального. Наибольшее из положительных коэффициентов   будет указывать на ту свободную переменную   , которая может изменяться от нуля до значений, не нарушающих условия ограничений. Приравнивают БП к нулю для всех ограничений на данном шаге. Находят отношения   для j – oй свободной переменной при условии равенства нулю других свободных переменных (   ). Наименьшее из положительных   укажет ту БП, которая станет свободной, т.е. укажет уравнение ограничений, из которого определится новая БП, выраженная через новые свободные переменные. Все остальные БП и функцию цели нужно пересчитать через новые свободные переменные. Т. о. будет получен очередной опорный план. Далее повторение шагов 3 и 4. Выполнение шагов один – четыре предполагает последовательные преобразования условий ограничений и функции цели. Поэтому, в дальнейшем будем говорить о решениях, полученных методом симплекс – преобразований.