Машиностроение и механика

Article Index
Моделирование процессов и объектов в металлургии: математические методы оптимизации
Методы построения обобщённых критериев оптимальности
Классификация оптимизационных задач
Аналитические методы решения оптимизационных задач
Поисковые (численные) методы решения однофакторных оптимизационных задач
Поисковые методы решения многофакторных оптимизационных задач
Метод координатного спуска
Градиентные методы
Симплексные методы
Экспериментальные методы оптимизации
Методы линейного программирования
Решение задач линейного программирования
All Pages

 

Методы линейного программирования

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

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

· Шихтовая задача;

· Задача об использовании ресурсов;

· Транспортная задача;

· Задача о составлении расписаний.

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

Рассмотрим постановку задачи. Пусть имеется 4 поставщика медных концентратов (обогатительных фабрик), и существует 3 медеплавильных завода для переработки этих концентратов. Требуется организовать перевозку концентрата с обогатительных фабрик на медеплавильные заводы. Всё количество медных концентратов должно быть вывезено и переработано, все медеплавильные заводы должны быть загружены переработкой концентратов. При этом суммарная стоимость перевозки концентратов должна быть минимальной.

Обозначим обогатительные фабрики А₁…А₄, а медеплавильные заводы В₁…В₃. Пусть стоимость перевозки одной тонны концентрата от i-того поставщика к j-тому потребителю составляет С_ij. Такая матрица носит название стоимости перевозок. Количество тонн концентрата, перевозимое от i-того поставщика к j-тому потребителю обозначим как х_ij и запишем в соответствующую матрицу, которая называется матрицей элементов решения.

	В1	В2	В3
А1 А2 А3 А4	С11 С21 С31 С41	С12 С22 С32 С42	С13 С23 С33 С43	а1 а2 а3 а4

Суммарная стоимость перевозки концентрата от А_i к В_i будет:

.

Разумеется, мы желаем достичь минимальной стоимости всех перевозок. Кроме того, все элементы решения – неотрицательные числа:

.

По условию задачи все концентраты должны быть вывезены от поставщиков:

,

и доставлены потребителям:

.

	В1	В2	В3
А1 А2 А3 А4	Х11 Х21 Х31 Х41	Х12 Х22 Х32 Х42	Х13 Х23 Х33 Х43
	b1	b2	b3

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