Методы решения задач транспортного типа

Задание. 

Изучить и решить различные классы задач  математического программирования и методы их решения.

Тема  работы – «методы решения задач транспортного типа».

Срок  сдачи работы – 23 декабря. 

Аннотация. 

Данная  работа состоит из 4 заданий, каждое задание включает в себя несколько  пунктов.

Цель  работы состоит в изучении различных  классов задач математического  программирования, а также  методов  их решения.

Данная  работа актуально тем, что она  содержит все характерные черты  рассматриваемых в ней классов  задач, рассматривает широкий круг методов решения этих задач и  проводит их геометрическую интерпретацию. Работа является наглядным примером решения различных классов задач  математического программирования.

Работа  состоит из  страниц, 6 рисунков и 54 таблиц. 
 
 
 
 
 
 
 
 
 
 

Содержание. 

1. Введение
2. Задание №1

-метод северо-западного  угла

-метод минимального элемента

-метод двойного предпочтения

-метод потенциалов

-венгерский метод

3. Задание №2

-графический  метод

-прямая задача

-двойственная  задача

-симплекс-метод

-метод целочисленных  форм

-метод ветвей  и границ

4. Задание №3

-метод наискорейшего  спуска

-метод золотого  сечения

-метод Ньютона

-метод Нелдора-Мида

5. Задание №4
6. Заключение
7. Список литературы

 
 
 
 
 
 

Введение. 

  Как лучше организовать производство, по каким ценам выгодно производить  продукцию, как лучше всего использовать производственные ресурсы, которые  высвобождаются и т.п.?

  На  все эти вопросы позволяет  получить ответ математическое программирование, являющееся действенным инструментом принятия решений.

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

  В данной курсовой работе рассмотрены различные классы задач математического программирования и методы их решения:

• первая группа задач — транспортные задачи, задача о назначении, задача выбора;
• ко второй группе задач относятся задачи линейного программирования, решаемые различными методами (прямой симплекс-метод, двойственный симплекс-метод);
• задачи нелинейного программирования входят в следующую, третью группу и решаются методом наискорейшего спуска, методом Ньютона, для оценки полученного решения используются методы «золотого сечения» ; задачи выпуклого программирования, решаемые с помощью метода возможных направлений или методом Нелдора - Мида, также входят в данную группу;
• задачи динамического программирования и матричные игры, решаемые симплекс-методом, составляют свой, четвертый класс.

  Задачи содержат небольшую размерность. Это позволяет рассмотреть широкий круг методов решения и провести их геометрическую интерпретацию. Оптимизационные задачи содержат все характерные черты рассматриваемого класса задач.

  При выполнении задания делались рисунки, проясняющие геометрическую сущность задачи. Наглядность обеспечивает более глубокое понимание идеи метода, а также проверку достоверности результата.

  Сначала детально прорабатывался алгоритм и только после 
этого делались вычисления. Выполнение алгоритма  
производились с помощью блок-схем, либо с помощью языков программирования высокого уровня. Это позволило организовать мышление и использовать для вычислений имеющиеся технические 
средства.

Основная  часть. 

Задание № 1

Методы  решения задач  транспортного типа 

1. Задание для  предложенного варианта

 
  

1.  Привести математическую постановку транспортной задачи (ТЗ).
2. Найти опорное решение ТЗ методом северо-западного угла и методом минимального элемента. Сравнить по значению целевой функции качество полученных опорных планов.
3. Получить оптимальный план перевозок методом потенциалов. Сравнить значение целевой функции на каждом шаге метода со значением для опорного плана.

  1.1.4. Решить задачу о назначении венгерским методом. 

1.2. Методические указания к выполнению задания № 1

  Метод потенциалов для решения ТЗ подробно освещен в [1-3]. Необходимо обратить внимание на экономический смысл условий оптимальности решения ТЗ, выражаемых через потенциалы. На каждом шаге реализации метода необходимо эти условия проверять. По возможности следует составить для каждого шага граф перевозок, в котором группа вершин с исходными дугами соответствует пунктам потребления. Дуги соотносятся с ненулевыми перевозками. Каждой вершине соответствует потенциал, а каждой дуге — стоимость перевозки. Данный граф удобно использовать для составления потенциальных уровней.

  Рассмотреть ситуацию, когда ТЗ будет вырожденной.

  Решая задачу о назначении (задача выбора), необходимо дать ее содержательную, а  также математическую постановку. Показать, что эта задача является частным случаем транспортной задачи. Исходными данными для задачи о назначении служит матрица, использованная в ТЗ. 

    Исходные  данные: 

Таблица 1.

 
 

    1.2.1. Метод северо-западного угла. 

Расставляем данные так, чтобы сумма строк  была равна В, а сумма столбцов – А. В верхнем левом углу таблицы выставляем максимальное количество груза, затем опять выбираем свободное окно в левом окне и заполняем таблицу 

Таблица 2.

 

W_с-з = 17∙12+22∙2+12∙18+13∙10+2∙11+3∙12+4∙17+27∙14 = 1098 
 

    1.2.2. Метод минимального элемента. 

  В каждой строке выбираем минимальный  элемент, обозначаем * и в эти ячейки расставляем максимальное количество груза.

Таблица 3. 

 

W_min = 19∙26+17∙11+5∙21+21∙2+2∙3+4∙17+4∙17+14∙1 = 916 
 

    1.2.3. Метод двойного предпочтения. 

В каждом столбце (*) и в каждой строке (**) выбираем минимальный элемент и расставляем максимальное количество груза. 

Таблица 4.

 

W_дв.пр. = 19∙26+17∙11+5∙21+21∙2+2∙3+4∙17+14∙1 = 916 

    1.2.4. Метод потенциалов. 

Заполняем таблицу аналогично методу северо-западного  угла. 

Таблица 5.