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

21 вариант

 

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

 

Для изготовления двух видов продукции используется три вида сырья. При производстве единицы продукции первого вида затрачивается 4 кг сырья первого вида, 7 кг сырья второго вида и 6 кг третьего вида. При производстве единицы продукции второго вида затрачивается 3 кг сырья первого вида, 5 сырья второго вида и 3 кг сырья третьего вида. Запасы сырья первого вида составляют 552 кг, второго - 607, третьего – 476 кг. Прибыль от реализации единицы продукции первого вида составляют 3 руб, а прибыль от реализации единицы продукции второго вида 6 руб. Построить экономико-математическую модель задачи, максимизирующую прибыль от реализации продукции. Решить задачу геометрически. Построить двойственную задачу и найти ее решение на основе теорем двойственности. Провести содержательный экономический анализ полученных результатов.

 

Решение.

 

Рассмотрим экономико-математическую модель. Если за взять количество изделий первого вида, а за количество изделий 2 вида, то получим задачу линейного программирования.

Найти максимум линейной функции:

При ограничениях:

Граничные условия:

Геометрическое решение задачи.

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

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

	0	138
	184	0

 

	0	86,7
	121,4	0

 

 

	0	79,3
	158,7	0

 

 

 

В пересечении соответствующих полуплоскостей получим пятиугольник ABCD. Для нахождения max F построим из начала координат вектор и перпендикулярно ему линию уровня , то есть прямую . Наибольшее значение получаем в вершине B.

Вершина B – это точка пересечения прямых и .

Находим координаты точки B из системы:

 

 

Решая систему, найдем что

Подставим в целевую функцию:

 

руб.

 

Для получения максимальной прибыли в объеме 728,4 руб. необходимо выпустить 0 ед. первого вида продукции и 121,4 ед. второго вида продукции.

 

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

 

Составим задачу двойственную следующей задаче:

При ограничениях:

Граничные условия:

Решение для прямой задачи:

Составляем двойственную задачу:

При ограничениях:

Решение двойственной задачи:

1) существование решения:

2)

первое условие двойственной задачи выполняется как равенство;

 второе условие двойственной задачи выполняется как равенство.

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

 

Из графического решения исходной задачи, видно, что прямая не проходит через точку B оптимального решения. Поэтому первое ограничение исходной задачи выполняется в виде строгого неравенства. По второй теореме двойственности, соответствующая двойственная оценка и равны 0. Подставив и в систему получим:

 

Решив систему находим: , и следовательно:

Как видим,

второй ресурс дефицитный.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2  Транспортная задача

 

Заданы объемы запасов в пунктах производства, объемы потребностей в пунктах потребления и матрица транспортных издержек по перевозке единицы груза из пункта производства в пункт потребления. Требуется найти оптимальный план перевозок. Построить математическую модель транспортной задачи. Решить задачу, найдя первоначальное распределение поставок одним из методов (методом «наименьших элементов» или методом северо-западного угла) и провести анализ полученного решения.

 

Поставщики	Потребители					Запас
	B1	B2	B3	B4	B5
A1	11	7	20	3	15	225
A2	12	3	14	10	20	250
A3	18	15	25	11	15	125
Потребности	150	110	135	85	120	600

 

Решение.

Составим математическую модель транспортной задачи:

Ограничения:

1) Следовательно:

 

таким образом, задача является закрытой.

2) Найдем первоначальное распределение  методом «наименьших элементов».

 

	B1	B2	B3	B4	B5	Запас
A1	11 140	7 -	20 -	3  85	15 -	225/140/0
A2	12      - 10	3 110	14         + 130	10 -	20 -	250/140/130/0
A3	18      + -	15 -	25         - 5	11 -	15 120	125/5/0
Потребности	150/10/0	110/0	135/5/0	85/0	120/0	600

 

 

4) Проверим план на оптимальность:

 

 

таким образом, из уравнений определим потенциалы потребителей и производителей:

 

 

Определим оценки свободных клеток, для того чтобы план был оптимальным, необходимо, чтобы выполнялось условие: .

Оценки:

 

 

Существует, план необходимо оптимизировать.

Перераспределение перевозки:

 

	B1	B2	B3	B4	B5
A1	11 140	7 -	20 -	3  85	15 -
A2	12      5	3 110	14         135	10 -	20 -
A3	18      5	15 -	25         0	11 -	15 120

 

min(3;3)=5

 

Оценки:

 

 

Найденный на 2 этапе план является оптимальным, так как, все , то план является оптимальным.

 

 

Суммарные затраты на перевозку:

 

руб.

 

 

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

 

Предпочтения потребителя описываются функцией полезности  , доход равен 400, а цены товаров p=(8, 10). Полагая, что поведение потребителя рационально (то есть он выбирает такие количества каждого блага из товарного набора, которые позволяют ему максимально удовлетворить свои потребности при наличии ограниченного дохода) требуется: определить оптимальный набор товаров, который выберет потребитель при фиксированном доходе и заданном векторе цен, а также достигнутый уровень полезности.

Построить экономико-математическую модель, решить задачу методом множителей Лагранжа.

 

Решение.

 

Построим математическую модель задачи потребительского выбора:

 

 

1) Построим функцию Лагранжа:

Найдем частные производные:

 

Приравняем данные выражения к 0.

 

    

 

Разделим 1 уравнение на 2 уравнение, таким образом, получаем:

 таким образом, получаем

 

Подставим результаты в целевую функцию:

 

.

 

Ответ: