Некоторые задачи оптимизации в экономике (стр. 5 из 12)

Решение. х₁- количество выпускаемых изделий А

х₂- количество выпускаемых изделий В

х₃- количество выпускаемых изделий С.

Тогда целевая функция будет иметь вид: F=10x₁+14x₂+12 х₃ →max

при ограничениях: 4x₁+2x₂+х₃≤180

3x₁+x₂+3х₃≤210

x₁+2x₂+5х₃≤236

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

4x₁+2x₂+х₃+х₄=180

3x₁+x₂+3х₃+х₅=210

x₁+2x₂+5х₃+х₆=236.

Составляем таблицу

х1	х2	х3	х4	х5	х6	Свободныйчлен
х4 х5 х6	4 3 1	2 1 2	1 3 5	1 0 0	0 1 0	0 0 1	180 210 236
F’	-10	-14	-12	0	0	0	0

Определим ведущий элемент: min

. Далее выполняем действия, следуя алгоритму.

х1	х2	х3	х4	х5	х6	Свободныйчлен
х2 х5 х6	2 1 -3	1 0 0	1/2 5/2 4	1/2 -1/2 -1	0 1 0	0 0 1	90 120 56
F’	18	0	-5	7	0	0	1260

min

х1	х2	х3	х4	х5	х6	Свободныйчлен
х2 х5 х3	19/8 23/8 -3/4	1 0 0	0 0 1	5/8 1/8 -1/4	0 1 0	-1/8 -5/8 1/4	83 85 14
F’	54/4	0	0	23/4	0	5/4	1330

Ответ: Чтобы получить оптимальный доход, нужно выпускать 83 ед. изделия В, 14 ед. изделия С, а изделие А не выпускать. Оптимальный доход составит 1330 у.е. По решению задачи видим, что у предприятия остаются свободными 85 кг. второго вида ресурсов, 1 и 3 вид полностью расходуются [5]

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

Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряжённой по отношению к исходной. Теория двойственности полезна для проведения качественных исследований ЗЛП. В главе I пункте 2) рассмотрена

задача об использовании ресурсов. Предположим, что некоторая организация решила закупить ресурсы и необходимо установить оптимальные цены на эти ресурсы y_1,y₂,y₃. Очевидно, что

покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах 180, 210, 236 по ценам соответственно y_1,y₂,y₃были минимальными, т.е. Z= 180y₁+210y₂+236y₃→min. С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не мене той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции А расходуется 4кг. ресурса 1, 3кг. ресурса 2, 1кг. ресурса 3 по цене соответственно y_1,y₂,y₃. Поэтому, для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции, должны быть не менее её цены 10у.е., т.е. 4 y₁+3 y₂+ y₃≥10.

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

Задача I (исходная)

Задача II (двойственная)

F= 10x1+14x2+12x3→max При ограничениях: 4х1+2х2+х3≤180 3х1+х2+3х3≤210 х1+2х2+5х3≤236и условие неотрицательности переменных x1≥0, x2≥0, х3≥0.Для производства трёх изделий А, В, С используются три вида сырья. каждый из них используется в объёме, не превышающем 180, 210 и 236кг. Определить план выпуска изделий, обеспечивающий получение оптимального дохода при условии, что потребление ресурсов по каждому виду продукции не превзойдёт имеющихся запасов.

Z= 180y1+210y2+236y3→minПри ограничениях: 4y1+3y2+y3≥10 2y1+y2+2y3≥14y1+3y2+5y3≥12и условие неотрицательности переменных y1≥0, у2≥0, у3≥0.Найти такой набор цен ресурсов, при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли от реализации этой продукции.

Обе задачи, представленные в таблице обладают следующими свойствами:

1. В одной задаче ищут максимум линейной функции, в другой минимум.

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

3. Каждая из задач задана в стандартной форме, причём в задаче максимизации – все неравенства вида «≤», а в задаче минимизации – все неравенства вида «≥».

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

Для задачи I А=

, для задачи II А =

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6. Условия неотрицательности переменных имеются в обеих задачах.

Две задачи Iи II линейного программирования, обладающие указанными свойствами, называются симметричными взаимодвойственными задачами.

Исходя из определения, можно предложить следующий алгоритм составления двойственной задачи.

1. Приводят все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задач ищут максимум линейной функции, то все неравенства системы ограничений приводят к виду «≤», а если минимум – к виду «≥».

2. Составляют расширенную матрицу системы А₁, в которую включают матрицу коэффициентов при переменных, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

3. Находят матрицу А

, транспонированную к матрице А₁.