Математические методы (стр. 2 из 3)

I шаг:

Основные переменные: х₂, х₄, х₅

Свободные переменные: х₁, х₃

С помощью дополнительных неотрицательных переменных перейдём к системе уравнений:

x₂=1+x₁-x₃

x₄=-4+6x₁-3x₃

x₅=25+3x₃

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

X1=(0,1,0,-4,25) – недопустимое базисное решение.

х₃=min{1,∞,

}=1

II Шаг

Основные переменные: х₁, х₂, х₅

Свободные переменные: х₃, х₄

Выразимновыеосновныепеременныечерезнеосновные:

х₁=2/3+х₃/2+х₄/6

x₂=5/3+x₃/2+x₄/6

x₅=25+x₃

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

X2=(

, ,0,0,25) – допустимое базисное решение.

Выражаем линейную функцию через неосновные переменные:

Z(x)=2/3+x₃/2+x₄/6-5/3-x₃/2-x₄/6+25+x₃=24+x₃=24.

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

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

Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача – это задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления.

Исходные данные транспортной задачи записываются в таблице вида:

b1	b2	…	bn
a1	c11	c12	…	c1n
a2	c21	c22	…	c2n
…	…	…	…	…
am	cm1	cm2	…	cmn

Где a_i – объемы поставок, b_j – объемы потребления, с_mn – стоимости перевозок.

Переменными транспортной задачи являются x_ij– объемы перевозок от каждого i-го поставщика каждому j-му потребителю. В рассмотренной задаче предполагается, что суммарные запасы поставщиков равны суммарным запасам потребителей, такая задача называется задачей с правильным балансом, а ее модель – закрытой. Если же равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель – открытой. Для того, чтобы транспортная задача имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т. е. задача должна бать с правильным балансом.

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

Согласно данному методу запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика. Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m + n -1.

Метод минимальной стоимости

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

Алгоритм решения транспортных задач методом потенциалов:

· Проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводиться фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок;

· Построить начальное опорное решение, проверить правильность его построения по количеству занятых клеток (их должно быть m + n - 1);

· Построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений u_i + v_j= c_ij при x_ij>=0, которая имеет бесконечное множество решений. Для нахождения частного решения системы одному из потенциалов задают произвольно некоторое значение. Остальные потенциалы считаются по формулам u_i= c_ij- v_jи v_j= c_ij- u_i.

· Проверить выполнение условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток D_ij = u_i+ v_j- c_ij, если D_ij>=0 , то полученное решение считается оптимальным, если нет то подлежит улучшению;

· Перейти к новому опорному решению, на котором значение целевой функции будет меньше. Для этого строят циклы.

IV Задание:

I способ: распределение поставок

методом минимальной стоимости.

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