В экономических организациях

Модели линейного программирования

(8 часов)

 

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

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

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

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

Пример 3. Цех выпускает в смену трансформаторы двух видов. Для их изготовления используются железо и проволока. Общий запас железа – 24 кг, проволоки – 18 кг. На один трансформатор первого вида расходуются 3 кг железа и 3 кг проволоки, а на один трансформатор второго вида – 4 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 4 д. е., второго – 2 д. е.

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

В данной задаче две неизвестные: – выпуск трансформаторов Т1 за смену, – выпуск трансформаторов Т2 за смену.

Ограничения накладываются на запасы железа и проволоки, а также на выпуск трансформаторов Т1 за смену:

Целевая функция имеет вид: .

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

1. : ,

.

1. : ,

.

1. – любое значение (вертикальная прямая).

Для построения целевой функции (значение выбрано произвольно):

,

.

 

Рис. 1. Графическое решение задачи

 

Из рис. 1 видно, что точкой максимума является точка В (точка пересечения прямых (2) и (3)), координаты которой можно определить как решение системы

Подставляя значение в первое уравнение системы, получаем значение . Целевая функция принимает значение .

Таким образом, может быть сделан следующий вывод: максимальная прибыль 20 д. е. будет получена при выпуске за смену и реализации 4 трансформаторов Т1 и 3 трансформаторов Т2.

 

Транспортная задача

(8 часов)

Транспортная модель используется при разработке плана перевозок одного вида продукции из нескольких пунктов отправления в пункты назначения. При построении модели используются:

- величины, характеризующие предложение в каждом исходном пункте и спрос в каждом пункте назначения;

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

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

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

Затем заполняется расчетная таблица и составляется первый опорный план, который может быть получен несколькими способами. Более близкий к оптимальному опорный план может быть получен методом минимальных в таблице затрат. При этом способе составление плана начинается с клетки с минимальной оценкой при решении задачи на минимум или с максимальной оценкой при решении на максимум. Если в таблице имеется несколько клеток с одинаковыми «лучшими» оценками, то заполняется прежде клетка, в которую можно записать наибольшую поставку.

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

 

Алгоритм метода потенциалов (решение задачи на минимум).

1. Для всех заполненных клеток рассчитываются потенциалы по фор­муле

, (4)

где – потенциалы строк; – потенциалы столбцов; – оценки.

Для расчета потенциалов одному из них вначале придают любое значение. Обычно .

2. Для всех свободных клеток рассчитываются характеристики по формуле

. (5)

Если в таблице нет ни одной свободной клетки с отрицательной характеристикой, то план считается оптимальным (при решении задачи на максимум – план оптимальный, если нет положитель­ных характеристик).

3. Среди отрицательных характеристик (при решении на максимум среди положительных) выбирается максимальная по абсолютной величине и для клетки с этой характеристикой строится цепь. Для этого из выбран­ной свободной клетки проводится по строке или столбцу прямая линия до занятой клетки, затем под углом 90° линия проводится до следующей заня­той клетки и так до тех пор, пока цепь не замкнется в исходной клетке.

4. В вершинах цепи, чередуя, проставляются знаки «+» и «–», начиная со свободной клетки. В клетках со знаком «–» выбирается минимальная поставка, которая перераспределяется по цепи: там, где стоит знак «+», она прибавляется, а где «–» – вычитается. Исходная свободная клетка становится занятой, а клетка, в которой выбрана ми­нимальная поставка, свободной.

Составляется новый план и рассчитывается значение целевой функции.

 

 

5. Переход к 1.

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

Таблица 1

Затраты на транспортировку

Участки дорог Заводы	А	В	C	D	Количество рейсов, ед.
АБЗ-1
АБЗ-2
АБЗ-3
АБЗ-4
АБЗ-5
Потребность в машинах, ед.					–

 

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

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

 

Таблица 2

Итерация 1

Заводы	Участки дорог	Предл.
А	В	C	D
АБЗ-1
АБЗ-2		–				+
АБЗ-3		+						–
АБЗ-4
АБЗ-5						–		+
Спрос						–
		–2			–	Z = 12480

 

Условие, что заполненных клеток в таблице должно быть равно m + n – 1 = 5 + 4 – 1= 8, выполняетcя.

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

Проверим, является ли план оптимальным, если нет, то улучшаем его.

1. Рассчитываем значения потенциалов по формуле (4):

; ; ; ; ; ; ; ; .

2. Рассчитываем характеристики для свободных клеток:

; ; ; ; ;

; ; ;

; ;

; .

2. Максимальная по абсолютной величине отрицательная характери­стика в клетке (2,3), для которой строим цепь.

3. Проставляем по углам цепи, начиная с выбранной клетки, знаки «+», «–». В клетках со знаком «–» минимальная поставка 200. Ее перерас­пределяем по цепи. Там, где стоит знак «+», прибавляем, а где «–», вычитаем. Заполняем следующую расчетную табл. 3.

Расчеты ведем аналогично. Получены следующие отрицательные ха­рактеристики: ; ; .

Для клетки (4,1) строим цепь. Перераспределяем по цепи поставку 40. Заполняем таблицу для итерации 3.

В расчетной табл. 4 нет отрицательных характеристик, следователь­но, план оптимальный.

Таблица 3

Итерация 2

Заводы	Участки дорог	Предл.
А	В	C	D
АБЗ-1
АБЗ-2		–				+
АБЗ-3
АБЗ-4		+				–
АБЗ-5
Спрос						–
vj					–	Z=12080

Таблица 4

Итерация 3

Заводы	Участки дорог	Предл.
А	В	C	D
АБЗ-1
АБЗ-2
АБЗ-3
АБЗ-4
АБЗ-5
Спрос						–
		-2			–	Z = 12000

Согласно оптимальному плану, необходимо за квартал с АБЗ-1 направить на участок D 600 машин асфальта, с АБЗ-2 к участку С – 240 машин, с АБЗ-3 к участку А – 560 машин и к участку В – 800 машин, с АБЗ-4 к участку А – 40 машин и к участку С – 960 машин, с АБЗ-5 к участку С – 200 машин и к участку С – 600 машин. При этом минимальные затраты на перевозку составят 12000 д. е.

МОДЕЛИ УПРАВЛЕНИЯ ЗАПАСАМИ

(6 часов)

 

Управление запасами связано с проблемой достижения оптимального равновесия между двумя конкурирующими факторами: минимизацией капиталовложений в запасы и максимизацией уровня обслуживания потребителей предприятия.

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

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

Таким образом, решение обобщенной задачи управления запасами определяется следующим образом:

1. В случае периодического контроля состояния запаса следует обеспечивать поставку нового количества ресурсов в объеме размера заказа через равные интервалы времени (система с фиксированным интервалом времени между заказами).

2. В случае непрерывного контроля состояния запаса необходимо размещать новый заказ в размере объема запаса, когда его уровень достигает точки заказа (система с фиксированным размером заказа).

В зависимости от этого выделяют две основные системы управления запасами: систему с фиксированным размером за­каза, систему с фиксированным интервалом времени между за­казами.

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

,

где – размер заказываемой партии, ед.;

– затраты на размещение заказа, д. е.;

– затраты на хранение единицы продукции, д. е.;

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

Оптимальный размер заказа (партии) основывается на крите­рии оптимизации и рассчитывается по формуле Уилсона

, (6)

где – оптимальный размер партии, ед.

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

Расчет заказа в систе­ме с фиксированным интервалом времени между заказами про­изводится по формуле

, (7)

где – максимально желательный запас;

– текущий запас;

П – ожидаемое потребление за время поставки.

Последовательность расчетовпараметров систем с фиксиро­ванным размером заказа и с фиксированным интервалом време­ни между заказами приведена в табл. 5 и 6.

Таблица 5