Таблица 2

     Производственные  возможности цехов и прибыль предприятия от реализации окон разных типов

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

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

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

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

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

         Так как требуется определить план производства, то переменными модели будут:

   x₁ – объём производства окон 1-ого типа, в единицах;

     x₂ – объём производства окон 2-ого типа, в единицах;

 x₃ – объём производства окон 3-его типа, в единицах;

     x₄ – объём производства окон 4-ого типа, в единицах.

     Таким образом, математическая модель задачи представлена в виде:

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

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

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

     f=6x₁+8,5x₂+9x₃+10,5x₄→max,

при наличии ограничений: 

      10x₁+12x₂+15x₃+20x₄ ≤ 720;

     15x₁+18x₂+20x₃+25x₄ ≤ 720;

     20x₁+25x₂+30x₃+35x₄ ≤ 720;

     x₄ ≥ 12. 

     Так как объёмы производства продукции  не могут принимать отрицательные  значения, то появляются ограничения  неотрицательности :

                x₁≥0   , x₂≥0   , x₃≥0   , x₄ ≥0.

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

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

               f=720x₅+720x₆+720x₇+12(-x₈+x₉)→min – общая оценка времени, затрачиваемого на производство продукции,

при наличии ограничений:

   10x₅+15х₆+20х₇≥ 6

                  12х₅+18х₆+25х₇ ≥ 8,5

                  15х₅+20х₆+30х₇ ≥ 9

                  20х₅+25х₆+35х₇+(-x₈+x₉)≥ 10,5

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

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

     I. Исходное ограничение, записанное в виде неравенства типа ≤ ( ≥),

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

     Для построения первого опорного плана  систему неравенств приведем к системе уравнений путем введения дополнительных переменных x₅, x₆, x₇, x₈ ≥0, получим:

      10x₁+12x₂+15x₃+20x₄+x₅ = 720;

     15x₁+18x₂+20x₃+25x₄+x₆ = 720;

     20x₁+25x₂+30x₃+35x₄+x₇ = 720;

     x₄-x₈ =12. 

     Все переменные неотрицательны, все ограничения  есть равенства и есть  набор  допустимых базисных переменных: х₅ – в 1-ом равенстве, х₆ – во 2-ом ,   х₇ – в 3-ем, они входят только в одно уравнение с коэффициентом 1. В 4-ое уравнение добавляем искусственную переменную x₉ ≥ 0. Чтобы можно было применить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это x₅, x₆, x₇ и x₉.

     Итак, имеем:

     f=6x₁+8,5x₂+9x₃+10,5x₄→max,

      10x₁+12x₂+15x₃+20x₄+x₅ = 720;

     15x₁+18x₂+20x₃+25x₄+x₆ = 720;

     20x₁+25x₂+30x₃+35x₄+x₇ = 720;

     x₄–x₈ +x₉ =12. 

       II. Исходную расширенную систему заносим в первую симплексную таблицу. Последняя строка таблицы называется оценочной. В ней указываются коэффициенты функции с противоположным знаком. Во втором столбце таблицы записываем основные переменные (базис), во второй строке таблицы все переменные, в предпоследнем столбце свободные члены расширенной системы. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы (начиная с третьего столбца третьей строки) заносим коэффициенты а_ij при переменных из расширенной системы. Теперь можно запускать симплекс-метод. Запишем начальную симплекс-таблицу (табл. 3): 
 

     Таблица 3

Шаг 1

     x₁=(0;0;0;0;720;720;720;12;0); f (x₁) = 0

     III, IV. Если все оценочные коэффициенты неотрицательны, то получено оптимальное решение: базисные переменные равны свободным членам, остальные равны 0. Если же есть отрицательный оценочный коэффициент, то находят самый малый из них. Если в столбце коэффициентов над ним нет положительных, то задача не имеет решения. Задача оптимального планирования не может быть таковой, поэтому ищут минимальное отношение свободных членов столбца b к положительным коэффициентам указанного x₁. В пересечении строки и столбца получаем разрешающий элемент и затем строим новую таблицу.

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

1. В  столбце базиса вместо базисной  переменной x₉ записываем свободную переменную x₄; 
2. В столбцах, соответствующих основным переменным, проставляем нули и единицы:  
      1– против "своей" основной переменной, 0 – против "чужой" основной переменной, 0 – в последней строке для всех основных переменных; 
3. Новую строку получаем из старой делением на разрешающий элемент а₄₄=1; 
4. Все остальные элементы вычисляем по правилу прямоугольника:

 

     [Пример:  a_12’= a₁₂ –(a₁₁∙a₃₂ /a₃₁) ] 

       Строится новая таблица (табл. 4)

Таблица 4

Шаг 2

     x₂ = (0;0;0;12;480;420;300;0;0);   f (x₂) = 12*10.5=126.

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

      В новой таблице переменная х₈ станет базисной за место переменной x₇. Переходим к следующей таблице (табл. 5) по правилам, описанным выше:

Таблица 5

Шаг 3