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

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

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

      (1.10)

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

     Симплексный метод позволяет наряду с получением решения прямой задачи получать и  решение двойственной задачи. Этот результат и лежит в основе двойственного симплексного метода решения задачи. Суть метода состоит в таком последовательном переборе угловых точек допустимого множества Q₀ двойственной задачи, при котором значение целевой функции возрастает, т. е. в применении симплексного метода к решению двойственной задачи. Двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными).[8]

     Отыскание решения задачи двойственным симплекс-методом  включает в себя следующие этапы:

     1. Находят псевдоплан задачи.

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

     3. Выбирают разрешающую строку  с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р₀ и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)–и строки к соответствующим отрицательным элементам разрешающей строки.

     4. Находят новый псевдоплан и  повторяют все действия начиная  со второго этапа.[9]

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

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

Глава 2. ЗЛП на примере  деятельности небольшого кирпичного завода

    Основа  построения экономических моделей  в виде ЗЛП - это, прежде всего, правильный выбор параметров экономической задачи (или некоторого процесса), через которые требуемая цель выражалась бы в виде линейной целевой функции, а ограничения на процесс записывались бы в виде системы линейных уравнений или неравенств.[12]

2.1. . Задачи ЗЛП на максимизацию и минимизацию

    Задача  планирования производства продукции (ЗЛП на максимизацию)

    

      Некоторое предприятие в течение  планового периода выпускает  2 вида продукции, например, табуретки и стулья. При их производстве используются три вида ресурсов. Данные по их расходу на выпуск одного изделия, запасы ресурсов, а также прибыль от реализации единицы продукции приведены в таблице. Требуется спланировать количество выпускаемых табуреток и стульев таким образом, чтобы при данных условиях производства полученная прибыль была максимальна.  
 
 

    Итак, цель задачи - получение максимальной прибыли. Выберем в качестве параметров, характеризующих процесс планирования   производства продукции, число выпускаемых табуреток (переменная    X₁) и выпускаемых стульев   (переменная  X₂). Выразим через   выбранные неизвестные суммарную прибыль от реализации всей продукции.

    Она включает в себя прибыль от реализации всех табуреток (4X₁) и выпускаемых стульев (5х₂). Цель  задачи   (максимизация   прибыли) запишется в виде

                              f (х₁,х₂) = 4х₁ +5х₂  → max

Перейдем    к    формулировке    ограничений.    Структура    всех    трех ограничений одинакова

РАСХОД   РЕСУРСА      ≤    ЗАПАС РЕСУРСА

Теперь  остается    выразить полный расход ресурса через выбранные неизвестные  Х₁ и Х₂ . Так, расход ресурса первого вида на выпуск всех табуреток составит   4X₁   единиц,  а на  выпуск всех стульев   6x₂ соответственно (см. первую строку таблицы). В сумме это даст полный расход ресурса  первого  вида  и  ограничение примет вид линейного неравенства

    4х₁ + 6х₂  ≤  24 

Аналогично  запишутся ограничения по второму  и третьему видам ресурсов

    Зх₁ +2x₂  ≤ 2

     x₁ +x₂ ≤ 8.

Объединяя их в систему, получим

     4х₁ + 6х₂ ≤ 24

    3x₁ +2x₂ ≤ 12

    x₁ +x₂ ≤ 8

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

    x₁ ≥ 0, х₂ ≥ 0

Окончательно  выпишем математическую модель задачи в форме ЗЛП.

    f (x_l, х₂) = 4х₁ + 5х₂    → max

    4х₁ + 6х₂ ≤ 24

    3x₁ +2x₂ ≤ 12

    x₁ +x₂ ≤ 8

    x₁ ≥ 0, х₂ ≥ 0

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

    После решения поставленной ЗЛП переменные x₁ и х₂ укажут плановое количество табуреток и стульев для получения максимальной прибыли, а разность между правой и левой частями каждого неравенства даст остаток ресурса каждого вида.

    Задача о составлении оптимального рациона (ЗЛП на минимизацию)

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

      
 
 
 

    Пусть   x₁ и х₂   - содержание в данном рационе единиц корма 1-го и 2-го вида соответственно. Общую стоимость дневного рациона запишем, используя цены на корма:

                                f (х₁,х₂) = 5x₁+ 2х₂ → min

Ограничения имеют следующую структуру:

         ≥

   Используя для записи левой  части введенные неизвестные,  получим

     2х₁ + х₂ >12

    6х₁ + 4х₂ > 30

Добавив к полученным ограничениям условия неотрицательности (Xi равно нулю, если корм i не используется в рационе), окончательно запишем ЗЛП.

    f (x_l, х₂) = 5 х₁+ 2х₂ → min

     2х₁ +х₂ ≥12

    6х₁ +4х₂ ≥30

      x₁ ≥ 0, х₂ ≥ 0  

• В  приведенных примерах все ограничения  имеют вид линейных неравенств. Это, так называемые, нежесткие ограничения (ресурс может быть израсходован полностью, а может и частично). Однако можно ставить и жесткие ограничения в виде линейных уравнений. Так, в первом примере, требование полного использования ресурса 1-го вида приводит к ограничению: 4X₁ + 6х₂ = 24

   2.2 Каракольский кирпичный завод

     В наше время возникает много споров по поводу преимуществ и недостатков  современных стеновых материалов и  обычного красного кирпича. Однако, как  говорится "собаки лают - а караван  идёт"! И из года в год, тысячи квадратных метров жилья в Кыргызстане строятся, используя проверенный временем материал - кирпич.

    Кирпич керамический полнотелый М100 и силикатный полнотелый - два вида продукции, который производит завод. Они изготавливаются на предприятии методом пластического формования и имеют морозостойкость 25 циклов.

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