Юридический техникум Рассмотрено и одобрено ПЦК
г. Кропоткин программирования
Председатель ПЦК
Покалицына О.В.
План чтения лекции по учебной дисциплине
«Математические методы»
Раздел № 2. Линейное программирование. Тема № 2.5. Транспортная задача.
Место проведения: аудитория.
Литература:
1. Венцель Е.С. Исследование операций. Задач, принципы, методология. – М.: Наука, 1980.
2. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе. – М.:ЮНИТИДАНА, 2001
Учебные вопросы и расчет времени
№п/п | Учебные вопросы | Время, мин | Методические указания |
1. 2. 3. | Постановка транспортной задачи. Математическая модель транспортной задачи. Методы решения транспортной задачи. |
1. Вводная часть. Организационный момент. План занятия. Основные требования.
2. Основная часть.
1. Постановка транспортной задачи.
Важным частным случаем задачи линейного программирования является транспортная задача.
Постановка задачи: Пусть имеется m поставщиков и n потребителей. Мощность поставщиков и спросы потребителей, а так же затраты на перевозку груза для каждой пары «поставщик – потребитель» заданы таблицей.
поставщики | потребители | В1 | В2 | … | Вj | … | Bn | Мощность поставщиков |
A1 | С11 | С12 |
| С1j |
| С1n | a1 | |
A2 | С21 | С22 |
| С2j |
| С2n | a2 | |
… | … | … |
| … |
| … |
| |
Ai | Сij | Сij |
| Сij |
| Сin | ai | |
… | … | … |
| … |
| … |
| |
Am | Cm1 | Cm2 |
| Cmj |
| Cmn | am | |
Спрос потребителей | b1 | b2 |
| bj |
| bn |
|
Найти объемы перевозок каждой пары «поставщик – потребитель» так, чтобы: мощности всех поставщиков были реализованы; спросы всех потребителей были удовлетворены; суммарные затраты на перевозку были бы максимальны.
Особенности математической модели транспортной задачи:
ü система ограничений есть система уравнений, то есть задача ЛП в каноническом виде;
ü коэффициенты при неизвестных системы ограничений равны единицы или нулю;
ü каждая переменная входит в систему ограничений два раза: один раз в систему ограничений поставок, второй раз – в систему ограничений спроса.
2. Математическая модель транспортной задачи.
Пусть хij – количество груза, перевозимого с i-го в j-й пункт.
Целевая функция:
Система ограничений:
Для решения задачи составляется таблица. В клетки таблицы записывается стоимость соответствующих перевозок сij и в них же заносятся значения перевозок xij, удовлетворяющих поставленным ограничениям. Клетки с не нулевыми перевозками называются базисными, а с нулевыми – свободными. В зависимости от соотношения между запасами и заявками транспортная задача называется сбалансированной или несбалансированной.
Сбалансированная ТЗ:
Несбалансированная ТЗ:
Для сбалансированной ТЗ ограничения принимают вид равенств, то есть получаем m+n ограничений, в которых все переменные линейно зависимы. В результате допустимое решение сбалансированной ТЗ может быть получено, если заполнять клетки транспортной таблицы таким образом, чтобы сумма перевозок в каждой строке должна быть равна запасам ai, а сумма перевозок в каждом столбце равна соответствующей заявке вj. Вариантов заполнения транспортной таблицы множество, поэтому искомым решением является то из допустимых решений, для которых общая стоимость перевозок будет минимальной.
... продукции второго вида. В этом случае предприятие получит прибыль денежных единиц. 2. Решить транспортную задачу распределительным методом, оценивая свободные клетки по методу потенциалов. 60 50 85 75 65 8 10 6 5 65 80 4 30 3 50 5 9 35 11 25 4 4 8 10 90 5 5 5 3 85 6 Проверим необходимое ...
... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...
... , является линейной функцией переменных : (2.4) Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4). Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без ...
... метод потенциалов. Однако на распределительном методе основаны некоторые другие способы решения задач, что и вызывает необходимость его изучения. [5] 9. Метод потенциалов Решение транспортной задачи любым способом производится на макете. Макет для применения метода потенциалов имеет следующий вид. Основная часть макета выделена двойными линиями. Она содержит k×l клеток. Каждая ...
0 комментариев