Практическая работа
Тема
Выбор транспортно-технологической схемы доставки груза, на основе сетевого графика, по критерию стоимости и времени доставки.
План
Транспортная задача(лекционный материал).
Задача (для самостоятельного решения)
Инструкция
1. Прочитать о методике решения транспортных задач и самостоятельно решить поставленную задачи, после прислать фото отчет(выполнить до 14.05.2020).
2. При возникновении вопросов по лекции(ям) задавать по адресам преподавателя
Адрес преподавателя (для фото отчета и ответов на вопросы, а также если возникли вопросы по предмету)
1. https://vk.com Вячеслав Голиков 
2. vvgolikov24@mail.ru
Конспект
Транспортная задача.
Транспортная задача, это специальный вид задачи линейного программирования. Для решения транспортной задачи можно использовать методы решения задач линейного программирования, однако ввиду специфического вида задачи, были построены алгоритмы специально для решения этой задачи.
Математическая постановка транспортной задачи.
Общая постановка транспортной задачи заключается в определении оптимального плана перевозок некоторого однородного груза из пунктов отправления A 1, A 2,..., Am в пункты назначения B 1, B 2,..., Bn. Критерий оптимальности берется минимальная стоимость перевозки или минимальное время доставки груза.
Рассмотрим транспортную задачу, где в качестве критерия оптимальности взята минимальная стоимость перевозок всего груза. Обозначим через Сij тарифы перевозки единицы груза из пункта отправления i в пункт назначения j. Обозначим через Ai запасы груза i -м пункте отправления, а через Bj потребности груза j -м пункте назначения, а через Xj количество единиц груза переводимого из пункта отправления i в пункт назначения j.
Тогда математическая модель транспортной задачи состоит в определении минимального значения функции
| (1.1) |
при условиях
| (1.2) |
| (1.3) |
| (1.4) |
Поскольку удовлетворяется условия (1.2)−(1.4), то обеспечивается доставка необходимого количества груза в каждый из пунктов назначения, вывоз груза из всех пунктов отправления, а также исключаются обратные перевозки.
Определение 1. Любое неотрицательное решение Xij =∥ xij ∥ (i =1,.., m; j =1,..., n) систем (1.2) и (1.3) называется допустимым планом транспортной задачи.
Определение 2. План 
при котором функция (1.1) принимает минимальное значение, называется оптимальным планом транспортной задачи.
Если сумма груза у поставщиков равно общей сумме потребностей в пунктах назначения:
| (1.5) |
то модель транспортной задачи называется закрытой (или сбалансированной). Если (1.5) не удовлетворяется, то модель транспортной задачи называется открытой (или несбалансированной).
Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие (1.5).
В случае превышения запаса над потребностью, т.е. при
 ,
|
вводится фиктивный (n +1)-ый пункт назначения с потребностью
 .
|
Соответствующие тарифы считаются равными нулю: ci n +1=0 (i =1,..., m). После этих преобразований получим закрытую модель транспортной задачи.
Аналогично, при 
вводится фиктивный (m +1) пункт отправления с грузом 
а тарифы полагаются равными нулю: cm +1j=0 (j =1,..., n). После этих преобразований получим закрытую модель транспортной задачи.
Мы будем рассматривать закрытую модель транспортной задачи. Если же модель транспортной задачи является открытой, то с помощью вышеизложенных преобразований строим закрытую модель транспортной задачи.
Обычно данные транспортной задачи записывают в виде таблицы: 
|
Число переменных Xij равно mn, где m число пунктов отправнения, а n число пунктов назначения. Число уравнений в (1.2) и (1.3) равно m+n. Так как мы рассматриваем закрытую модель транспортной задачи (выполняется равенство (1.5)), то число линейно независимых уравнений равно m+n −1. Следовательно опорный план транспортной задачи может иметь не более m+n −1 отличных от нуля неизвестных.
Если в опорном плане количество отличных от нуля компонентов равно в точности m+n −1, то опорный план называется невырожденным, а если меньше − то вырожденным.
Для решения транспортной задачи сначала определяется начальный опорный план, а затем определяется оптимальный план путем улучшения текущего опорного плана.
Для определения начального опорного плана существует несколько методов. Мы рассмоьтрим три метода. Метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля.