Решение транспортных задач линейного программирования

Линейное программирование (ЛП) – раздел МП, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных ограничениях, наложенных на эти переменные.
Применение методов МП:
оптимизация производственных программ;
ассортиментная загрузка оборудования;
планирование грузопотоков;
составление оптимальных смесей;
раскрой материалов;
выбор ресурсосберегающих технологий и т.д.

В результате изучения дисциплины студент должен:
Иметь представление: о проблематике и перспективах развития методов математического программирования как одного из важнейших направлений, связанных с созданием и внедрением новых информационных технологий.
Знать: основные принципы и математические методы решения задач линейного программирования (ЗЛП).
Уметь: строить экономико-математическую модель, выбирать рациональный метод решения ЗЛП с целью принятия управленческого решения.
Владеть: компьютерными технологиями подготовки и принятия решений с использованием инструментального средства моделирования – стандартной офисной программы Excel.

Открытый урок «Решение транспортных задач»
Цель занятия: научиться решать транспортные задачи различными методами
Формируемые профессиональные компетенции:
ПК 1.1 Выполнить разработку спецификаций отдельных компонент
Формирование общих компетенций:
ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
ОК 2. Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.

Транспортная задача - это математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов с минимизацией затрат на перемещение.
Существует несколько методов решения транспортной задачи. Два из них:
• решение транспортной задачи методом потенциалов (будем использовать).
• решение транспортной задачи с использованием инструментального средтва моделирования Excel (будем использовать, если успеем).
Решение задачи методом потенциалов происходит в несколько этапов:
• Определение опорного решения.
• Применение к найденному опорному решению самого метода потенциалов.
• Проверка единственности решения.
Определение опорного плана, в свою очередь, можно выполнить несколькими способами. Рассмотрим два из них:
• метод северо-западного угла
• метод минимальных стоимостей

Постановка задачи
Имеется m пунктов производства однородного продукта и n пунктов потребления. Мощности пунктов производства = аi, единиц, потребности пунктов потребления = . .Известны затраты на перевозку единицы продукта от i-го поставщика j-му потребителю. Составить план перевозок, при котором суммарные затраты на все перевозки наименьшие.
Если спрос и предложение совпадают, т.е. , задачу называют сбалансированной (закрытой).
– план перевозок, – количество продукта, перевозимого из i-го пункта производства в j-й пункт потребления
- матрица затрат (тарифов).
Если транспортные затраты прямо пропорциональны количеству перевозимого продукта, то функция цели или (1)

ограничения: (из каждого пункта вывезен весь продукт);
(спрос каждого потребителя удовлетворен) или
(2)
Из условия также следует. (3)