Эксперт по сдаче вступительных испытаний в ВУЗах
ПРАКТИЧЕСКАЯ РАБОТА №3.
ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ СКЛАДОВ С ИСПОЛЬЗОВАНИЕМ ТРАНСПОРТНОЙ ЗАДАЧИ ЛП
Среди задач линейного программирования особое место занимает транспортная задача. Ее методы широко используются в экономике, особенно в транспортных и дистрибьюторских фирмах. Традиционная постановка транспортной задачи такова:
Имеются
m поставщиков и
n потребителей. У поставщиков сосредоточен однородный груз
в количестве
a1, a2,…..am. Спрос потребителей на груз:
в1, в2,….вn. Известны стоимости (тарифы)
с ij на перевозку единицы груза от
i-го поставщика к
j— му потребителю. Требуется составить оптимальный план перевозок грузов такой, чтобы:
- вывести весь груз поставщиков
- удовлетворить весь спрос потребителей
- минимизировать суммарные затраты.
Математическая модель задачи:
Пусть
хij – количество груза, перевозимого от
i-го исх. пункта к
j-му пункту потребления.
х11 + х12+ ….+х1n= а1
х21 + х22+ ….+х2n= а2 →все грузы должны быть вывезены (3.1)
……………………..
хm1 + хm2+ ….+хmn= аm
х11 + х21+ ….+хm1= b1
х12 + х22+ ….+хm2= b2 → весь спрос удовлетворен (3.2)
…………………….
х1n + х2n+ ….+хmn= bn
(3.3)
Замечание:
Если , то задача называется закрытой, в противном случае — открытой. Доказано, что закрытая транспортная задача всегда имеет оптимальное решение.
Транспортная задача, как задача ЛП может быть решена симплексным методом. Но существуют более простые методы решения которые являются модификацией симплексного метода. Наиболее известным из них является метод потенциалов. В нем применяется тот же прием последовательного улучшения плана, состоящий из трех этапов:
— находится исходное опорное решение;
— оценка решения на оптимальность;
— переход к другому лучшему опорному решению путем однократного замещения одной базовой переменной на свободную.
При этом первоначальное опорное решение ищется с помощью метода «северо-западного угла» или «минимального элемента»
Транспортную задачу ЛП можно также решить в среде Microsoft Excel, меню Сервис-Поиск решения. Формат представления данных и результатов решения приведен в прил. 4.
Торговый дом имеет четыре супермаркета, расположенные в четырех районах P, Q, R, S. Поставки продукции в эти супермаркеты осуществляются с двух, всегда полностью заполненных, складов А и В, площади которых вмещают по 40 контейнеров.
Прогнозирование спроса, выполненное службой маркетинга, показывает, что потребность супермаркетов в продукции в скором времени составит 50, 25, 30 и 35 контейнеров в день, соответственно.
Поэтому, планируется построить третий склад, который также всегда будет полностью заполнен и площадь которого вместит 60 контейнеров.
В таблице 1 приведены транспортные затраты (в руб.), соответствующие перевозкам одного контейнера со складов А и В и нового склада в каждый из супермаркетов. При этом рассматриваются два варианта размещения нового склада.
Менеджеру торгового дома требуется выбрать и обосновать оптимальный вариант размещения нового склада. Указать соответствующие оптимальные затраты. Результаты представить в графической форме.
Проверить результаты решением в среде EXCEL.
Табл.1
| Склад |
P |
Q |
R |
S |
| A |
70 |
85+ V |
55- V |
120 |
| B |
110-V |
90 |
75 |
110+ V |
| С (вариант 1) |
115 |
115- V |
70 |
90 |
| D (вариант 2) |
135 |
95 |
80 |
75+ V |
