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

РЕФЕРАТ

на тему:

Постановка и модель транспортной задачи линейного программирования. Решение задач в MS Excel

Выполнил:

Студент 41группы

Нурумбетов К.

Проверила:

Спешилова Н.В.

Оренбург- 2013г.

Теоретическая часть

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

Начнем с её содержательной формулировки.

Пусть имеется некоторый однородный продукт, сосредоточенный на m пунктах отправления (складах), так что на i-м складе находится единиц этого продукта.

Этот продукт необходимо доставить в n пунктов назначения (потребления), причем на j-й пункт необходимо доставить единиц продукта. Запасы и потребности сбалансированы, то есть

,

то есть наличие продукта равно потребности в нем.

Пусть стоимость перевозки единицы продукта из i-го склада в j-й пункт назначения равна . Пусть есть то количество продукта, которое перевозится из i-го склада в j-й пункт потребления.

Тогда общие транспортные расходы составят величину

.

Из каждого склада весь продукт должен быть вывезен. Это значит, что должно быть выполнено условие

.

С другой стороны, потребности j-го пункта назначения должны быть полностью удовлетворены. Это означает, что

.

Желание минимизировать транспортные расходы приводит нас к следующей задаче:

являющейся типичной задачей линейного программирования.

Определение. Транспортная задача называется открытой транспортной задачей, если условие баланса нарушаются; в случае выполнения условия баланса она называется сбалансированной транспортной задачей.

Однако у этой задачи есть одна очень существенная особенность: в ограничениях перед неизвестными всегда стоит 1. И именно это позволяет разработать гораздо более эффективные и простые алгоритмы решения транспортной задачи, чем симплекс-метод.

Сам же симплекс-метод был бы не эффективен по двум причинам:

1. Большая размерность решаемой задачи. Общее число неизвестных величин равно mn, и даже при n =m = 10 размерность решаемой задачи уже будет равна 100. Даже ЭВМ будет решать такую задачу симплекс-методом достаточно долго.

2. Опорные планы в транспортной задаче очень часто бывают вырожденными, а наличие вырождения приводит к необходимости несколько модифицировать симплекс-метод.

Приведение открытой транспортной задачи к сбалансированной

1. Превышение запасов над потребностями.

В этом случае вводится “фиктивный” потребитель с потребностями равными абсолютной величине разности между общим количеством запасов и общим количеством требуемых единиц. Стоимость по доставке будет для потребителя равна 0, т.к. поставки фактически нет.

2. Превышение потребностей над запасами.

Вводим “фиктивного” производителя (склад) с потребностями равными абсолютной величине разности между общим количеством запасов и общим количеством требуемых единиц. Стоимость по доставке будет для производителя равна 0, т.к. поставки фактически нет.

4.2. Простейшие свойства транспортной задачи

Теорема 1. Для любой транспортной задачи существует план (то есть для любой транспортной задачи допустимая область не пуста).

Доказательство

Действительно, по смыслу задачи, .

Так как ,

то возьмем план в виде

.

Величины .

Далее

то есть ограничения выполняются. Поэтому составляют план. Теорема доказана.J

Теорема 2. Транспортная задача всегда имеет оптимальный план.

Доказательство

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

.

В силу того, что значения целевой функции ограничены снизу, транспортная задача всегда имеет решение. Теорема доказана.J

Теорема 3. Любой опорный план имеет не более

положительных компонент.

Доказательство

Действительно, исходная система содержит всего ограничений типа равенств:

, то есть m ограничений;

то есть n ограничений.

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

(1)

а из второй группы сложим первые n- 1 ограничение

(2)

Вычитая теперь (2) из (1), получим:

,

и мы получили последнее, n-ое ограничение второй группы.

Таким образом, независимых ограничений всего не более . Поэтому

каждый опорный план имеет не более

компонент.

Следствие. Оптимальный план содержит не более, чем перевозку.