Конспект_лекц_Кишкурно

ЛЕКЦИЯ 10

РЕШЕНИЕ ИНЖЕНЕРНО-ЭКОНОМИЧЕСКИХ ЗАДАЧ НА БАЗЕ MATHCAD

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

Общей задачей линейного программирования называется задача,

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

где aij , bi , cj – заданные постоянные величины.

Функция (1) называется целевой функцией (или линейной формой) за-

дачи (1)–(3), а условия (2)−(3) – ограничениями данной задачи. Совокупность чисел X = (x1, x2, …, xn), удовлетворяющих огра-

ничениям задачи (2)–(3), называется допустимым решением (или

планом).

План X* = (x1*, x2*, …, xn*), при котором целевая функция задачи (1) принимает свое максимальное (минимальное) значение, называ-

ется оптимальным.

В пакете MathCAD для поиска экстремума функции многих переменных y = f (x1, x2, , xn ) имеются встроенные функции Minimize и

Maximize. С помощью этих функций решается задача поиска ло-

81

Общая прибыль от реализации x1 изделий вида А и x2 изделий вида В составит: F = 30x1 + 40x2. Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений требуется найти такое, при котором функция принимает максимальное значение.

Для поиска экстремума функции в пакете MathCAD необходимо использовать блок Given, как показано ниже.

Запишем целевую функцию:

Чтобы получить максимальную прибыль 1080 усл. ед., необходимо произвести изделия А (х1) 12 шт., изделия В (х2) – 18 шт.

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

Цех предприятия должен изготовить 100 изделий трех типов (табл. 10.2). Каждого изделия нужно не менее 20 штук. На изделие уходит соответственно 4, 5 и 2 кг однородного металла при его общем запасе 340 кг, а также по 5, 9 и 2 кг пластмассы при ее общем запасе 700 кг. Сколько изделий каждого типа надо выпустить для получения максимального объема в денежном выражении, если цена изделия составляет по калькуляции 4, 3 и 2 усл. ед.?

Данная производственная задача тоже сводится к задаче вычисления максимума функции с ограничениями.

83

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через сij тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через аi – запасы груза в i-м пункте отправления, через bj – потребности в грузе в j-м пункте назначения, а через xij – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

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

План, при котором целевая функция F принимает свое мини-

мальное значение, называется оптимальным планом транспорт-

ной задачи. Обычно исходные данные транспортной задачи записывают в виде табл. 10.3. Очевидно, общее наличие груза у по-

пунктах назначения равна запасу груза в пунктах отправле ния,

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

85

Количество продукта у 1-го и 2-го поставщиков: a1:=40 a2:=50

Потребности потребителей 1-го, 2-го, 3-го: b1:=40 b2:=30 b3:=20

Общие затраты на перевозку (целевая функция):

f(x11,x12,x13,x21,x22,x23):=c11∙x11+c12∙x12+c13∙x13+c21∙x21+

+c22∙x22+c23∙x23

Начальные приближения:

x11:=40 x12:= 0 x13:=0 x21:=0 x22:=30 x23:=20

Блок решений и ограничений:

Given

Условие равенства вывозимого продукта запасам у 1-го и 2-го поставщиков:

x11+x12+x13═a1

x21+x22+x23═a2

Условие равенства доставленного продукта потребностям 1-го, 2-го и 3-го потребителей:

x11+x21═b1

x12+x22═b2

x13+x23═b3

Физический смысл транспортной задачи: x11≥0 x12≥0 x13≥0 x21≥0 x22≥0 x23≥0

Минимизация: c:=Minimize(f,x11,x12,x13,x21,x22,x23)

0

20

В результате мы получим вектор решений: c

20

40

10

0

87

пункта назначения В1, В2, В3, B4 соответственно в количествах 20, 25, 35 и 10 ед. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в следующей табл. 10.6. Составить план перевозок, обеспечивающий минимальную общую стоимость перевозок.

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

Тарифы – стоимости перевозки единицы продукта от трех поставщиков (Ai) четырем потребителям (Bj):

Общие затраты на перевозку (целевая функция):

2 3

f (x)

i 0 k 0

Начальное приближение:

20 10 0 0

0 0 10 10

Для решения задачи необходимо создать вспомогательную единичную матрицу:

89