Постановка транспортной задачи в матричной форме. Симплекс метод решения задачи линейного программирования

Петербургский государственный университет путей сообщения

Кафедра «Экономика транспорта»

КУРСОВАЯ РАБОТА

Модели и моделирование на железнодорожном транспорте

Санкт-Петербург

2009

Содержание:

1.  Постановка транспортной задачи в матричной форме................3стр.

  Решение транспортной задачи методом потенциалов.............4стр.

  Решение транспортной задачи методом разрешающих слагаемых.........................................................................................9стр.

2.  Постановка транспортной задачи в сетевой форме......................17стр.

3.  Задача о назначении..............................................................................23стр.

4.  Симплекс метод решения задачи линейного программирования.....27стр.

1. Постановка базисной задачи в матричной форме.

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

i – номер станции отправления или поставщика,

j – номер станции назначения или потребителя.

Постановка транспортной задачи может быть задана в матричной или сетевой форме. От этого зависит специфика решения:

;

x_ij  - переменная (перевозка из n_i d n_j)

c_ij – критерий оптимальности

a_ij  - ресурс станции отправления

b_ij – потребность на станции назначения

d_ij – ограничение пропускной способности

Целевая функция решения задачи:

                                                        (1)

,                                                                       (2)

Сумма всех перевозок для каждого поставщика не превышает его ресурсов.

                                                                    (3)

Для каждого потребителя сумма перевозок равна его потребности

                                                                   (4)

                                                                                       (5)

                                                                                        (6)

1.1 Решение транспортной задачи методом потенциалов.

Для решения задач данного типа вначале строится базисный план, удовлетворяющий постановке задачи 2-6, которая затем оптимизируется.

Построенный план называется допустимым.

Рассмотрим построение допустимого плана методом минимальной стоимости.

В таблице матрицы с_ij отыскивается наименьшее значение, куда заносится наибольшее значение перевозки с учетом потребности строки и точности столбца. Затем снова отыскивается наименьшее с_ij и выполняется аналогичная операция.

Допустимый план должен иметь ((m+n)-1) базисных элементов, где m – число строк, n – число столбцов.

Алгоритм решения:

Шаг 1. Расстановка потенциалов выполняется по формуле:

u_i- потенциал строки

v_j – потенциал столбца

Шаг 2. Проверка плана на оптимальность.

Если все небазисные клетки матрицы удовлетворяют условию:

, то план оптимальный, если нет, то переход к Шагу 3.

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

В найденном контуре производится метка клеток. Новой клетке, входящей в базис присваивается метка «+», остальные клетки получают метод перемещающейся полярности для строки или столбца. Из клеток помеченных «-» отыскиваем наименьшее значение, оно вычитается из указанных клеток и добавляется к клеткам «+». Значение перевозок в других базисных клетках не меняется. Переход к Шагу 1.

Условия:

Значение критериев оптимальности с_ij

Шаг 1: Построим допустимый (базисный) план.