Случай многих переменных

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

(1.7)

где n-число неизвестных, m – число линейно независимых уравнений системы ограничений.

Если условие (1.7) не выполняется, то задача графическим методом неразрешима.

При выполнении условия (1.7) решение задачи осуществляется в следующей последовательности.

1. Выбираем две любые переменные, которые назовём свободными.

2. Выражаем все остальные переменные через свободные, то есть, решаем систему ограничений задачи.

3. Выражаем целевую функцию через свободные переменные.

4. Полученную двухмерную задачу решаем обычным графическим методом.

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

Пример 3. Найти решение задачи

Р ешение. В качестве свободных переменных примем, например, и . Из уравнений ограничений выразим переменные и через свободные:

Выразим целевую функцию f через свободные переменные и

Опуская неотрицательные переменные и , получаем задачу с двумя переменными

,

Графическое решение задачи показано на Рис.1.8.

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

Таким образом, оптимальный план имеет вид

.

Задачи для решения

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

2.1. 2.2.

2.3 2.4.

2.5. 2.6.

2.7. 2.8.

2.9. 2.10.

2.11. 2.12.

2.13. 2.14.

2.15. 2.16 .

2.17. 2.18.

1.4. Аналитическое решение

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

1.4.1. Различные формы записи задач

линейного программирования

Пусть задача линейного программирования задана в симметричной форме, то есть, ограничения даны в виде неравенств вида (1.2), (1.4). Симметричную задачу можно привести к каноническому виду. Для этого, в левые части неравенств (1.2), вводятся дополнительные (неотрицательные) переменные со знаком плюс, а в левые части неравенств (1.4), при знаке , – со знаком минус. Эти дополнительные переменные называются балансовыми. Тогда все неравенства превращаются в равенства, и задача может быть решена обычными методами линейной алгебры, например, методом Гаусса. Вводимые дополнительные, то есть балансовые, переменные отражают, например, количество неиспользованного ресурса для определённого типа сырья при производстве продукции.

Пример 4.

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

Преобразуем ограничения введением балансовых переменных

Тогда кроме условий добавляются неравенства .

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

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

Пример 5. Преобразовать систему ограничений, данную в канонической форме, к симметрической форме при условии, что и

Решение. В данном случае можно из второго уравнения выразить , а из первого уравнения выразить

.

Затем воспользоваться выражением для

.

Получили решение

Учитывая условия и , можно отбросить переменные и . Тогда, будут справедливы неравенства

, .

То есть, ограничения приведены к симметричной форме.