Читать реферат по эконометрике: "Математическая постановка транспортной задачи линейного программирования" Страница 2

(Назад) (Cкачать работу)

…

Bj

…

Bn

А1

A1

C11X11

…

C1jX1j

…

C1nX1n

a1

…

…

…

…

…

…

…

Ai

Ci1Xi1

…

CijXij

…

CinXin

ai

…

…

…

…

…

…

…

Am

Cm1Xm1

…

CmjXmj

…

CmnXmn

am

Потребности

b1

…

bj

…

bn

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единице. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

, (5)

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

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

, i 1, ..., m.

Введение этого условия приводит к открытой транспортной модели.

Теорема 1.

Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение. 2. Модели транспортной задачи

2.1. Закрытая модель транспортной задачи Для доказательства теоремы необходимо показать, что при заданных условиях существует хотя бы один план задачи и линейная функция на множестве планов ограничена.

Доказательство. Пусть = M > 0.

Тогдавеличины xij = aibj /M (i = 1,2,3, ... m; j = 1,2,3, ..., n)являются планом, так как они удовлетворяют системе ограничений

( 2 ) и ( 3 ) .

Действительно, подставляя значения в (2) и (3) , находим

= ai ,

= bj .

Выберем из значений Cij наибольшее C = max Cij и заменим в линейной функции ( 1 ) все коэффициенты на C тогда, учитывая ( 2 ) , получим

,

Выберем из значений Cij наименьшее C=min Cij и заменим в линейной функции все коэффициенты на C ; тогда, учитывая ( 2 ) имеем Объединяя два последних неравенства в одно двойное , окончательно получаем

CM ? Z ? C M,

т. е. линейная функция ограничена на множестве планов транспортной задачи.2.2. Открытая модель транспортной задачи Транспортная задача, в которой суммарные запасы и потребности не совпадают, т. е. не выполняется условие , называется открытой. Для открытой модели может быть два случая:

суммарные запасы превышают суммарные потребности ; суммарные потребности превышают суммарные запасы .

Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.

Найти минимальное значение линейной функции

при ограничениях

,i = 1, 2, ..., m,(случай а)

,j = 1, 2, ..., n;

,i = 1, 2, ..., m,(случай б)

, j = 1, 2, ..., n,

xij  0(i = 1, 2, ..., m;j = 1, 2, ..., n).

Открытая модель решается приведением к закрытой модели.

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого bn+1 = . В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого am+1 = .

Стоимость перевозки

Похожие работы