Математическая экономика

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

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

риальными или задачами векторной оптимизации. Довольно часто их сводят к однокритериальным задачам, выбрав один критерий в качестве оптимального (например прибыль), а на остальные показатели накладывают ограничения – «не более чем…» или «не менее чем…». Однако существуют и специальные подходы к анализу задач векторной оптимизации (см. например [27]).

До сих пор нами предполагалось, что все исходные данные, фигурирующие в задаче, например, нормы расхода материалов, удельная доходность от реализации продукции и т.д., однозначно определены и известны. Эти задачи называют детерминированными. Однако на практике такие ситуации встречаются далеко не всегда. Зачастую в формулировке задачи подобной четкой определенности нет. Многие исходные условия оказываются неопределенными, например, спрос на продукцию, которая запланирована к выпуску. Такие задачи называются задачами с неопределенностями. При их формализации и анализе используют специальные подходы, в частности вероятностно-статистические, интервальные и нечеткие модели [9, 11, 18].

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

21

Контрольные вопросы

1.Какие действия необходимо осуществить для перехода от содержательной постановки задачи к математической модели?

2.В чем состоит задача статической оптимизации, каковы особенности задач динамической оптимизации?

3.Что такое целевая функция, какую роль она играет в оптимизационной задаче?

4.Как формулируется задача безусловной оптимизации?

5.Как формулируется задача условной оптимизации?

6.Как формулируется задача математического программирования?

7.Какой смысл имеет термин «программирование» в теории оптимизации?

8.В чем состоит сущность задач векторной оптимизации?

9.Какими особенностями обладают детерминированные задачи оптимизации?

10.Какие подходы используются при формализации и анализе оптимизационных задач с неопределенностями?

Задачи для самостоятельного решения

Требуется формализовать приведенные ниже задачи и определить их

тип.

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

2.Из всех треугольников данного периметра p найти тот, который имеет наибольшую площадь.

3.Из проволоки заданной длины l необходимо изготовить равносторонний треугольник и квадрат. Требуется найти такие размеры этих фигур, чтобы их суммарная площадь была максимальна.

4.Малое предприятие изготавливает два вида красок: для внутренних K1 и наружных K2 работ. Продукция обоих видов поступает в опто-

вую продажу. Для производства этих красок используются два исходных продукта П1 и П2 , их максимально возможные суточные запасы со-

22

одной минутой радиорекламы. Определить оптимальное распределение средств между радио- и телерекламой.

8. На предприятии изготавливаются изделия двух видов. Процесс изготовления каждого из них осуществляется последовательно в трех цехах. Время обработки и прибыль от продажи одного изделия каждого вида приведены в табл. 1.3. Рабочее время составляет 8 ч в сутки. Найти оптимальные объемы производства изделий каждого вида.

9. Формализовать задачу об оптимальном составе смеси. В ней требуется определить такие концентрации веществ в смеси, чтобы стоимость смеси была минимальна, а показатели, оценивающие ее свойства (плотность, прочность, теплоемкость и т.п.), были не меньше заданных значений. Примером такой задачи может служить задача об оптимальной диете (рационе). При откормке животных каждое из них ежедневно должно получить не менее 60 ед. питательного вещества А, не менее 50 ед. вещества В и не менее 12 ед. вещества С. Использоваться могут три вида корма. Содержание питательных веществ в каждом из них задается в табл. 1.4.

Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах, если цена кормов 1-го, 2-го и 3-го видов составляет соответственно 9, 12 и 10 у.е.

10. Для производства чугунного литья используется n различных исходных шихтовых материалов (чугун различных марок, стальной лом,

24

феррофосфор и др.). Химический состав чугунного литья определяется содержанием в нем химических элементов (кремния, марганца, фосфора и др.). Готовый чугун должен иметь строго определенный химический состав, который задается величинами H j , представляющими собой доли (%)

j-го химического элемента в готовом продукте. При этом известны величины: hij – содержание (%) j-го химического элемента в i-м исходном

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

11. Имеются заготовки в виде листов материала определенного размера. Из них нужно накроить детали четырех видов: А – 6 шт., Б – 15 шт., В – 25 шт., Г – 10 шт. Известны три способа раскроя заготовки. Количество деталей каждого вида, получаемых при этих способах раскроя, приведено в табл. 1.5.

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

12. Имеется n = 2 предприятий А1и А2 , в которых производится однородная продукция. Количество ежедневно производимой продукции в

найти оптимальный план перевозок, определяющий количество продукции, перевозимой из пункта Аi в пункт B j (i = 1,2; j = 1,..., 4). Этот план

25

должен обеспечивать минимальные общие затраты на перевозки. При

Примечание. В рассматриваемой задаче объем производства равен

объему потребления∑ai = ∑вj , т.е. система «производство – потребле- i j

ние» сбалансирована. В противном случае продукция либо «затоварилась» бы в пунктах потребления, либо возникал дефицит в ней.

Пусть xij – количество единиц продукции, перевозимой из Аi в B j .

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

2 4

y = ∑∑cij xij , i =1 j =1

где cij – стоимости из табл. 1.6.

y = 2,3x11 + 4,7x12 +1,8x13 +1,1x14 +3,7x21 + 4,6x22 +8,2x23 +12,3x24. (1.12)

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

26

Таким образом, данная задача сводится к отысканию nm переменных xi j ≥0, при которых выполняется система из n+m ограничений-равенств

(1.13), а целевая функция (1.12) принимает наименьшее значение. Эта задача является задачей линейного программирования, причем она имеет существенную особенность: все переменные xi j входят в ограничения-

равенства с единичными коэффициентами. Заметим, что в отличие от предыдущих задач при формализации рассмотренной транспортной задачи оказалось удобным использовать обозначение искомых величин в виде переменных с двойной индексацией, хотя можно было использовать и одноиндексные переменные xk (k =1,..., nm) .

13. Задача о назначениях (о распределении работ). В цехе имеется два участка А1 и А2 по контролю и настройке производимой электронной аппаратуры четырех разновидностей: B1,..., B4 . Известно, что оборудование участков и квалификация работающих там специалистов таковы, что на участке Аi на наладку одного изделия вида B j требуется время Cij (ч)

(табл. 1.7).

Поступило задание: провести настройку 7 изделий вида B1 , 10 изделий – B2 , 14 изделий – B3 и 9 изделий – B4 . Как распределить эти изделия по участкам, чтобы общие затраты времени на их настройку были минимальными?

27

Глава 2. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

§ 2.1. Общая и каноническая задачи линейного программирования

Как указывалось в § 1.2, оптимизационную задачу называют задачей линейного программирования (ЛП), если она состоит в отыскании значений переменных x1,..., xn , при которых целевая функция, являющаяся ли-

нейной формой этих переменных:

принимает наименьшее (или наибольшее) значение и выполняется система линейных ограничений-равенств:

но они легко сводятся к виду (2.3) умножением обеих частей неравенства на (–1).

Примечание 2. Из физического смысла переменных, фигурирующих в задаче, довольно часто следует, что все либо часть этих переменных должны быть неотрицательны (см. пример 3 из § 1.1). Это приводит к по-

хотя ясно, что они непосредственно вписываются в систему ограничений

(2.3).

Выделим частный случай сформулированной общей задачи ЛП, в которой находятся наименьшее значение линейной целевой функции (2.1) при выполнении системы ограничений-равенств (2.2) и требования неотрицательности всех переменных. Такая задача называется канонической задачей линейного программирования (КЗЛП) [1, 26], или основной (ОЗЛП) [6, 26], или стандартной [32].

28

быть неотрицательны).

Общая задача ЛП отличается от канонической тем, что в ней может находиться как наименьшее, так и наибольшее значение целевой функции, а среди ограничений-неравенств кроме простейших условий xi ≥ 0 могут

присутствовать неравенства, в которые входят несколько переменных, например, 2x1 + x2 − x3 + 4x5 ≥10. В теории ЛП рассматривается главным

образом более простая КЗЛП. При этом учитывается то, что общую задачу ЛП всегда можно свести к канонической.

Если необходимо найти наибольшее значение целевой функции y, то для сведения этой задачи к канонической следует перейти к вспомогатель-

ной функции y = −y . Ясно, что при этом наименьшему значению ~y будет

соответствовать наибольшее значение y и наоборот.

Допустим, что при формализации конкретной практической задачи

соответствующие условиям канонической задачи.

Пример. Формализация задачи 14 о планировании производства из § 1.3 приводит к следующей задаче ЛП: найти неотрицательные значения x1 и x2 , при которых целевая функция, выражающая прибыль предпри-

ятия от реализации продукции

будет наибольшей при наличии ограничений, выражаемых системой неравенств:

29

Требуется свести эту задачу к КЗЛП.

Решение. Преобразуем каждое из неравенств системы (2.11) к виду

Преобразуя эту систему к стандартному виду (2.2), т.е. перенося все члены уравнений, содержащие переменные xi , в левую часть, а свободные

члены – в правую, вместо исходной системы неравенств (2.11) получаем систему уравнений

получаем вместо исходной задачи об отыскании наибольшего значения функции (2.10) при выполнении неравенств (2.11) каноническую задачу об отыскании наименьшего значения функции (2.16) при выполнении системы линейных алгебраических уравнений (2.15) и требовании неотрица-

тельности всех переменных xi (i =1,6).

Будем в дальнейшем рассматривать задачи ЛП в канонической форме, считая, что в том случае, когда исходная задача окажется сформулированной в общем виде, она указанным выше образом будет сведена в КЗЛП.

Отметим, что каждый набор переменных ( x1,..., xn ), удовлетворяющий системе ограничений (2.2) и требованию неотрицательности xi ≥ 0 (i =1,..., n ), называется допустимым решением рассматриваемой задачи ЛП, а множество всех таких наборов называется областью допустимых решений (ОДР). Ясно, что для осуществления решения задачи ЛП необходимо (хотя и не достаточно), чтобы ОДР не была пустым множеством, а для этого нужно прежде всего, чтобы система уравнений (2.2) была совместна. Для этого (в соответствии с теоремой Кронекера – Капелли [17]) не-

30