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

Размещено на http://www.allbest.ru/

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

Условие задачи №1

Задача о выборе оптимальных технологий

Продукция в цехе может производиться n различными способами T_j (n=3). Для производства продукции могут использоваться ресурсы: рабочая сила, сырьё (сталь, древесина, цветные металлы), электроэнергия. Обозначения:

x_j - время использования технологического способа T_j при производстве продукции (j=1,2,3);

b_i - объем ресурса R_i (i=1,2,3);

a_ij - расход ресурса R_i за единицу времени по технологии T_j;

A - годовое плановое задание по выработке продукции (ден. ед.);

c_j - производительность технологии T_j (в денежных единицах за единицу времени работы по данной технологии);

l_j - затраты на изготовление продукции в единицу времени по технологии T_j (денежных единицах).

Налагаются ограничения по объемам b_i ресурсов (вида ) и по плановому выпуску A продукции (вида ).

Возможны три критерия f₁, f₂, f₃ оптимальности плана X=(x₁,…,x_n) применения каждого технологического способа:

а) f₁ - наибольший объем выпускаемой продукции по всем технологиям (ден. ед.);

б) f₂ - наименьшие затраты на выполнение планового задания (ден. ед.);

в) f₃ - наибольшая конечная прибыль от выпуска продукции с учетом затрат на изготовление продукции (ден. ед.).

В табл. 1 представлены объемы bi ресурсов Ri, их расход a_ij в единицу времени для каждой технологии, плановое задание A, производительности cj технологий T_j и затраты l_j.

Задание

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

2. Дать математические постановки задач.

3. Привести полученные три математические модели к каноническому виду. Указать экономический смысл дополнительных (балансовых) переменных.

Таблица 1

Ресурсы	Технологические способы	Объем ресурсов
	T1	T2	T3
Рабочая сила, чел-ч	12	10	8	684
Сырье, т	6	5	3	690
Электроэнергия, кВт ч	4	2	3	558
Производительность технологического способа, ден. ед.	51	38	42	5370
Затраты в ед. времени работы по технологическому способу, ден. ед.	35	19	24

Решение

а) Пусть требуется реализовать первый критерий f₁ оптимальности плана X=(x₁,…,x_n), т.е. объем выпускаемой продукции по всем технологиям должен быть наибольшими. Поскольку x₁, x₂, x₃ время использования технологического способа T₁, T₂, T₃, соответственно, то объем использования каждого ресурса в соответствии с таблицей будет равен:



При этом потребление каждого ресурса не должно превышать их объемов, т.е. 684, 690, 558, соответственно. Таким образом, связь между потреблением ресурсов и их объемами выражается следующей системой неравенств:

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

F = 51x₁ + 38x₂ + 42x₃ (ден. ед.) (2)

Добавляя сюда условия неотрицательности

(3)

Сформулируем математическую модель задачи по критерию №1:

Найти такой план использования технологических способов X=(x₁, x₂, x₃), который удовлетворяет системе (1) и условиям (3), при которых целевая функция (2) принимает максимальное значение.

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

Новые переменные имеют следующий смысл: x₄ - количество неиспользуемой рабочей силы, x₅ - количество неиспользуемого сырья, x₆ - количество неиспользуемой электроэнергии.

б) Пусть требуется реализовать второй критерий f₂ оптимальности плана X=(x₁,…,x_n), т.е. затраты на выполнение планового задания должны быть наименьшими. В отличие от выше рассмотренной задачи, здесь добавляется дополнительное условие, т.е. кроме ограничений по объемам ресурсов налагаются условия по плановому выпуску продукции. Учитывая производительность каждого технологического способа и годовое плановое задание по выработке продукции, по данным табл. 1 получим ограничение 51x₁ + 38x₂ + 42x₃ ? 5370. Таким образом, система ограничений будет иметь вид



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

F = 35x₁ + 19x₂ + 24x₃ (ден. ед.)

Сформулируем математическую модель задачи по критерию №2:

Найти такой план использования технологических способов X=(x₁, x₂, x₃), удовлетворяющий системе (5) и условиям (6), при которых целевая функция (7) принимает минимальное значение.

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

Новые переменные имеют следующий смысл: x₄ - количество неиспользуемой рабочей силы, x₅ - количество неиспользуемого сырья, x₆ - количество неиспользуемой электроэнергии, x₇ - количество продукции, выработанной сверх плана.

в) Пусть требуется реализовать третий критерий f₃ оптимальности плана X=(x₁,…,x_n), т.е. конечная прибыль от выпуска продукции с учетом затрат на изготовление продукции должна быть наибольшей. В отличие от случая а), целевая функция будет иметь вид

,

F = 16x₁ + 19x₂ + 18x₃

математический линейный программирование

Сформулируем математическую модель задачи по критерию №3:

Найти такой план использования технологических способов X=(x₁, x₂, x₃), удовлетворяющий системе (1) и условиям (3), при которых целевая функция (9) принимает максимальное значение.

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

Новые переменные имеют следующий смысл: x₄ - количество неиспользуемой рабочей силы, x₅ - количество неиспользуемого сырья, x₆ - количество неиспользуемой электроэнергии.

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

Условие задачи №2

Задача о выборе оптимальных технологий

Предприятие выпускает продукцию вида P₁ и P₂, на изготовление которой используется сырье S₁, S₂, S₃. Известны:

b_i - запасы сырья; a_ij - нормы расхода сырья S_i (i=1,2,3) на производство единицы продукции (j=1,2); c_j - себестоимость единицы продукции P_j; p_j - оптовая цена единицы P_j.

Определить оптимальный план X=(x₁,x₂) производства продукции P₁ и P₂, при котором при имеющемся количестве сырья можно получить наибольшую прибыль.

Задание

1. Записать числовые данные таблицу и составить математическую модель задачи.

2. Решить задачу графическим методом.

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

4. Определить аналитически и графически, можно ли произвести 3 ед. продукции P₁ и 2 ед. продукции P₂.

Таблица 2.

Сырье	Продукция	Запасы сырья
	P1	P2
S1	2	3	28
S2	4	3	32
S3	8	4	55
Себестоимость, cj, ден. ед.	2	3
Оптовая цена, pj, ден. ед.	5	7

Решение

Пусть x₁, x₂, - количество продукции вида P₁ и P₂. Тогда будет израсходовано сырья S₁: x₁+x₂, сырья S₂: x₂, сырья S₃: x₁. С учетом запасов сырья, система ограничений будет иметь следующий вид



Целевая функция (прибыль) будет иметь вид

,

или, учитывая данные таблицы,

F = 3x₁ + 4x₂. (13)

Таким образом, математическая модель задачи формулируется следующим образом:

Требуется найти такой план выпуска продукции X=(x₁, x₂, x₃), удовлетворяющий системе (11) и условиям (12), при которых целевая функция (13) принимает максимальное значение.



Построим многоугольник решений (см. рис. 1). Для этого на плоскости в системе координат x₁Ox₂ изобразим граничные прямые: (I) 2x₁+3x₂=28, (II) 4x₁+3x₂=32, (III) 8x₁+4x₂=55. С учетом условий (12), многоугольник решений будет иметь вид фигуры, заштрихованной на рис. 1. Далее строим линии уровня целевой функции (13). При F=0 линия уровня проходит через начало координат. Затем, например, построим линию уровня F=4, т.е. 3x₁+4x₂=4. Ее расположение указывает на направление возрастания целевой функции (градиент целевой функции, вектор ). Двигая линию уровня, т.е. прямую, целевой функции в направлении вектора , найдем ее самое крайнее положение, при котором она проходит через точку B. Таким образом, оптимальное решение задачи будет находиться в угловой точке B, находящейся на пересечении прямых (I) и (II), т.е. координаты точки B определяются решение системы уравнений

Отсюда находим, что x₁=2, x₂=8, т.е. B(2;8). Максимальное значение целевой функции равно F_max=3Ч2+4Ч8=38.

Итак, F_max=38 при оптимальном решении x₁=2, x₂=8, т.е. максимальная прибыль в 38 ден. ед. может быть достигнута при производстве 2 ед. продукции П₁ и производстве 8 ед. продукции П₂.

Отметим, что при найденном оптимальном плане, сырье S₁ и S₂ расходуются полностью.

Можно ли произвести 3 ед. продукции P₁ и 2 ед. продукции P₂? Да, можно. Поскольку при x₁=3 и x₂=2 все три неравенства выполняются



то такой план является допустимым, но не является оптимальным. На графике (см. рис.1) предложенному плану соответствует точка E(3;2), которая входит в многоугольник допустимых решений, но отличается от оптимального решения, т.е. от точки B.

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

Условие задачи №3

Задача о выборе оптимальных технологий

На предприятии выпускается n видов P_j (j=1, 2,…, n). При ее изготовлении используются ресурсы R₁, R₂, R₃, размеры допустимых затрат ресурсов ограничены величинами b₁, b₂, b₃. Расход ресурса R_i (i=1,2,3) на производство единицы продукции P_j равен a_ij. Прибыль от реализации единицы продукции P_j равна c_j ден. ед.

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

Задание

1. Записать математическую модель задачи.

2. Привести модель к каноническому виду и заполнить симплексную таблицу.

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

4. Дать экономическое истолкование оптимального решения X_опт и наибольшего значения целевой функции f_наиб(X_опт).

Решение

Исходные данные запишем в виде таблицы

Таблица 3

Сырье	Продукция	Запасы сырья
	P1	P2	P3
R1	15	20	25	1200
R2	2	3	2,5	150
R3	35	60	60	3000
Прибыль от реализации единицы продукции, cj, ден. ед.	300	250	450

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

Требуется найти такой план выпуска продукции X=(x₁, x₂, x₃), удовлетворяющий системе

(14)

и условиям

x₁ ? 0, x₂ ? 0, x₃ ? 0,

при которых целевая функция



F = 300x₁ + 250x₂ + 450x₃

принимает максимальное значение.

F = 300x₁ + 250x₂ + 450x₃ max

Перейдем к каноническому виду системы ограничений:

Перепишем систему ограничений в векторной форме:

A₁x₁ + A₂x₂ + A₃x₃ + A₄x₄ + A₅x₅ + A₆x₆ = B

Где

За базис векторов выбираем систему векторов A₄, A₅, A₆, т.к. эти векторы единичные и линейно независимые. Другими словами, в качестве базисных векторов выбираем переменные x₄, x₅, x₆. Приравняв нулю свободные переменные x₁=x₂=x₃=0, получим первоначальный опорный план:



X₀ = (0; 0; 0; 1200; 150; 3000).

Для проверки на оптимальность этого опорного плана составим первую симплекс-таблицу:

Таблица 4

Оценочная строка вычисляется следующим образом: F₀=C_бB=0, D₁=C_бA₁-c₁=-300, D₂=C_бA₂-c₂=-250, D₃=C_бA₃-c₃=-450. Для базисных векторов оценки равны нулю.

Поскольку все оценки D_j отрицательные, следовательно, первоначальный план не является оптимальным. В качестве разрешающего элемента выберем число 25, стоящее на перекрестке третьего столбца (в этом столбце самая маленькая оценка, -450) и первой строки (здесь 1200/25<150/2,5<3000/60). Это означает, что вектор A₃ нужно включить в базис, а вектор A₄ исключить. Составим новую симплекс-таблицу. Для этого все элементы разрешающей строки разделим на 25 и с помощью этой строки получим нули в разрешающем столбце, т.е. прибавим первую преобразованную стоку ко второй, предварительно умножив ее на -2,5, прибавим первую преобразованную стоку к третьей, предварительно умножив ее на -60, и т.д.



Таблица 5

Во второй симплекс-таблице получен новый опорный план:

X₁ = (0; 0; 48; 0; 30; 120),

Которому соответствует новое значение целевой функции F₁=F(X₁)=21600. Однако в последней строке есть отрицательная оценка, следовательно, полученный опорный план не является еще оптимальным.

Преобразуем симплекс-таблицу еще раз. Для этого в качестве разрешающего элемента возьмем число 0,5, стоящее на перекрестке первого столбца (в этом столбце находится отрицательная оценка) и второй строки (здесь 30/0,5<48/0,6, -1 не учитываем). Таким образом, вектор A₅ исключается из базиса, а вектор A₁ включается. Составляем третью симплекс-таблицу.

Таблица 6

Итак, в последней строке все оценки положительные. Следовательно, опорный план



X₂ = (60; 0; 12; 0; 0; 180),

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

F_max=F(X₂)=23400.

Таким образом, для того чтобы предприятию получить максимальную прибыль нужно выпускать 60 ед. продукции П₁ и 12 ед. продукции П₃, а продукцию П₂ вообще не выпускать. При таком плане ресурсы R₁ и R₂ будут реализовываться полностью, а ресурс R₃ будет реализовываться не полностью, здесь будет оставаться остаток 180 ед. При осуществлении такого плана, предприятие получит наибольшую прибыль в размере 23400 ден. ед.

4. Двойственные задачи

математический линейный программирование

Условие задачи №4

Для задачи о выборе оптимальных технологий (см. задачу №3) требуется:

1. Сформулировать в экономических терминах двойственную задачу.

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

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

4. Дать экономическое истолкование величине T_min, значениям основных и дополнительных переменных в оптимальном решении Y_опт двойственной задачи. Указать наиболее дефицитный и недефицитный (избыточный) ресурсы, если они имеются.

5. Пусть ресурсы взаимозаменяемы и из производства исключается Db₁=2 единицы ресурса R₁. Определить на сколько может уменьшиться максимальный доход (величина D₁f_max). Найти, сколько единиц ресурсов R₂ и R₃ нужно ввести дополнительно в производство, чтобы компенсировать возможный убыток.

Решение

Двойственную задачу можно сформулировать следующим образом. Найти такой набор цен ресурсов Y, при котором общие затраты на ресурсы будут минимальными, при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции.

Составим математическую модель двойственной задачи. Выпишем расширенную матрицу системы, в которую включим основную матрицу системы A, столбец свободных членов B и строку коэффициентов целевой функции C:

Транспонируем матрицу A₁:

Сформулируем двойственную задачу на основании полученной матрицы и условия неотрицательности переменных. Найти такой набор цен ресурсов Y=(y₁,y₂,y₃), при котором общие затраты на ресурсы (целевая функция) будут минимальными

T = 1200y₁ + 150y₂ + 3000y₃,

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

Если прямая ЗЛП имеет оптимальный план X, то Y=C_бD-¹ является оптимальным планом двойственной задачи. Здесь C_б=(c₁,c₂,…,c_r) - вектор-строка, составленная из коэффициентов при базисных переменных целевой функции; D-¹ - матрица, обратная матрице D, составленной из компонент векторов A₁, A₂,…,A_r. таким образом. если найти симплекс-методом оптимальный план прямой задачи, то зная C_б и D-¹ можно найти оптимальный план двойственной задачи. Для определения C_б и D-¹ можно использовать последнюю симплекс-таблицу. Более тог, по этой таблице можно сразу определить произведение C_бD-¹, поскольку компоненты этого плана совпадают с соответствующими элементами последней оценочной строки плюс c_j, т.е. y_j=D_j+c_j.

В последней симплекс-таблице задачи №3 базисом являются векторы A₁, A₃, A₆, тогда по первой симплекс-таблице находим



Обратная матрица D-1 образуется из коэффициентов последней симплекс-таблице, стоящих в столбцах A₄, A5₆, A₆ (являющихся единичными в исходной симплекс-таблице):

Поскольку, в соответствие с симплекс-таблицей, C_б=(300; 450; 0), то

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

В соответствии с первой теоремой двойственности, если одна из пары двойственных задач обладает оптимальным планом, то и другая обладает оптимальным планом, причем F_max=T_min. В нашем случае

T_min = F_max = 23400

т.е. общие затраты на ресурсы при производстве каждого вида продукции при оптимальном плане совпадает прибылью от реализации этой продукции.

Сырье R₁ и R₂ по оптимальному плану полностью использовано () и объективно обусловленные оценки этого сырья ненулевые (), а сырье R₃ использовано не полностью используется в оптимальном плане () и объективно обусловленная оценка этого сырья нулевая ().

Таким образом, сырье R₁ и R₂ будет дефицитным (т.е. полностью используемым). При этом сырье R₂ будет наиболее дефицитным, т.к. ее оценка самая высокая. Сырье R₃ будет не дефицитным и поэтому ее оценка равна нулю.

Дополнительные переменные двойственной задачи y₄, y₅, y₆, представляют разность между затратами на сырье для производства из них единицы продукции и ценами c_j продукции P_j. По оптимальному плану в исходной задаче следует производить только продукцию P₁ и P₃ () и превышение затрат на сырье над ценой реализации равно нулю, т.е. дополнительные переменные .

Если из производства исключается Db₁=2 единиц продукции R₁, то максимальный доход уменьшится на величину

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

единиц ресурса R₂.

Размещено на Allbest.ru