Доказательство. Пусть максимальное значение функции f достигается в точ­ках ,т

Пусть максимальное значение функции f достигается в точ­ках ,т. е. . Рассмотрим произвольную выпуклую комбинацию этих точек

где (1.11)

Найдем значение целевой функции в точке х^*

(1.12)

Итак, для произвольной выпуклой комбинации х^* точек справедливо равенство

f(x^*)=cx^*=f^* ▲ (1.13)

Теорема 1.3. Каждый допустимый базисный план яв­ляется угловой точкой множества допустимых пла­нов D.

12. Каноническая форма задачи линейного программирования.

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

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

Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:

Ø ограничения в виде неравенств преобразуются в уравне­ния за счет добавления фиктивных неотрицательных переменных , которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;

Ø переменные, на которые не наложено условие неотрица­тельности, представляются в виде разности двух новых неотрицательных переменных:

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

и множеством допустимых планов D, определенным системой уравнений и неравенств,

Тогда в соответствии со сформулированными правилами эк­вивалентная каноническая задача будет иметь вид ,где:

а множество определено как:

Нетрудно заметить, что «платой» за переход от общей фор­мы задачи линейного программирования к канонической явля­ется рост ее размерности, что, при прочих равных условиях, является фактором, усложняющим процесс решения.

13. Сведение общей задачи линейного программирования к каноническому виду.

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

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

Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:

Ø ограничения в виде неравенств преобразуются в уравне­ния за счет добавления фиктивных неотрицательных переменных , которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;

Ø переменные, на которые не наложено условие неотрица­тельности, представляются в виде разности двух новых неотрицательных переменных:

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

и множеством допустимых планов D, определенным системой уравнений и неравенств,

Тогда в соответствии со сформулированными правилами эк­вивалентная каноническая задача будет иметь вид ,где:

а множество определено как:

Нетрудно заметить, что «платой» за переход от общей фор­мы задачи линейного программирования к канонической явля­ется рост ее размерности, что, при прочих равных условиях, является фактором, усложняющим процесс решения.

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

Графический метод используется для решения задач с двумя переменными следующего вида:

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

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

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

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

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

Для нахождения среди допустимых решений оптимального решения используют линии уровня и опорные прямые.

Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение линии уровня в общем случае имеет вид . Все линии уровня параллельны между собой. Их нормаль n = (c₁,с₂).

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

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

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

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

1. Построить область допустимых решений

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

3. Если область допустимых решений является не пустым множеством, построить нормаль линий уровня n = (c₁,с₂) и одну из линий уровня, имеющую общие точки с этой областью.

4. Линию уровня переместить до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум – в противоположном направлении.

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

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

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

Симплексом в n-мерном пространстве называют фигуру, содержащую n+1 вершину. На плоскости – это треугольник, в трехмерном пространстве – тетраэдр и т.д.

Симплекс-метод представляет собой направленный перебор угловых точек допустимого множества решений в сторону приближения к искомой точке экстремума.

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

Базисом опорного решения называется базис системы векторов условий задачи, включающий в свой состав векторы, соответствующие отличным от нуля координатам опорного решения.

Канонический вид:

Алгоритм составления симплексных таблиц:

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

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

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