Графический метод решеия задачи линейного программирования

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

IV. Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня    (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V. Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

 

 

3. ПРИМЕНЕНИЕ ГРАФИЧЕСКОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ.

 

3.1 Экономическая постановка задачи линейного программирования

 

Предприятие электронной  промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической  линии. Суточный объем первой линии - 60 изделий, второй линии - 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели - 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

 

3.2 Построение  математической модели.

 

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

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

 – суточный объем производства радиоприемников  первой модели, [шт/сутки];

 – суточный объем производства радиоприемников  второй модели, [шт/сутки];

 

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

Цель задачи  – добиться максимального дохода от реализации продукции. Т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи радиоприемников обоих моделей, необходимо знать:

- их объемы производства, т.е. и радиоприемников в сутки;

- прибыль от их реализации  – согласно условию, соответственно 40 и 20 $.

Таким образом, доход от продажи суточного объема производства радиоприемников первой модели равен  $ в сутки, а от продажи радиоприемников второй модели – $  в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:

[$/сутки]

Ограничения

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

- количество элементов электронных схем, израсходованное в течении суток на производство радиоприемников обоих моделей, не может превышать суточного запаса этих элементов на складе;

- суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) – 80 шт;

- объемы производства радиоприемников не могут быть отрицательными.

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

1) расходом элементов  электронных схем;

2) суточным объемом  технологических линий;

3)неотрицательностью  объемов производства.

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

1) Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 20 элементов соответственно, то данное ограничение имеет вид:

[шт/сутки]

2) Ограничения по суточному объему первой и второй технологических линий имеют вид:

[шт/сутки]

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

.

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

 

3.3 Нахождение  оптимального решения задачи с помощью линейного метода.

 

Математическую  модель задачи о радиоприёмниках  мы нашли на предыдущем шаге:

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с  осями координат (рис.3.1).

прямая (1) –  точки (0;95) и (63,(3);0), прямая (2) проходит через  точку  параллельно оси , прямая (3) проходит через точку параллельно оси .

Рис.3.1. Графическое решение задачи о производстве радиоприемников.

 

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим  , что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.3.1). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDE.

Целевую прямую можно построить по уравнению

Точки пересечения  с осями – (0;75) и (37,5;0)

Строим вектор из точки (0;0) в точку (40;20). Точка D – это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому D – это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)

Получили точку D(60;5) [шт/сутки].

Максимальное  значение ЦФ равно  [$/сутки].

Таким образом, наилучшим режимом работы предприятия  является ежесуточное производство радиоприемников первой модели в количестве 60 штук и радиоприемников второй модели в количестве 5 штук. Доход от продажи составит  2500$ в сутки.

4. Понятие двойственной задачи линейного программирования.

 

Важную роль в линейном программировании имеет  понятие двойственности. Рассмотрим две задачи линейного программирования:

max{F(x) = C^T x| Ax≤B, x_i≥0, i =1,n} (1)

и

min{F(y) = B^T y| A^T y≥C, y_j ≥0, j = 1,m}. (2)

Задачу (1) называют прямой, а связанную с ней задачу (2) – двойственной. Вместе они образуют симметрическую пару двойственных задач. Число переменных двойственной задачи равно количеству ограничений прямой. Кроме того, при переходе от прямой задачи к двойственной вектора B и C меняют местами, матрица A коэффициентов системы ограничений прямой задачи транспонируется, а знак неравенств в ограничениях меняют на противоположный. Смысл экстремума F(x) противоположен смыслу экстремума F(y) . Связь между задачами (1) и (2) взаимна, т.е. если прямой считать задачу (2), то в качестве двойственной ей будет соответствовать задача (1). Возможность перехода от прямой задачи к двойственной (и наоборот) устанавливается теоремой двойственности: если одна из задач (1) или (2) имеет оптимальное решение, то и другая также имеет оптимальное решение, причем оптимальные значения функции цели прямой и двойственной задач совпадают, т.е. max F(x) = min F( y) .

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

При этом выполняются  следующие правила:

1. Если на  переменную x_i прямой задачи наложено условие неотрицательности, то i-е условие системы ограничений двойственной задачи является неравенством и наоборот.

2. Если на  переменную xi прямой задачи не  наложено условие неотрицательности, то i-е ограничение двойственной задачи записывается в виде строгого равенства.

3. Если в прямой  задаче имеются ограничения равенства,  то на соответствующие переменные  двойственной задачи не накладывается  условие неотрицательности.

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

Рассмотрим  задачу рационального использования ресурсов.

Пусть предприятие  располагает ресурсами b₁,b₂,...,b_m, которые могут использоваться для выпуска n видов продукции. Известны нормы потребления j-го ресурса на производство единицы i-й продукции – a_ij , а также прибыль от реализации единицы i-го вида продукции c_i (i = 1, n; j = 1,m) . Найти объем производства продукции каждого вида x*_i, максимизирующий суммарную прибыль предприятия F(x) = ∑c_ix_i , при этом расход ресурсов не должен превышать их наличия. Математическая модель задачи имеет вид

max{F(x)=∑c_ix_i|∑a_jix_i≤b_j, j=1,m; x_i≥0, i=1,n} (3)

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

max{F(x)=∑c_ix_i|∑a_jix_i=b_j, j=1,m; x_i≥0}.

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

а) насколько  можно увеличить запас некоторого ресурса, чтобы улучшить оптимальное  значение F;

б) насколько  можно сократить запас некоторого ресурса, чтобы сохранить при  этом оптимальное значение F;

в) увеличение объёма какого из ресурсов наиболее выгодно;

г) какому из ресурсов отдать предпочтение при вложении дополнительных средств;

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

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

Сформулируем  задачу, двойственную к рассматриваемой  задаче рационального использования  ресурсов. Пусть некоторая организация может закупить все ресурсы b_j, которыми располагает предприятие. Необходимо определить оптимальные цены y*_j ( j = 1,m) на единицу этих ресурсов при условии, что покупатель стремиться минимизировать общую оценку ресурсов. При этом общая ценность ресурсов должна быть не меньше прибыли, которую может получить предприятие при организации собственного производства. Математическая модель задачи имеет вид

min{F(y)=∑b_jy_j|∑a_ijy_j≥c_i, i=1,n; y_j0, j=1,m} (4)

Пока прибыль  предприятия (задача 3) меньше общей  ценности ресурсов (задача 4), решение обеих задач будет неоптимальным. Оптимум достигается в случае, когда прибыль становится равной общей ценности ресурсов, т.е. max F(x) = min F( y) .

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

F(x) = 3x₁ + 2x₂ (min) ;

x₁ + x₂ ≤ 5

2x₁ - x₂ ≤ 3

x₁ + 0.5x₂ ≥2

x_1,2 ≥ 0

Приведем условие  к стандартной форме (2). Так как  требуется найти минимум целевой  функции, то неравенства в системе  ограничений должны быть вида ≥. Первое и второе неравенства умножим на (-1), тогда

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

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ.

 

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

Оптимальная прибыль  от реализации продукции достигается  при следующем суточном производстве радиоприемников: 60 шт радиоприемников первой модели и 5 шт радиоприемников второй модели. При этом прибыль от реализации составит 2500$ в сутки.

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

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

- предел увеличения производительности первой линии равен 63 радиоприемника в сутки. Дальнейшее увеличение производительности не имеет смысла, т.к. значение ЦФ не улучшится.

2. Определите предел уменьшения производительности второй линии, при котором полученное оптимальное решение останется неизменным.

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

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

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