,

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

; ; ; .

Областью решений неравенств является пятиугольник ABCDE .

Построим вектор .Через начало координат перпендикулярно вектору проведем линию уровня . И затем будем перемещать ее параллельно самой себе в направлении вектора до точки выхода из области допустимых решений. Это будет точка С . Найдем координаты этой точки, решив систему, состоящую из уравнений первой и четвертой прямых:

.

Подставим координаты точки С в целевую функцию и найдем ее максимальное значение Пример. Построить линии уровня и для задачи линейного программирования:

max (min )

Решение. Область допустимых решений – открытая область (рис. 6). Линия уровня проходит через точку В . Функция Z имеет минимум в этой точке. Линию уровня построить нельзя, так как нет точки выхода из области допустимых решений, это значит, что .

Задания для самостоятельной работы .

1. Найти область решений системы неравенств:

а) б)

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

min

3. Составить экономико-математическую модель и решить графически задачу линейного программирования

Фирма выпускает изделия двух видов А и В. Изделия каждого вида обрабатывают на двух станках (I и II). Время обработки одного изделия каждого вида на станках, время работы станков за рабочую смену, прибыль фирмы от реализации одного изделия вида А и вида В занесены в таблицу:

Станки	Время обработки одного изделия, мин.		Время работы станка за смену, мин.
	А	В
I	10	20	1300
II	4	13	720
Прибыль от одного изделия, грн.	0,3	0,9

Изучение рынка сбыта показало, что ежедневный спрос на изделия вида В никогда не превышает спрос на изделия вида А более чем на 40 единиц, а спрос на изделия вида А не превышает 90 единиц в день.

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

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

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

Этот метод включает в себя три основные этапа:

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

2) Правило перехода к лучшему (точнее, нехудшему) решению.

3) Критерий проверки найденного решения на оптимальность.

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

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

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

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

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