III. Проверяем выполнение критерия оптимальности при решении задачи на максимум – наличие в последней строке отрицательных коэффициентов F<0 . Если таких нет, то решение оптимально, достигнут max F, основные переменные принимают значения а_i0 (второй столбец), основные переменные равны 0, т.е. получаем оптимальное базисное решение.

    IV. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент F < 0 в последней строке определяет разрешающий столбец s.

    Составляем  оценочные ограничения каждой строки по следующим правилам:

1. бесконечность, если b_i и a_is имеют разные знаки;
2. бесконечность, если b_i =0 и a_is <0;
3. бесконечность, если a_is =0;
4. 0, если b_i =0 и a_is >0;
5. , если a_i0 и a_is имеют одинаковые знаки;

 

Определяем  минимум   Если конечного минимума нет, то задача не имеет конечного оптимума (F_max =бесконечности). Если минимум конечен, то выбираем строку q, на которой он достигается (любую, если их несколько), и называем ее разрешающей строкой. На пересечении разрешающих строки и столбца находится разрешающий элемент а_qs.

    V.  Переходим к следующей таблице по правилам:

а) в левом столбце записываем новый базис: вместо основной переменной х_q – переменную x_s;

б) в столбцах, соответствующих основным переменным, проставляем нули и единицы:

1 – против "своей" основной переменной, 0 – против "чужой" основной переменной,

0 – в последней строке для всех основных переменных;

в) новую строку с номером q получаем из старой делением на разрешающий элемент a_qs

г) все остальные элементы вычисляем по правилу прямоугольника 

               (3)

В результате получают новую симплекс–таблицу, отвечающую новому базисному решению. Далее переходим к пункту III алгоритма.

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

    В этом подразделе вводится новое понятие теории линейного программирования – понятие двойственности. Будучи исключительно важным в теоретическом отношении, оно представляет и большой практический интерес. На основе теории двойственности разработан алгоритм решения задач линейного программирования – двойственный симплексный метод и эффективные методы анализа моделей на чувствительность. Любой задаче линейного программирования можно поставить в соответствие другую задачу, сформулированную по стандартным правилам таким образом, что решение любой из них является и решением другой задачи. Такие задачи называются взаимодвойственными.

1.3.1. Построение двойственной  задачи

 

    Двойственная  обратная задача – задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой, задачи[4]. В литературе по линейному программированию в большинстве случаев рассматриваются формулировки двойственной задачи, соответствующие различным формам прямой задачи, которые, в свою очередь,

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

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

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

максимизировать

F(X) = ∑c_j x_j                                                 (4)

при ограничениях:

    

      ∑а_ij x_j ≤ b_i , i = 1,… m,                                          (5) 

x_j ≥ 0,  j = 1,… n. 
 

    Чтобы сформулировать условия двойственной задачи, проведем симметричное структурное  преобразование условий прямой задачи в соответствии со следующими правилами:

    1) каждому ограничению прямой задачи  соответствует переменная двойственной  задачи;

    2) каждой переменной прямой задачи  соответствует ограничение двойственной  задачи;

    3) коэффициенты при некоторой переменной, фигурирующие в ограничениях  прямой задачи, становятся коэффициентами  левой части соответствующего  ограничения двойственной задачи, а коэффициент, фигурирующий при  той же переменной в выражении  для целевой функции прямой  задачи, становится постоянной правой  части этого же ограничения  двойственной задачи.

    На  примере задачи планирования товарооборота  двойственная задача формулируется  следующим образом:

    определить  оценку (неявную стоимость) единицы  каждого вида ресурсов y_j (i = 1,… m), чтобы при заданных объемах ресурсов b_i , прибыли С_j нормах расхода ресурсов a_ij минимизировать оценку всех ресурсов торгового предприятия, затраченных на организацию торгового процесса.

    Запишем математическую модель двойственной задачи. 
 

    Определить  вектор У = (y₁, y₂,..., у_m), который удовлетворяет ограничениям 

∑а_ij x_i ≤ c_j , j = 1,… n,                                            (6) 

X_i ≥ 0,  i = 1,… m 
 

и обеспечивает минимальное значение целевой функции 

Z(Y)= ∑b_i y_i →min.                                              (7) 

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

    В целом двойственная задача по отношению  к исходной составляется согласно следующим правилам.

    1. Число переменных в двойственной  задаче равно числу ограничений  в прямой задаче.

    2. Матрица коэффициентов системы  ограничений двойственной задачи  получается из матрицы коэффициентов  системы ограничений прямой задачи  путем транспонирования.

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

    4. Свободными членами системы ограничений  двойственной задачи являются  коэффициенты функции цели прямой  задачи.

    5. Двойственная задача решается  на минимум, если целевая функция  прямой задачи задается на  максимум, и наоборот.

    6. Коэффициентами функции цели  двойственной задачи служат свободные  члены системы ограничений прямой  задачи.

    7. Если переменная прямой задачи  x_j ≥ 0, то j-е условие системы ограничений двойственной задачи является неравенством, если x_j – любое число, то j-е условие двойственной задачи представляет собой уравнение.

    8. Если i-е соотношение прямой задачи является неравенством, то соответствующая оценка i-го ресурса – переменная у_i ≥ 0, если i-е соотношение представляет собой уравнение, то переменная двойственной задачи у_i– любое число.

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

1.3.2. Двойственный симплексный  метод

 

    Двойственный  симплексный метод основан на теории двойственности и используется для решения задач линейного  программирования, свободные члены  которых b_i(i = 1,… m) могут принимать любые значения, а система ограничений задана неравенствами смысла «≤», «≥» или равенством «=».

    В двойственном симплексном методе оптимальный  план получается в результате движения по псевдопланам.

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

    Алгоритм  двойственного симплексного метода включает следующие этапы.

    1. Составление псевдоплана. Систему ограничений исходной задачи требуется привести к системе неравенств смысла «≤». Для этого обе части неравенств смысла «≥» необходимо умножить на (-1). Затем от системы неравенств смысла «≤» переходят к системе уравнений, вводя неотрицательные дополнительные переменные, которые являются базисными переменными. Первый опорный план заносят в симплексную таблицу.

    2. Проверка плана  на оптимальность.  Если в полученном опорном плане не выполняется условие оптимальности, то решаем задачу симплексным методом. При этом столбец θ_i имеет значения по тем строкам, в которых значения в базисных переменных и коэффициенты ведущего столбца содержат одинаковые знаки (положительные или отрицательные). В случае разноименных знаков b_i и а_ik значения θ_i не определяют.

    Если  в опорном плане условия оптимальности  удовлетворяются и все значения базисных переменных – положительные числа, то получен оптимальный план. Наличие отрицательных значений в столбце «Значения базисных переменных» свидетельствует о получении псевдоплана.

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

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

    4. Расчет нового  опорного плана.  Новый план получаем в результате пересчета симплексной таблицы методом Жордана - Гаусса.

Далее переходим к этапу 2.

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

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

     В связи с расширением производства предприятие планирует запустить новые цеха и изготавливать в них пластиковые окна 4 типов. Все типы окон изготавливаются из одних и тех же материалов, ресурс которых в данный момент не ограничен. Будет запущено 3 цеха: 1-ый будет разрезать стекла по размерам, соответствующим типам окон; 2-ой будет изготавливать стеклопакеты; 3-ий будет занимается окончательной сборкой окон и их загрузкой для отправления на склад фирмы-продавца. У предприятия уже есть обязательство на поставку 12 окон в день 4 типа. Каждый цех работает по 12 часов в сутки (720 минут в сутки). Затраты времени цехов, а также прибыль с реализации окон  указаны в таблице. Задача заключается в правильном распределении возможностей цехов, максимизации прибыли от реализации продукции.