Симплекс метод

Таблица 1.

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

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

   Алгоритм перехода к следующей таблице:

• Просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов y₀) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при решении задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;
• Просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке - разрешающий столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
• Среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, так же, как и строка, в которой он находится. [5] Если на каком-либо этапе расчета возникает неопределенность в выборе разрешающей строки, т.е. оказывается несколько равных минимальных отношений, то следует выбирать ту строку, для которой отношение элементов следующего столбца к разрешающему является наименьшим. Если при этом снова оказываются равные минимальные отношения, то составляют отношения элементов следующего столбца, и так до тех пор, пока разрешающая строка не определится однозначно; [1]
• В дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных;
• Разделим каждый элемент разрешающей строки  на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.
• Строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.
• В новой таблице все элементы разрешающего столбца = 0, кроме самого разрезающего элемента, он всегда равен 1.
• Столбец, у которого в разрешающей строке имеется 0,в новой таблице будет таким же.
• Строка, у которой в разрешающем столбце имеется 0,в новой таблице будет такой же.
• В остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

Схема 1.

     В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

     Теперь  следует просмотреть строку целевой функции (индексную), если в ней нет отрицательных значений (в задачи на нахождение максимального значения), либо положительных (в задачи на нахождение минимального значения) кроме стоящего на месте y₀ (свободного столбца), то значит, что оптимальное решение получено. В противном случае, переходим к новой симплекс таблице по выше описанному алгоритму. [5]

1.3. Смысл двойственной задачи линейного программирования

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

     f =c₁x₁ + c₂x₂ +…+ c_nx_n→max   (4)

при условиях: a₁₁x₁ + a₁₂x₂ +…+ a_1nx_n ≤ b₁

     a₂₁x₁ + a₂₂x₂ +…+ a_2nx_n ≤ b₂

     …       (5)

     a_m1x₁ + a_m2x₂ +…+ a_mnx_n ≤ b_m

     x_j ≥ 0 (j = 1, 2,…m, m ≤ n).

Задача, состоящая в нахождении минимального значения функции

     f*=b₁y₁ + b₂y₂ +…+ b_my_m→min  (6)

при условиях:  a₁₁y₁ + a₁₂y₂ +…+ a_m1y_m ≥ c₁

     a₁₂y₁ + a₂₂y₂ +…+ a_m2y_m ≤ c₂

     …       (7)

     a_1ny₁ + a_2ny₂ +…+ a_mny_m ≤ c_m

                        y_i ≥ 0 (i = 1, 2, … k ≤ m)

называется  двойственной по отношению к задаче (4) – (5). Задачи (4) – (5) и (6) – (7) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

     1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной– на минимум.

      2. Матрица

                              (8)

составленная  из коэффициентов при неизвестных  в системе ограничений (5) исходной задачи, и аналогичная матрица

                                 (9)

в двойственной задаче получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов – строками).

     3. Число переменных в двойственной  задаче равно числу ограничений  в системе (5) исходной задачи, а число ограничений в системе (7) двойственной задачи – числу переменных в исходной задаче.

     4. Коэффициентами при неизвестных  в целевой функции (6) двойственной задачи являются свободные члены в системе (5) исходной задачи, а правыми частями в соотношениях системы (7) двойственной задачи – коэффициенты при неизвестных в целевой функции (4) исходной задачи.

     5. Если i–е соотношение в системе (5) исходной задачи является неравенством, то j–я переменная двойственной задачи y_j ≥ 0. В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

     Двойственные  пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (5) прямой задачи и соотношения (7) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

     Если  одна из задач двойственной пары (4) – (5) или (6) – (7) имеет оптимальный план, то и другая имеет оптимальный план, и значения целевых функций задач при их оптимальных планах равны между собой, т. е. f _max =  f*_min.

     Если  же целевая функция одной задачи из двойственной пары неограниченна (для исходной – сверху, для двойственной – снизу), то другая задача вообще не имеет планов. [3] 

2. ПРАКТИЧЕСКИЙ РАЗДЕЛ

2.1. Описание производственной  ситуации

      Фирма по изготовлению мебели для производства 4 видов изделий (комоды, столы, стулья и кресла) должна использовать 3 вида дерева (дуб, сосна, кедр), запасы которых на планируемый месяц составляют соответственно 3000, 3360 и 7120 м². В приведенной ниже таблице 2 даны технологические коэффициенты, т.е. расход каждого вида древесины на изготовление единицы продукции, прибыль от реализации изделия каждого вида, а также количество часов, затрачиваемых на производство одной единицы продукции каждого вида. Сотрудники предприятия за планируемый месяц должны отработать не менее 5040 часов.

      Таблица 2.

     Прямая  задача:

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

     Двойственная задача:

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

2.2. Математическое описание ситуации

      Обозначим через x₁ , x₂ , x₃ , x₄ количество единиц соответствующих изделий: Комоды, столы, стулья и кресла. Тогда можно записать экономико-математическую модель задачи. 

      Прямая  задача:

     Найти максимум функции

     f=400x₁+600x₂+200x₃+1000x₄→max,

     при выполнении системы ограничений:

      x₂+2x₄ ≤ 3000

     4x₂+x₃+3x₄ ≤ 3360

     3x₁+x₂+x₃+x₄ ≤ 7120

     2x₁+3x₂+x₃+4x₄ ≥ 5040,

     где x₁ , x₂ , x₃ , x₄ ≥0.

      Двойственная задача:

      Найти минимум функции

               f=3000x₅+3360x₆+7120x₇+5040(-x₈+x₉)→min - общая оценка сырья, используемого на производство продукции,

     при выполнении системы ограничений:

   3х₇+2(-х₈+х₉) ≥ 400

                  х₅+4х₆+х₇+3(-х₈+х₉) ≥ 600

                  х₆+х₇+(-х₈+х₉) ≥ 200

                  2х₅+3х₆+х₇+4(-х₈+х₉) ≥ 1000

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

2.3. Решение задачи

     Обратим систему ограничений-неравенств в систему уравнений. Для этого введем 4 переменные x₅, x₆, x₇, x₈ ≥ 0 получим: