Линейное программирование (Графический метод. Симплексный метод) (стр. 8 )

Этап 5 Строим вектор . Вектор =(2;3) перпендикулярен исходной линии уровня и указывает направление, в котором эта функция возрастает с наибольшей скоростью.

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

Этап 7 Определяем координаты точки B и вычисляем значение целевой функции в этой точке. Точка B лежит на пересечении прямых (I) и (II). Для нахождения координат точки В решим систему уравнений

В результате решения системы уравнений найдены координаты точки В(3;4). Подставим координаты этой точки в выражения для целевой функции и получим максимальное её значение .

Ответ: при х1=3, х2=4.

Экономическая интерпретация полученных результатов выглядит следующим образом: необходимо выпускать 3 изделия вида П1 и 4 изделий вида П2 . В этом случае предприятие получит максимальную прибыль в размере 18 ден. ед.

Вопросы:

1)  Дайте определение выпуклой линейной комбинации точек евклидова пространства?

2)  Какое множество называется выпуклым?

3)  Какая точка выпуклого множества называется угловой?

4)  Сформулируйте основную теорему линейного программирования?

5)  Как геометрически интерпретируются неравенства системы ограничений задачи линейного программирования, система неравенств, целевая функция?

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

Упражнения

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

10  ; .	11  ; .
12  ; .	13  ; .
14  ; .	15  ;	16  ;

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

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

Рассмотрим каноническую форму задачи линейного программирования.

Кроме того, для этой формы должно выполняться требование неотрицательности свободных членов системы уравнений .

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

Если перенести в правые части уравнений все слагаемые, содержащие неизвестные , то система примет вид

Неизвестным данной системы уравнений можно придавать любые значения, и поэтому они называются свободными. Неизвестные соответствующие базисным столбцам, называются базисными.

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

Допустимым базисным решением является решение, содержащее m основных (базисных) переменных и n-m неосновных (небазисных или свободных) переменных. Неосновные переменные в базисном решении равны нулю. Основные переменные, как правило, больше нуля.

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

1 Построение начального опорного плана.

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

Помним, что мы рассматриваем случай, когда .

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

В целевую функцию дополнительные переменные вводят с коэффициентами равными нулю: , т. е.

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

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

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

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