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

3.1. Переход от общей задачи к стандартной

1. 
   Для удобства применения методов решения выполняют преобразование исходной общей задачи. Ограничения неравенства преобразуют в равенства. Вводятся дополнительные переменные по числу неравенств, т. е. формулируют расширенную задачу x_n+1 ≥0, x_n+2 ≥0, ... , x_n+k ≥0. Неравенства a_i1x₁+a_i2x₂+...+a_inx_n ≥b_i введением переменной x_n+1≥0 преобразуются в равенства a_i1x₁+a_i2x₂+...+a_inx_n + a_i(n+1)x_n+1=b_i. В ЦФ вновь введённые переменные имеют коэффициенты равные нулю c_n+1=c_n+2=...=c_n+k =0.
   
2. 
   а) Если в исходной общей задаче на некоторые переменные x_j , j = 1(1)n,  не наложено условие их неотрицательности, то каждую такую переменную представляют в виде разности положительных новых переменных x'_j - x''_j , где x'_j≥0 и x''_j≥0 , j>r . Способ устранения отрицательных переменных прост, но при этом размерность (число неотрицательных переменных) задачи возрастает. б) Имеется другой более сложный путь. Каждую x_j ≯ 0 выражают явно через другие, для которых условие x_j ≥0 выполняется. Затем найденные выражения подставляют в ограничения, чтобы исключить их из рассмотрения. При этом размерность задачи даже уменьшается. 
   

4. Каноническая форма задачи
Удобство этой формы ЗЛП состоит в том, что она позволяет предельно просто получить первое допустимое решение. Для этой формы должны быть выполнены условия:

• 
  правые части в ограничениях – неотрицательны b_i ≥ 0, i = 1(1)m;
  
• 
  каждое уравнение содержит переменную x_j ≥0  с коэффициентом при ней равным “1” в этом уравнении и с коэффициентом “0” во всех других уравнениях; эти переменные называют дополнительными или искусственными;
  
• 
  в ЦФ эти переменные входят с коэффициентом “0”;
  
• 
  определение опорного плана (начальной вершины) выполняют методом искусственного базиса, что ещё до решения задачи позволяет выяснить факт существования решения.
  

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

Переменные x₁, x₂, ..., x_m называют базисными – остальные свободными (внебазисными). Вершина допустимой области решений записывается в виде точки <β₁, β₂, ..., β_m, 0, 0,...,0>, так как векторы условий для x₁, x₂, ..., x_m являются линейно независимыми (образуют подматрицу, где единицы помещаются только на главной диагонали).
5. Геометрическая интерпретация ЗЛП
Будем рассматривать пример ЗЛП в производстве двух видов продукции на предприятии, использующем при этом четыре виды сырья (см. ранее эту задачу). Этот пример удобен для геометрической интерпретации тем, что пространство решений является двумерным (т. е. плоскость) и все элементы ЗЛП допускают наглядное представление (изображение) в трёхмерном пространстве. Начнём с рассмотрения системы неравенств (ограничений ЗЛП). Заметим, что каждое i-е неравенство в ограничениях ЗЛП определяет полуплоскость в системе координат х₁Ох₂ с граничной прямой a_i1x₁ + a_i2x₂ = b_i , i = 1(1)m.
Рисунок 1 - Примеры областей, рписывающих ограничения, задачи линейного программирования
Выпишем их и присвоим им имена

Область, формируемая полуплоскостями, может быть получена в виде замкнутого или разомкнутого (неограниченного) многогранника. Путём непосредственного построения границ (прямых) и выявления области пересечения полупространств выясним, является ли многогранное множество ограниченным и не пусто ли оно (рис.). Имеем на плоскости х₁ О х₂ многоугольник А Ո В Ո C Ո D Ո E Ո F . Он является выпуклым (всегда ли?), его граница образована отрезками прямых.