Математическая модель транспортной задачи. Теорема о существование решений ТЗ. Задачи рациона.

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

{spoiler=Подробнее}

Некоторой однородной продукт, сосредоточенный у m поставщиков А_i в количестве а_i(i=1,2,..., m) единиц соответственно, необходимо доставить n потребителям В_j(j=1,2,..., n) единиц.

Известна стоимость С_ij- перевозки единицы груза от  i-го поставщика к j-му потребителю.

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

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

Z=

Систему ограничений получаем из следующих условий задачи:

a) все грузы должны быть вывезены, т.е.

(эти уравнения получаются из строк таблицы планирования.

б) все потребности должны быть удовлетворены, т.е.

(уравнения получаются из столбцов матрицы планирования).

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

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

         (1)

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

            (2)

x_ij>=0(i=1,2, ... ,m; j=1,2, ... .n).

В рассмотренной модели предполагается, что суммарные запасы равны суммарным , потребностям, т.е.

       (3)

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

Теорема. Любая транспортная задача, у которой суммарный объём запасов совпадает с суммарным объемом потребностей, имеет решение. Для доказательства теоремы необходимо показать, что при заданных условиях существует хотя бы один план задачи и линейная функция на множестве планов ограничена.

Доказательство. Пусть

Тогда величины х_ij=а_ib_j/М (i=1,2,...,m;j=1,2,..,n) являются планом, так как они удовлетворяют системе ограничений (1),(2). Действительно, подставляя значения х_ij в(1) и (2), имеем

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

Выберем из значений С_ij наименьшее C¹¹ = min C_ij  и  заменим в линейной функции все коэффициенты на С¹¹; тогда учитывая (2) имеем 

Объединяя два последних неравенства в одно двойное. Окончательно получаем

т.е. линейная функция ограничена на множестве планов транспортной задачи.

Задачи рациона.

Необходимость составления оптимальных рационов является актуальной задачей сельского хозяйства. Она обусловлено требованием полноценного кормления животных и стремлением добиваться максимальной продуктивности скота и птицы при возможно наименьших затратах труда, денежно-материальных средств, кормов и т.п. на их содержание. Кроме того, часто в различных кормах содержатся одинаковые кормовые компоненты, но в неодинаковом количестве. Поэтому одни корма могут заменять другие. Однако экономически такая замена оправдана лишь в определенных случаях - когда стоимость единицы питательности корма ниже стоимости соответствующей единицы другого корма.

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

Примем следующие    обозначения:

j - индекс вида корма  (j=1, 2,..., 16);

i - индекс ограничения (j=1, 2,..., 16);

x_i - количество корма j-го вида, входящего в рацион;

c_j - себестоимость или цена приобретения единицы j-го вида корма;

a_ij - содержание i-го вида корма;

B_i - минимально допустимое  количество i-го питательного вещества в рационе;

Q_i - максимально возможно содержание i-го питательного вещества в рационе;

Q_{i min,} Q_{i max} - соответственно минимально допустимое и максимально возможное содержание кормовых единиц в рационе от конкретной группы кормов;

L - стоимость оптимального рациона.

На основании этих ограничений построим конкретную модель задачи в структурной форме.

Найти

(минимальная стоимость рациона) при условиях:

1)           (i=1)

(общее соотношение по содержанию в рационе кормовых единиц);

1. åa_ijx_j³B_i  (i=2, 3, 4, 5, 16)

(содержание i-ых питательных веществ в рационе должно быть не ниже определенной величины);

3)    

содержание сухих веществ в рационе не должно превышать максимальную норму);  

4)    

(содержание кормовых единиц в рационе по отдельным группам кормов должно находиться в заранее установленных пределах);    

1. x_j³ 0

(условие неотрицательности переменных).

Четвертое ограничение вводится в модель для того, чтобы ограничить содержание отдельных групп кормов (концентрированные, грубые, сочные и т.п.) в рационе.

{/spoilers}