logo

94. Постановка задачи линейного программирования и основные методы решения.

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

Наиболее простой и изученной является модель линейного программирования. Она содержит в себе три основных момента:

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

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

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

и минимизировалась величина

.

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

  1. Система ограничений противоречива, задача не имеет неотрицательных решений.

  2. Система ограничений имеет неотрицательные решения, но максимум (минимум) функции цели равен  .

  3. Значение максимума (минимума) целевой функции конечно, система ограничений имеет неотрицательные решения.

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

Задачи линейного программирования можно решить следующими методами:

Алгоритм решения задач линейного программирования методом Дейкстры на графах.

В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевых переменных.

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

На каждом шаге цикла необходимо найти вершину U с минимальным расстоянием и флагом равным нулю. Затем нужно установить в ней флаг в 1 и проверяем все соседние с ней вершины U. Если расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то необходимо уменьшить его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 . Последний случай возможен тогда и только тогда, когда граф G не связан.

Способом решения задач линейного программирования графическим методом.

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