Юридический техникум Рассмотрено и одобрено ПЦК г. Кропоткин программирования Председатель ПЦК Покалицына О.В. План чтения лекции по учебной дисциплине "Математические методы" Раздел № 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. Вариантов заполнения транспортной таблицы множество, поэтому искомым решением является то из допустимых решений, для которых общая стоимость перевозок будет минимальной. 3. Методы решения транспортной задачи. Транспортная задача может быть решена симплекс методом. Однако специфическая форма системы ограничений позволяет упростить симплекс метод. МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА. ............