Основы математики и ее приложения в экономическом образовании (стр. 39 )

Оценки свободных клеток:

Пределы изменения λ:

Оптимальное решение сохраняется при 7/5 ≤ λ ≤ 3. При этом L(X5)min = 1890 – 10λ. Итак,

УПРАЖНЕНИЯ

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

25.1. L() = -λx1 — х2 → min, 1 ≤ λ ≤ 11 при ограничениях:

25.2. L() = 5x1 + (2 + 3λ)x2 → max, 0 ≤ λ ≤ 10 при ограни­чениях:

25.3. L() = 2x1 + (3 + 4λ)x2 → max, - < λ < при ограничениях:

25.4. L() = (1 + λ)x1 + (2 - λ)x2 → min, -1 ≤ λ ≤ 4 при ограничениях:

25.5. L() = (3 + 3λ)x1 + 2x2 + (5 – 6λ)x3 → max, - < λ < при ограничениях:

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

25.6. Произвести транспортировку однородного груза с трех складов с объемами хранения 100, 200, 200 т соответствен­но пяти оптовым рынкам с потребностями 80, 70, 100, 150, 100 т соответственно. Стоимость транспортных расходов за­дана матрицей

причем стоимость перевозки груза со второго склада на чет­вертый рынок и с третьего склада на пятый рынок изменяется в некотором диапазоне 0 ≤ λ ≤ 2.

Определить план перевозок, обеспечивающий минималь­ные транспортные расходы в заданном диапазоне изменения параметра λ.

25.7. Имеются четыре поставщика однородного груза с объем­ами поставок 100, 70, 70, 20 т и три потребителя с объемами потребления 120, 80, 60 т. Cтоимость транспортных расходов задана матрицей

причем стоимость перевозки груза от четвертого поставщика до третьего потребителя изменяется в диапазоне 0 ≤ λ ≤ 9.

Определить оптимальный план перевозок, обеспечиваю­щий минимальные транспортные расходы.

26.1. Постановка задачи

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

Возможные применения задачи о назначениях представле­ны в табл. 26.1.

Матрица стоимостей С имеет вид

где cij — затраты, связанные с назначением i-го ресурса на j-й объект, i = j = , где п — число объектов или ресурсов.

Обозначим:

Таким образом, решение задачи может быть записано в ви­де Х = (xij).

Допустимое решение называется назначением. Оно строит­ся путем выбора ровно одного элемента в каждой строке мат­рицы X = (xij) и ровно одного элемента в каждом столбце этой матрицы.

Элементы cij матрицы С, соответствующие элементам xij = 1 матрицы X, будем отмечать кружками:

Математическая постановка задачи:

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

26.2. Алгоритм решения задачи

Задача о назначениях является частным случаем транспо­ртной задачи, в которой ai = bj = 1. Поэтому ее можно решать алгоритмами транспортной задачи. Рассмотрим другой метод, который является более эффективным, учитывающим специ­фику математической модели. Этот метод называется венгер­ским алгоритмом. Он состоит из следующих шагов:

1) преобразования строк и столбцов матрицы;

2) определение назначения;

3) модификация преобразованной матрицы.

1-й шаг. Цель данного шага — получение максимально воз­можного числа нулевых элементов в матрице С. Для этого из всех элементов каждой строки вычитаем ми­нимальный элемент соответствующей строки, а из всех элементов каждого столбца вычитаем минимальный эле­мент соответствующего столбца.

2-й шаг. Если после выполнения 1-го шага в каждой строке и каждом столбце матрицы С можно выбрать по одному нулевому элементу, то полученное решение будет опти­мальным назначением.

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

Если после проведения 3-го шага оптимальное решение не достигнуто, то процедуру проведения прямых следует повто­рять до тех пор, пока не будет получено допустимое решение.

Пример.

Распределить ресурсы по объектам.

Решение. 1-й шаг. Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вы­читая из элементов каждой строки соответствующее ми­нимальное значение, получим

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5, 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значе­ние, получим

2-й шаг. Ни одно полное назначение не получено, необходимо провести модификацию матрицы стоимостей.

3-й шаг. Вычеркиваем столбец 1, строку 3, строку 2 (или столбец 2). Значение минимального невычеркнутого эле­мента равно 2:

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

Ответ. Первый ресурс направляем на 3-й объект, вто­рой — на 2-й объект, четвертый — на 1-й объект, третий ре­сурс — на 4-й объект. Стоимость назначения: 9 + 4 + 11 + 4 = 28.

Примечания. 1. Если исходная матрица не является квад­ратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

2. Если какой-либо ресурс не может быть назначен на ка­кой-то объект, то соответствующая стоимость полагается рав­ной достаточно большому числу М.

3. Если исходная задача является задачей максимизации, то все элементы матрицы С следует умножить на (—1) и сло­жить их с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем задачу следу­ет решать как задачу минимизации.

4. Если число линий, необходимое для того, чтобы вы­черкнуть нулевые элементы, равно числу строк или столб­цов (квадратной матрицы), то существует назначение нулевой стоимости.

26.3. Планирование загрузки оборудования с учетом максимальной производительности станков

Рассмотрим следующую задачу.

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

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

Решение. Так как в задаче требуется определить max, a алгоритм метода дан для задач на min, умножим матрицу С на (—1). Сложим полученную матрицу, имеющую отрицатель­ные коэффициенты, с положительным числом, например с чис­лом 10. Получим

Минимальные элементы в строчках есть 3, 4, 4, 6, 4. Выч­тем их из соответствующих элементов матрицы, получим

Так как назначение не получено, вычеркиваем строку 2, столбцы 2, 4, 5:

Минимальный элемент равен 1. Вычитаем его из всех не­вычеркнутых элементов и складываем со всеми элементами, расположенными на пересечении двух линий. Получаем

Оптимальное решение, соответствующее последней матри­це, равно

Суммарная производительность: 6 + 6 + 3 + 6 + 7= 28.

Таким образом, на первом станке надо делать 5-ю опера­цию, на втором — 1-ю операцию, на третьем — 4-ю операцию, на четвертом — 3-ю операцию, на пятом станке — 2-ю опе­рацию. Суммарная производительность: 28 деталей в единицу времени.

26.4. Выбор инвестиционных проектов в условиях ограниченности финансовых ресурсов

При планировании вложений проект может быть принят к исполнению, если он имеет положительную чистую приведен­ную стоимость. Однако в действительности для предприятий существуют ограничения, связанные с нехваткой финансовых ресурсов на его осуществление. В этом случае возникает не­обходимость разработки такого метода отбора одного проекта (или группы проектов), который, с одной стороны, обеспечит максимально возможную чистую приведенную стоимость, а с другой — позволит "уложиться" в выделенные для инвестиций средства.

Например, у предприятия для выполнения некоторых про­грамм имеется пять инвестиционных проектов, чистая приве­денная стоимость которых указана в табл. 26.2. Однако пред­приятие не может финансировать все проекты: суммы денег, выделенные на текущий год и последующие два, меньше не­обходимых для инвестирования в полном объеме. При этом оставшиеся денежные средства не могут быть перенесены на следующие годы, также не предусмотрено более одного финан­сирования одного и того же проекта. Требуется распределить выделенные средства в инвестиционные проекты оптимальным способом.

Решение. Обозначим черех xj долю вложения в j-й про­ект, где j = . Тогда чистая приведенная стоимость инвес­тиций в 1-й проект составит 40x1; во 2-й проект — 60x2 и т. д. При этом необходимо учитывать, что инвестиции не должны превышать 54, 62 и 70 ден. ед. в первый, второй и третий годы соответственно. Требуется выбрать один или группу проектов с наибольшей совокупной чистой приведенной стоимостью.

Математическая модель этой экономической задачи имеет вид

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

причем xj = 0 или 1, j = (проект либо финансируется, либо нет).

Решая задачу на компьютере, получаем х1 = х2 = х4 = x5 = 1, x3 = 0. Иными словами, необходимо производить финансирование 1, 2, 4 и 5-го проектов. При этом потребуются денежные средства в объеме 177 ден. ед. в течение трех лет (при выделяемом предприятием объеме 186 ден. ед.), а сумма чистой приведенной пои мести проектов будет максимальной и составит 205 ден. ед.

Математическая модель может быть составлена для произ­вольного конечного числа программ при предполагаемом фи­нансировании в течение любого количества лет.

УПРАЖНЕНИЯ

26.1. Фирма имеет три механизма A1, А2, А3, каждый из ко­торых может быть использован на каждом из трех видов ра­бот B1, B2, B3 с производительностью, заданной матрицей (в условных единицах)

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

26.2. Пять человек должны выполнить четыре работы, при­чем каждый из работников с разной производительностью мо­жет выполнить любую из этих работ. Предусматривается, что каждый работник в состоянии сделать только одну работу.

Производительности работников при выполнении работ зада­ны матрицей

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

26.3. Фирма, имеющая четыре склада, получила четыре зака­за, которые необходимо доставить различным потребителям. Складские помещения каждой базы имеют вполне достаточ­ное количество товара, чтобы выполнить любой один из этих заказов.

Расстояния между каждой базой и каждым потребителем приведены в матрице

Как следует распределить заказы по базам, чтобы общая даль­ность транспортировки была минимальной?

26.4. Фирма объединяет три предприятия, каждое из которых производит 3 вида изделий.

Себестоимости каждого изделия в усл. ед. при изготовле­нии на каждом предприятии указаны в матрице

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

26.5. Компания разрабатывает план выпуска трех новых ви­дов продукции. Она уже владеет пятью предприятиями, и те­перь на трех из них должны производиться новые виды про­дукции — по одному виду на одно предприятие.

Даны издержки производства единицы продукции, усл. ед.:

Издержки сбыта единицы продукции, усл. ед.:

Плановый объем годового производства, который позволил бы удовлетворить спрос, и себестоимость единицы продукции каждого вида приведены в табл. 26.3.

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

27.1. Формулировка задачи

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

Нахождение компромиссного решения относится к много­критериальным задачам оценки оптимальности.

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

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

2. Построение единого (интегрального) показателя эффек­тивности посредством суммирования произведений име­ющихся показателей на "весовые" коэффициенты (коэф­фициенты важности показателей).

3. Превращение всех целевых функций, кроме одной, в ограничения.

27.2. Математическая модель нахождения компромиссного решения

Дана математическая модель экономической задачи, в ко­торой две целевые функции и система ограничений линейны. Найдем компромиссное решение по двум показателям, один из которых требует отыскания максимума, а другой — мини­мума:

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

где L1, L2 — значения целевых функций (экономические пока­затели), для упрощения записи опущены обозначения аргумен­та; aij, cj, dj, bi — коэффициенты; xj — переменные.

Решим задачу по каждому показателю в отдельности и найдем оптимальные значения L1max, L2min.

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

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

где W — целевая функция; xn+1 — наибольшее относительное значение экономических показателей.

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

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