Элементы линейного программирования Параметрическое линейное программирование

Высшая математика в экономике

Вырожденность в транспортных задачах

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

Рассмотрим вырожденность в транспортной задаче на примере.

Пример 2. Фирма осуществляет поставку бутылок на три завода, занимающиеся производством прохладительных напитков. Она имеет три склада, причем на складе 1 находится 6000 бутылок, на складе 2 — 3 000 бутылок и на складе 3 — 4 000 бутылок. Первому заводу требуется 4000 бутылок, второму заводу — 5 000 бутылок, третьему заводу — 1000 бутылок. Матрицей

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

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

Решение. Запишем исходные данные в распределительную таблицу (табл. 23.9), найдем исходное опорное решение по методу минимального тарифа. Число заполненных клеток равно 5, т + п - 1 = 6, следовательно, задача является вырожденной.

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

Так, для нахождения потенциала и3 поместим нулевую поставку в клетку (3,2), после чего представляется возможным вычислить остальные потенциалы.

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

Все оценки отрицательные, получили оптимальное решение:

Таким образом, со склада 1 целесообразно поставить 3000 бутылок второму и четвертому заводам, со склада 2 — 2000 бутылок второму заводу и 1000 бутылок третьему, со склада 3 — 4000 бутылок первому заводу, при этом стоимость транспортных расходов будет минимальной и составит 28 000 усл. ед.

Открытая транспортная задача

При открытой транспортной задаче сумма запасов не совпадает с суммой потребностей, т.е.

При этом:

а) если

то объем запасов превышает объем потребления, все потребители будут удовлетворены полностью и часть запасов останется невывезенной. Для решения задачи вводят фиктивного (n + 1)-потребителя, потребности которого

Модель такой задачи будет иметь вид

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

б) если

то объем потребления превышает объем запасов, часть потребностей останется неудовлетворенной. Для решения задачи вводим фиктивного (m + 1)- поставщика

:

Модель такой задачи имеет вид

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

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

Определение оптимального варианта перевозки грузов с учетом трансформации спроса и предложений

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

Составить оптимальный план перевозки грузов от трех поставщиков с грузами 240, 40, 110 т к четырем потребителям с запросами 90, 190, 40 и 130 т. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей

Решение. Запасы грузов у поставщиков:  = 390 т. Запросы потребителей:  = 450 т; так как

  < то вводим фиктивного поставщика с грузом а4ф = 450 - 390 = 60 т.

Тариф фиктивного поставщика 4ф примем равным 20 усл. ед.

Так как т + п – 1 = 7, а число занятых клеток равно 6, то для исключения вырожденности введем в клетку (2, 2) нулевую поставку. Оценки свободных клеток:

(табл. 23.10).

Оценка свободной клетки (1,3) больше нуля, перераспределим грузы:

Запишем полученное перераспределение грузов в табл. 23.11.

Имеем

Получили оптимальное решение:

Стоимость транспортных расходов — 3120 усл. ед.

 Пример. Найти предел.

  Пример. Найти предел .

 Для нахождения этого предела разложим на множители числитель и знаменатель данной дроби.

x2 – 6x + 8 = 0; x2 – 8x + 12 = 0;

D = 36 – 32 = 4; D = 64 – 48 = 16;

x1 = (6 + 2)/2 = 4; x1 = (8 + 4)/2 = 6;

x2 = (6 – 2)/2 = 2 ; x2 = (8 – 4)/2 = 2;

Тогда

Свойства бесконечно малых функций.

Сумма фиксированного числа бесконечно малых функций при х®а тоже бесконечно малая функция при х®а.

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

Произведение бесконечно малой функции на функцию, ограниченную вблизи точки х = а является бесконечно малой функцией при х®а.

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

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

Доказательство теоремы 2. Представим f(x) = A + a(x), g(x) = B + b(x), где

, тогда

f(x) ± g(x) = (A + B) + a(x) + b(x)

A + B = const, a(х) + b(х) – бесконечно малая, значит

Теорема доказана.

Доказательство теоремы 3. Представим f(x) = A + a(x), g(x) = B + b(x), где

, тогда

A×B = const, a(х) и b(х) – бесконечно малые, значит

Теорема доказана.


Элементы системы массового обслуживания