Теоретические сведения. тема: “Решение транспортной задачи линейного программирования

Лабораторная работа №3

тема: “Решение транспортной задачи линейного программирования. Составление первоначального плана транспортной задачи”

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

Теоретические сведения.

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

Методы составления первоначальных планов включают: метод северо-западного угла, методы минимального элемента (в строке, в столбце, в матрице, двойного предпочтения), метод Фогеля.

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

Метод состоит в следующем. Просматривается матрица перевозок, начиная с левого верхнего угла (клетки). В эту клетку заносится поставка X_ij = min(a_i, b_j). Она вычитается из соответствующих a_i и b_j. Если в результате исчерпан запас a_i, то далее рассматривается i+1 строка, если удовлетворена потребность b_j, то далее рассматривается j+1 столбец. Если X_ij = a_i = b_j, то далее рассматривается i+1 строка, j+1 столбец. Процесс повторяется до тех пор, пока не будет рассмотрена вся таблица.

Метод наименьшего элемента в столбце

Метод состоит в том, что поочередно в каждом столбце, начиная с первого, выбираются минимальные стоимости перевозок C_ij и в соответствующие клетки записываются поставки. Если при этом потребность b_j не удовлетворена, то выбирается следующий по величине элемент в этом столбце из тех строк, в которых мощность поставщика еще не исчерпана, и т.д. пока потребность b_j не будет полностью удовлетворена. Далее рассматривается следующий (j+1) столбец. Процесс повторяется до тех пор, пока не будут рассмотрены все столбцы.

Метод наименьшего элемента в строке

Отличие данного метода от метода наименьшего элемента в столбце заключается в том, что таблица просматривается по строкам.

Метод наименьшего элемента в матрице

Метод состоит в том, что выбирается минимальный элемент C_ij в матрице перевозок. Если в матрице несколько элементов с минимальным значением, то выбирается любой из них и в соответствующую клетку проставляется поставка. Далее выбирается следующий по величине элемент C_ij в строках и столбцах, где a_i ≠ 0 и b_j ≠ 0. Процесс повторяется до тех пор, пока не будет рассмотрена вся таблица

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

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

Метод Фогеля

Метод состоит в следующем. Просматриваются все строки и столбцы матрицы перевозок. В каждой строке и в каждом столбце вычисляется разность между двумя наименьшими элементами. Из всех этих разностей выбирается наибольшая. В выбранной строке или столбце заполняется клетка с наименьшим значением C_ij. Обнулившаяся строка a_i или столбец b_j исключаются из дальнейшего рассмотрения. Далее снова определяются разности между двумя наименьшими элементами, исключая те строки и столбцы для которых уже a_i = 0 или b_j = 0. Если наибольшая разность находится двух строках или столбцах, то выполняется проверка, является ли минимальный элемент по столбцу (строке) также минимальным и по строке (столбцу). Если является, то в данную клетку заносим поставку, если не является, то вычисляются вторые разности – между минимальным и третьим по величине элементом, и выбирается наибольшая разность. Если и по этому признаку нельзя отдать предпочтение ни одному элементу, то выбирается любой из них. Процесс повторяется до тех пор, пока не будет рассмотрена вся таблица.