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

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

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

• Шихтовая задача.

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

• Транспортная задача.

• Составление расписаний и т.д.

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

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

Решение задач линейного программирования.

Геометрический метод.

Имеется 2 предприятия, производящие 2 продукта.

3x₁ + 5x₂ = 15

5x₂ = –3x₁ + 15

x₁ ≥ 0

x₂ ≥ 0

3x₁ + 9x₂ ≤ 75

x₁ + x₂ ≤ 10

x₁ – x₂ ≤3

ПОР –прямая опорных решений.

3x₁ + 9x₂ = 75

x₁ + x₂ = 10

x₁ = 2,5, x₂ = 7,5

L = 45

В задачах линейного программирования находится в ОДР.

69