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

Графический метод. Он успешно используется для решения задач линейного программирования, когда число ограничитель­ных уравнений меньше числа элементов решения на два [3]..

Полагаем, что целевая функция имеет вид

Дана система ограничительных уравнений

Предположим, что свободными переменными являются x₁ и x₂. Выразив базисные переменные через свободные переменные, получим

(3.5)

Элементы решения являются положительными, поэтому об­ласть решения будет лежать в первом квадрате (рис. 3.2).

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

Положим х₃ = 0, тогда γ₁₃x₁ + γ₂₃x₂— β₃/γ₃ = 0.

Найдем отрезки х₁ и х₂, отсекаемые прямой на осях oх₁ и ох₂, положив х₁ = 0, а затем х₂ = 0, х₁ = β₃/γ₁₃γ₃, х₂ = Рз/β₃/γ₂₃γ₃.

Отметим на рис. 3.2- штриховкой ту сторону прямой, по ко­торую x₃ > 0. Учтем, что коэффициенты могут быть и отрица­тельными и положительными, однако x_i всегда положительны.

Затем полагаем х₄ = 0 из второго уравнения (3.5) и снова проводим прямую и штриховкой отмечаем область, где х₄ > 0 и т. д. Получаем область допустимых решений (ОДР), она всегда выпукла.

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

где γ₁*, γ₂* — результирующие значения коэффициентов при свобод­ных переменных; D*—свободный член.

Преобразуем целевую функцию к виду К* = γ₁*x₁ + γ₂*x₂, где K*=K-D*.

•Рис. 3.2. Графический метод решения задач линейного программирования

Рис. 3.3. График, поясняющий решение задачи методом линейного программи­рования

Очевидно, в зависимости от значения переменных х₁ и x₂ экстре­мум для .K* и K—D* будет одним и тем же. Если положить K*= 0, то получим уравнение прямой, проходящей через начало координат: γ₁*x₁ + γ₂*x₂= 0.

Эту прямую называют основной. Она имеет угловой коэффи­циент К_у = —γ₁*/γ₂*. Заметим, что угловой коэффициент прямой не изменится, если прямая не проходит через начало координат. Следовательно, придавая различные значения K*, мы будем «перемещать» основную прямую параллельно самой себе.

Построим основную прямую на графике (рис. 3.2) и начнем перемещать её в ОДР параллельно самой себе в сторону убы­вания К*, т. е. ищем минимальное значение целевой функции. Одна из вершин области или граница, которую пересечет основ­ная прямая, дает оптимальное решение [2].

Таким образом, решение может быть единственным, если основная прямая пересекает одну вершину, или множество ре­шений, если она пересекает границу ОДР.

Пример. Рассмотрим поставленную задачу о комплектах про­водов при следующих данных: С₁ =2; С₂ = 3; а₁₁ = 2; a₁₂ = l; a₂₁ = 1; а₂₂ = 2; b₁ = 8; b₂ = 6.

Обозначим количество комплектов проводов первого и вто­рого видов через х₁ и х₂ — соответственно.

Целевая функция, минимизирующая затраты, имеет вид:

K = 2x₁ +3x₂ → min.

Составим ограничительные уравнения, 2x₁ +x₂ ≥ 8; x₁≥ 0, x₂ ≥ 0, x₁ + 2x₂ ≥ 6, или у₁ =2x₁ +x₂ — 8; у₂ = x₁ + 2x₂ — 6. Построим график ограничительных прямых у₁ =0 и у₂ =0 (рис. 3.3).

Первая прямая отсекает отрезки на осях x₁ и x₂ соответственно равные 4 и 8.

Вторая прямая отсекает отрезки, равные 6 и 3. Найдем угловые коэффициенты прямых у_k1 = — 2; у_k2 = —0,5; у_kоп = —2/3.

Находим вершину А. Оптимальным решением является x₁ = 3,5, x₂ = 1,5. Другие вершины не дают оптимального решения,

так как основная прямая пересекает в ОДР первой вершину А. Следовательно, К = 2x₁ +3x₂ = 2 * 3,5 + 3.*1,5 = 11,5.

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

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

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

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

.

 

Целевая функция имеет вид

.

ее решение через свободные переменные

.

Положим равными нулю все свободные переменные, тогда К = D. Это и будет оптимальным решением, если γ₁* и γ₂* являются положительными, так как любое увеличение х приводит к уве­личению K, а это ухудшает решение.

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

В данном случае поступают следующим образом: наиболее критичные свободные переменные переводят в разряд базисных, а базисные — в разряд свободных. Затем вновь полученные зна­чения переменных нужно подставить в целевую функцию. Такую замену продолжают до тех пор, пока все коэффициенты целе­вой функции станут положительными. Заметим, что при задаче максимизации целевой функции они все должны быть отрица­тельными, так как задача максимизации отличается от задачи минимизации умножением целевой функции на—1.

Пример. Минимизировать целевую функцию К = С₁x₁ + С₂х₂ → min при известных ограничениях

Приведем ограничения к стандартному виду

Положим x₁ и x₂ = 0, тогда у₁ = 5, у₂ = 3. Целевая функция К = 0, но x₂ имеет отрицательный коэффициент, поэтому K = 0 не есть оптимальное решение. Найдем критические переменные.

Такой переменной является x₂. При x₁ = 0 у₁ обращается в нуль только при значении x₂ = 1,25, а при втором уравнении y₂ обращается в нуль только при x₂=1,5. Следовательно, более критичным является x₂ первого уравнения.

Переведем x₂ первого уравнения в базисную переменную, а у₁ — в свободную переменную. Следовательно, мы перешли к новому базису.

Составим новую систему ограничительных уравнений:

Подставим x₂ во второе уравнение:

Запишем целевую функцию через новые свободные перемен­ные. Найдем x₁ из этого уравнения: x₁ = — 2у₂ + у₁ + 1. Под ставим его в первое уравнение: x₂ = — 1.5у₂ + 0,5у₁ + 2. Введем значения х₁ и x₂ в целевую функцию:

При у₁ = 0, у₂ = 0 K = — 2. Следовательно, x₁ = 1, x₂ = 2.