Типовой расчет №1 «Линейное программирование» (стр. 1 )

Типовой расчет №1 «Линейное программирование»

Задача 1

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

Тип сырья	Нормы расхода сырья на 1 т. пряжи	Количество сырья (т.)
Вид 1	Вид 2
Шерсть	0,5	0,2	600
Капрон	a	0,6	b
Акрил	0,5-a	0,2	c
Прибыль (руб./т.)	1100	900

Составить по этим данным задачу линейного программирования. Графическим методом найти оптимальный план производства пряжи. Решить симплекс-методом. Вариант 7: a=0,1; b=790; c=520. Таблица:

Тип сырья	Нормы расхода сырья на 1 т. пряжи	Количество сырья (т.)
Вид 1	Вид 2
Шерсть	0,5	0,2	600
Капрон	0,1	0,6	790
Акрил	0,4	0,2	520
Прибыль (руб./т.)	1100	900

Обозначим план выпуска первого вида пряжи через x1, а второго через x2.

С учетом количества сырья и норм расхода на выпуск получаем систему ограничений:

Тогда целевая функция-функция прибыли должна быть максимизирована и равна:

Получаем математическую модель задачи:

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

Построим прямые, соответствующие ограничениям

L1	X1	0	1200
X2	3000	0

L2	X1	0	7900
X2	1317	0

L3	X1	0	1300
X2	2600	0

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

Наискорейшее возрастание функции происходит в направлении вектора её градиента (1100; 900), т. е. линии уровня будем перемещаем перпендикулярно направлению вектора (1100; 900). Построим график целевой функции

L: 1100x1+900x2=0

L	X1	0	900
X2	0	-1100

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

В этой точке M (800;1000) целевая функция будет достигать максимума , что равно прибыли полученной при этом плане производства.

Оптимальный план производства, полученный графически, X=(800;1000), Fmax(x1,x2)=1 780 000.

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

при условиях:

Составим симплекс-таблицу. У нас получилось три единичных вектора. Получили базис из векторов А3, А4, А5, запишем эти вектора в базисный столбец, в следующий столбец запишем коэффициенты перед соответствующими переменными целевой функции. Соответственно в системе уравнений x3, x4, x5 - базисные переменные, а x1, x2 – свободные переменные. Получаем симплексную таблицу для первой итерации.

i	Баз.	С баз.	А0	1100	900	0	0	0
A1	A2	A3	A4	A5
1	А3	0	600	0,5	0,2	1	0	0
2	А4	0	790	0,1	0,6	0	1	0
3	А5	0	520	0,4	0,2	0	0	1
4			F0=0	∆1=-1100	∆2=-900	∆3=0	∆4=0	∆5=0

Вычислив оценки ∆i, получаем, что среди оценок есть отрицательные, значит, план X1=(0;0;600;790;520) не является оптимальным для задачи на максимум. Наибольшая по абсолютному значению отрицательная оценка это первая. В первом столбце есть положительные элементы, значит, примем его за разрешающий.

Наименьшее отношение соответствует первой строке, значит, выберем первую строку в качестве разрешающей. Разрешающий элемент равен 0,5, выделим его в таблице цветом. Вектор A1 введем в базис вместо А3. Для получения новой таблицы разрешающую строку делим на разрешающий элемент, разрешающий столбец заполняем нулями, за исключением разрешающего элемента (получаем единичный вектор). Остальные элементы новой таблицы получаем методом Жордана-Гаусса, т. е. по правилу прямоугольника. Получаем таблицу:

i	Баз.	С баз.	А0	1100	900	0	0	0
A1	A2	A3	A4	A5
1	А1	1100	1200	1	0,4	2	0	0
2	А4	0	670	0	0,56	-0,2	1	0
3	А5	0	40	0	0,04	-0,8	0	1
4			F0=1320000	∆1=0	∆2=-460	∆3=2200	∆4=0	∆5=0

Вычислив оценки ∆i, получаем, что среди оценок есть отрицательные, значит, план X2=(1200; 0;0;670;40) не является оптимальным для задачи на максимум. Вторая оценка отрицательная, в столбце A2 есть положительные элементы, значит, этот столбец можем принять за разрешающий.

Наименьшее отношение соответствует третьей строке, значит, выберем третью строку в качестве разрешающей. Разрешающий элемент равен 0,04, выделим его в таблице цветом. Вектор A2 введем в базис вместо А5. Для получения новой таблицы разрешающую строку делим на разрешающий элемент, разрешающий столбец заполняем нулями, за исключением разрешающего элемента (получаем единичный вектор). Остальные элементы новой таблицы получаем методом Жордана-Гаусса, т. е. по правилу прямоугольника. Получаем таблицу:

i	Баз.	С баз.	А0	1100	900	0	0	0
A1	A2	A3	A4	A5
1	А1	1100	800	1	0	10	0	10
2	А4	0	110	0	0	11	1	14
3	А2	900	1000	0	1	20	0	25
4			F0=1780000	∆1=0	∆2=0	∆3=29000	∆4=0	∆5=335000

Получили базисные вектора А1, A4, А2. Среди оценок нет отрицательных, значит найдено оптимальное решение на максимум. X3=(800; 1000;0;110;0) и Fmax=1 780 000. Присутствие x4=110, говорит о том, что запасы второго типа сырья (капрон) будут недоиспользованы на 110 тонн.