Решение оптимизационной задачи линейного программирования

Из теоремы(о характеристиках экстремальных точек) нахождение начальной экстремальной точки связано с разбиением матрицы A на ,

где В - матрица m x m полного ранга, называемая базисом.

N - матрица m x (n-m) ,

так чтобы  . В предыдущем примере начальная точка определялась легко. В практических задачах определить начальную точку не так - то легко. Для этого используются различные приемы.

Начальная точка может быть получена введением искусственных переменных.

Рассмотрим  два метода выбора начальной экстремальной  точки. Для обоих методов предварительно необходимо привести задачу к каноническому  виду     (причем предполагается, что (если , то i - ое ограничение умножается на (-1))).

1. Двухэтапный метод:

• на первом этапе решения задачи вводится вектор - вектор искусственных переменных размерности m.

 

 

 

где - вектор, все компоненты которого равны единице.

После окончания  первого этапа:

либо , либо

Если   исходная система несовместна, то есть допустимая область пуста.

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

• на втором этапе начиная из полученной точки решается задача минимизации целевой функции.

2. M - метод:

В этом методе также вводятся искусственные переменные и каждой искусственной переменной назначается большой положительный  штраф M (больше любого c_i )

Задача линейного  программирования принимает вид:

 

 

 

Если в  оптимальном решении , то это означает, что получено решение исходной задачи.

Если  , то это означает, что система (     ) не имеет решения.

Замечание 1.(зацикливание)

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

В принципе зацикливание преодолимо(оно встречается сравнительно редко) и в качестве практических рекомендаций может быть предложено несколько вариантов выбора следующей точки:

• отказ от точки для которой ;
• случайный выбор новой угловой точки

и так далее.

Задача  №1.01

Фабрика производит два вида красок: первый –для наружных, а второй для внутренних работ .Для производства  используются два ингредиента:

А и В. Максимально  возможные суточные запасы этих ингредиентов составляет 6 и 8 т соответственно. Известны расходы А и В на 1 т соответствующих красок (табл. 1.1). Изучение рынка сбыта показало , что суточный спрос 2-го вида не когда не превышает спрос на краску 1-го вида более , чем на 1 т. Кроме того , установлено , что спрос на краску второго вида не превышает 2т в сутки . Оптовые цены одной тонны краски равны : 3 тыс. руб. для краски 1-го вида; для краски 2-го вида  2 тыс. руб.

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

Ингредиенты	Расход ингредиентов , т ингр./т краски		Запас, т ингр./ сутки
	Краска 1-го вида	Краска 2-го вида
А	1	2	6
В	2	1	8

 

 

 

Решение

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

1. Что является искомыми величинами задачи?
2. Какова цель решения? Какой параметр задачи служит критерием эффективности (Оптимальности) решения, например, прибыль, себестоимость, время, и т.д. В каком направлении должно изменяться значение этого параметра ( к max или к min) для достижения наилучших результатов?
3. Какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены? Эти условия устанавливают как должны соотноситься друг с другом различные параметры задачи, например, количество ресурса, затраченного при производстве и его запас на складе; количество выпускаемой продукции и емкость склада, где она будет храниться; количество выпускаемой продукции и рыночный спрос  на эту продукцию и т.д

Только после  экономического ответа на все эти  вопросы можно приступать  к  записи этих ответов в математическом виде то есть к записи математической модели.

1. Искомые величины являются переменными задачи, которые как правила обозначаются малыми латинскими буквами с индексами, например, однотипные переменные  удобно представлять ввиду х=(х₁,х₂….,х_n).
2. Цель решения записывается виде целевой функции , обозначаемой  например, L(X). Математическая формула ЦФ L(X) отражает способ расчета значений параметра- критерия эффективности задачи.
3. Условия, налагаемые на переменные  и ресурсы задачи, записываются в виде системы равенств или неравенств, то есть ограничений. Левые и правые части ограничений отражают способ получения (расчет или численное значение из условия задачи) значений тех параметров задачи, на которые были наложены соответствующие условия.

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

Построим  модель задачи №1.01, используя описанную  методику

Переменные  задачи

В задачи №1.01 требуется  установить, сколько краски каждого вида надо производить. Поэтому  искомыми величинами , а значит , и переменными задачи являются  суточные объемы производства каждого вида красок:

х₁-суточный объем производства краски первого вида,  [т краски/ сутки];

х₂- суточный объем производства краски второго вида,  [т краски/ сутки].

 

 

Целевая функция 

В условии  задачи №1.01 сформулирована цель  добиться максимального дохода от реализации продукции. То есть критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Что бы рассчитать величину суточного дохода от продажи красок обоих видов, необходимо знать объемы производства красок, то есть  х₁ и х₂ т краски в сутки, а так же оптовые цены на краски первого и второго видов – согласно условию, 3 и 2 тыс. руб. за 1т краски таким образом , доход от продажи суточного объема производства краски 1-го вида равен 3х₁тыс. руб. в сутки, а от продажи краски 2-го вида – 2х₂ тыс.руб. в стуки. Поэтому запишем ЦФ виде суммы дохода от продажи красок первого и второго видов(при допущении не зависимости объемов сбыта каждый из красок )

L(X)= 3х₁ +2х₂          max[тыс.руб./ сутки]

 

 

Ограничения

Возможные объемы производства красок х₁ и х₂ ограничиваются  следующими условиями:

• количество ингредиентов А и В, израсходованное в течении суток на производство красок обоих видов, не может превышать суточного запаса этих ингредиентов на складе;
• согласно результатам изучения рыночного спроса суточный объем производства краски   2-го вида может превышать объем производства краски 1-го вида, но не более чем на 1 т краски;
• объем производства краски 2-го вида не должен превышать 2 т в сутки, что также следует из результатов изучения рынков сбыта;
• объемы производства красок не могут быть отрицательными.

Таким образом, все ограничения задачи № 1.01 делятся  на 3 группы, обусловленные:

1. расходом ингредиентов;
2. рыночным спросом на краску;
3. неорицательностью объемов производства.

Ограничения по расходу любого из ингредиентов имеют следующую  содержательную форму записи

                          ≤

 

 

   Запишем  эти ограничения в математической форме.

Левая часть ограничения – это формула расчета суточного расхода конкретного ингредиента на производство красок. Так из условия известен расход ингредиента А на производство 1 т краски 1-го вида (1 т ингр. А) и 1 т краски 2-го вида (2 т ингр. А) (см. табл. 1.1). Тогда на производство х₁ т краски 1-го вида и х₂ т краски 2-го вида потребуется 1х₁ + 2х₂ т ингр. А.

Правая  часть ограничения – это величина суточного запаса ингредиента на складе, например 6 т ингредиента А в сутки (см. табл. 1.1). Таким образом,

 

1х₁ + 2х₂ ≤ 6 т ингр. А _.     т краски       ≤       т ингр. А

                           т краски           сутки  сутки

 

Аналогична математическая запись ограничения по расходу В

 

2х₁ + 1х₁ ≤8 т ингр. В   _.   т краски ≤ т ингр. В

 т краски сутки    сутки

  

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

    Ограничение по суточному объему производства краски 1-го вида по сравнению с объемом производства краски 2-го вида имеет

содержательную форму

 ≤

 

 

и математическую форму

 

х₂ – х₁ ≤1 ≤ 

 

 

Ограничение по суточному объему производства краски 1-го вида имеет содержательную форму

                                                           

 

 

и математическую форму

 

х₁ ≤ 2                           ≤

 

 

Неотрицательность объемов производства задается как

Х₁≥0,

Х₂≥0

 

Таким образом, математическая модель этой задачи имеет вид

L(X)= 3х₁ +2х₂       max[тыс.руб./ сутки]

х₁₊2х₂≤ 6  [т ингр. А/ сутки],

2x₁₊x₂ ≤ 8 [т ингр. B/ сутки],

-x₁₊x₂ ≤ 1  [т краски/ сутки],

       x₂ ≤ 2 [т краски/ сутки],

х₁≥ 0, х₂≥ 0 [т краски/ сутки].

 

Задача  №1.03

Для пошива одного изделия требуется  выкроить из ткани 6 деталей. На пошивочной фабрике были разработаны два  варианта раскроя ткани. В табл.1,3 указаны характеристики вариантов  раскроя 10м²ткани и комплексность, на  количество деталей  определённого вида, которые необходимы для пошива одного изделия. Ежемесячный запас ткани для пошива изделия данного типа составляет 405м² .  В ближайший месяц планируется сшить 90 изделий.

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

 

Таблица 1.3.

Характеристики  вариантов раскроя отрезов ткани  по 10м²

Варианты раскроя	Количество деталей, шт/отрез.						Отходы,м2/отрез.
	1	2	3	4	5	6
1	60	0	90	40	70	90	0,5
2	80	35	20	78	15	0	0,35
Комплектность шт/изделия	1	2	2	2	2	2

Решение.