Контрольная работа: Математические методы экономических исследований

Если в этой системе имеется переменная, входящая только в одно уравнение, и коэффициент при ней имеет знак «+», то уравнение можно разрешить относительно этой переменной.

Считаем, что в (4.2) уравнения разрешены относительно всех таких переменных, тогда, сделав перенумерацию, имеем:

(4.3)

l = 1, 2, ..., l₀ ;  = 1, 2, ..., ₀ ;

l₀ + ₀ = m; l₀ + k = n; .

Любое уравнение в (4.3), неразрешенное относительно какой-либо переменной, будем называть 0-уравнением.

Для системы (4.3) неотрицательное решение отыскивается последовательными тождественными преобразованиями, удовлетворяющими следующим условиям:

1. Отыскиваем 0-уравнение, у которого свободный член (если такого свободного члена нет, то значения переменных xl = bl, , l = 1, 2, ..., l0; j = 1, 2, ..., k образуют неотрицательное решение системы (4.3)). Пусть это будет i-ое уравнение.

2. Отмечаем в i-ом уравнении положительный коэффициент .

3. Находим разрешающий элемент и производим торжествен­ное преобразование (4.3).

4. i-ое 0-уравнение используется до тех пор, пока либо разрешим его, либо придем к несовместимости системы (4.3).

5. После разрешения i-го уравнения отыскиваем следующее 0-уравнение с положительным свободным членом и производим с ним аналогичные действия.

6. Процесс продолжается до тех пор, пока не освободимся от всех 0-уравнений.

В результате можем получить:

а) после конечного числа тождественных преобразований система освободится от 0-уравнений. Тогда система будет совместимой. Совокупность значений переменных, получаемых приравниванием неосновных переменных нулю, а основных - свободным членам в системе, не содержащей 0-уравнений, является неотрицательным решением исходной системы;

б) После конечного числа тождественных преобразований обнаружится, что используемое 0-уравнение превращается в уравнение вида:

,

где , т.е. для всех j - система несовместна;

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

Тема 5. Транспортная задача

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

2. Общий подход к решению транспортной задачи.

Краткое содержание темы

Среди задач линейного программирования выделяется класс задач, условия постановки которых в определенной степени позволяют упростить процедуру их решения и определить специфические алгоритмы нахождения этих решений. Этот класс задач получил название "Транспортные задачи".

Рассмотрим постановку таких задач.

Пусть имеем m предприятий A₁ , A₂ ,..., A_m , производящих один и тот же продукт в количествах соответственно a₁ , a₂ ,..., a_m .

Пусть, далее, имеется n потребителей (складов) B₁ , B₂ ,..., B_n с потребностями (вместимостями) соответственно b₁ , b₂ ,..., b_n .

Пусть весь произведенный продукт может быть размещен на складах B₁ , B₂ ,..., B_n при полном их заполнении.

Пусть, наконец, перевозка единицы продукции из пункта A_i в пункт B_j оценивается величиной c_ij (c_ij - заданы).

Необходимо определить наилучший план перевозок по стоимости, т.е. такой план, который давал бы минимальную стоимость перевозок всей произведенной продукции на склады.

Строим математическую модель. Пусть x_ij - количество продукта, перевозимого из пункта A_i в пункт B_j . Из постановки задачи очевидно, что каждый склад вмещает: