Лекция 8. Тема: “ Определение опорного плана

Тема: “ Определение опорного плана

транспортной задачи”

Решение транспортной задачи, как и решение основной задачи линейного программирования, состоит из двух этапов:

1) нахождение начального плана перевозок , удовлетворяющего ограничениям задачи;

2) улучшение начального плана перевозок и получение оптимального плана перевозок, доставляющего минимум функции .

Общее число неизвестных в транспортной задаче равно , а число уравнений . Так как их правые части связаны условием =, то число линейно-независимых уравнений в ограничениях транспортной задачи равно . Следовательно, опорный план транспортной задачи может иметь не более отличных от нуля неизвестных.

Систему уравнений можно разрешить относительно базисных переменных. Остальные переменных являются свободными. Каждое решение транспортной задачи находят следующим образом: свободные переменные полагаются равными нулю, а базисные переменные находят из системы ограничений. Полученное решение проверяют на оптимальность. Если решение неоптимально, то осуществляют переход к новому решению путём изменения списка базисных переменных. Эти действия повторяют до тех пор, пока не будет получено оптимальное решение, доставляющее минимум целевой функции.

Для определения опорного плана существует несколько методов. Два из них – метод северо-западного угла и метод минимального элемента.

Пример 1. Четыре предприятия используют для производства продукции три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырьё сосредоточено в трёх местах его получения. Предложения поставщиков сырья равны: 160,140 и 170 ед. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через количество единиц сырья, перевозимого из i -ого пункта его получения на j -ое предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счёт выполнения следующих равенств:

(1)

При данном плане перевозок общая стоимость перевозок составит

(2)

Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (1), при котором целевая функция (2) принимает минимальное значение.

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

Шаг 1. Составляют транспортную таблицу.

Шаг 2. Транспортную таблицу начинают заполнять с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз. В клетку, находящуюся на пересечении первой строки и первого столбца, помещается максимально возможное число единиц продукции, разрешённое ограничениями на предложение и спрос: . Пусть например, , тогда и предложение первого поставщика полностью исчерпано. Первая строка вычёркивается, и двигаются по столбцу вниз. В клетку, находящуюся на пересечении первого столбца и второй строки, помещается максимально возможное число единиц продукции, разрешённое ограничениями на предложение и спрос: . Если например, , то . Спрос первого потребителя удовлетворён. Первый столбец вычёркивают и двигаются по второй строке вправо. Заполнив клетку, стоящую на пересечении второй строки и второго столбца, переходят к заполнению следующей третьей клетки второй строки либо второго столбца. Процесс продолжают до тех пор, пока не исчерпается предложение и не удовлетворится спрос.

Замечание. На некотором шаге (но не на последнем) может оказаться, что потребности очередного пункта назначения равны запасам очередного пункта отправления. В этом случае также временно исключают из рассмотрения либо столбец, либо строку (что-нибудь одно). Таким образом, либо запасы соответствующего пункта отправления, либо потребности данного пункта назначения считаются равными нулю.

Определим начальное решение по методу «северо-западного» угла в транспортной задаче из примера 1.

Транспортная таблица имеет следующий вид:

Пункты отправления	Пункты назначения
				Запасы
Потребности

Стоимость перевозок по этому плану равна:

Метод «северо-западного» угла – наиболее простой метод нахождения начального решения. План перевозок, полученный по этому методу, обычно бывает достаточно далёк от оптимального.

Дата добавления: 2014-01-07