МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ Факультет заочно-послевузовского обучения КУРСОВАЯ РАБОТА По дисциплине: "Методы оптимизации" На тему: " Решение задач транспортного типа методом потенциалов " Воронеж 2003 г. СОДЕРЖАНИЕ 1. Линейная транспортная задача. 3 2. Математическая модель транспортной задачи. 4 3. Составление опорного плана. 5 4. Распределительный метод достижения оптимального плана. 8 5. Решение транспортной задачи методом потенциалов. 11 Список использованной литературы 16 1. Линейная транспортная задача.
    
    Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы k С i j.
    Далее, предполагается, что
    
    где ai есть количество продукции, находящееся на складе i, и bj - потребность потребителя j.
    
    Замечание.
    1. Если сумма запасов в пунктах отправления превышает сумму поданных заявок то количество продукции, равное остается на складах. В этом случае мы введем "фиктивного" потребителя n +1 с потребностью и положим транспортные расходы pi,n+1 равными 0 для всех i.
    2. Если сумма поданных заявок превышает наличные запасы то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m + 1 с запасом и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.
    
     2. Математическая модель транспортной задачи.
    
    
    
    
    
    
    
    где xij количество продукции, поставляемое со склада i потребителю j, а С i j издержки (стоимость перевозок со склада i потребителю j).
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
     3. Составление опорного плана.
    
    Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ северо-западного угла, способ минимальной стоимости по строке, способ минимальной стоимости по столбцу и способ минимальной стоимости таблицы.
    Рассмотрим простейший, так называемый способ северо-западного угла. Пояснить его проще всего будет на конкретном примере:
    Условия транспортной задачи заданы транспортной таблицей.
    
    Таблица № 1
     ПН ПО В1 В2 В3 В4 В5 Запасы аi А1 10 8 5 6 9 48 А2 6 7 8 6 5 30 А3 8 7 10 8 7 27 А4 7 5 4 6 8 20 Заявки bj 18 27 42 12 26 125
    Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки ("северо-западного угла" таблицы). ............