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

Лекция 2

графический метод нахождения оптимального решения

1. Формы линейных математических моделей и их преобразование 
2. Графический метод решения задачи линейного программирования
3. Особые ситуации графического решения ЗЛП
4. Графическое решение экономических задач линейного программирования  

 

1. Формы линейных математических  моделей и их преобразование

 

Математическая модель задачи линейного программирования (ЗЛП) может быть записана в одной из трех форм.

В общей форме математической модели требуется найти максимум или минимум целевой функции; система ограничений содержит неравенства и уравнения; не все переменные могут быть неотрицательными.

В канонической форме математической модели требуется найти максимум целевой функции; система ограничений состоит только из уравнений; все переменные неотрицательны.

В стандартной форме математической модели требуется найти максимум или минимум функции; все ограничения являются неравенствами; все переменные неотрицательны.

 

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

Множество допустимых решений называют областью допустимых решений ЗЛП.

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

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

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

Переход к канонической форме записи ЗЛП.

Пример.

Запишем задачу в канонической форме, вводя в левую часть первого неравенства системы ограничений дополнительную (балансовую) переменную со знаком «+», а в левую часть второго неравенства дополнительную переменную   со знаком  «минус».

   

Экономический смысл различных дополнительных переменных может быть не одинаков: он зависит от экономического смысла ограничений, в которые эти переменные входят.

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

 

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

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

найти наибольшее и наименьшее значения функции

                                                                                

при ограничениях

                                                                   

                                             .                                      

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

Для линейной функции координатами градиента являются коэффициенты при переменных и : . Градиент показывает направление возрастания целевой функции.

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

Решение системы линейных неравенств (3.2) называется допустимым, если его координаты неотрицательны , .

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

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

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

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

1. Построить область допустимых решений (ОДР) задачи в соответствии с системой неравенств .
2. Если область допустимых решений непустая, то можно говорить о целесообразности нахождения оптимального решения ЗЛП.

 

        

 

                                                         В

 

 

 

 

    A

 

 

 

                                   

 

                                                                                       

 

Рисунок 1 – Графический метод решения задачи

 

3. Строим для целевой функции градиент и фиксированную линию уровня – прямую .
4. Параллельным перемещением прямой в направлении вектора найдем первую точку «встречи» прямой с областью. Это – точка минимума целевой функции . Значение функции является наименьшим значением функции в ОДР.
5. Найдем последнюю точку встречи прямой с ОДР. Это - точка максимума целевой функции . Значение функции является наибольшим значением целевой функции в области допустимых решений.

 

3. Особые ситуации графического решения ЗЛП

 

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

1. задача имеет бесконечное множество оптимальных  решений – экстремум функции достигается на отрезке (альтернативный оптимум) – рисунок 2;
2. задача не разрешима из-за неограниченности ОДР, или – рисунок 3;
3. ОДР - единственная точка А, тогда ;
4. задача не разрешима, если ОДР есть пустая область.

 

          

                                                                   

 

                                        В

                                                                                   

 

 

        

                                                                                       А      

                                                  

                                                                 

 

                   Рисунок 2                                               Рисунок 3

 

Если линия уровня параллельна стороне области допустимых решений, то экстремум достигается во всех точках стороны . Задача имеет бесчисленное множество оптимальных решений – альтернативный оптимум. Оптимальное решение находится по формуле

                                ,           

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

 

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

Эту задачу рекомендуется решить студентам самостоятельно.

 

 

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

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

1. Составление математической модели задачи.
2. Решение задачи графическим методом (если ЗЛП имеет стандартную модель с двумя переменными).
3. Анализ оптимального решения:

• экономическое истолкование компонент в оптимальном решении и значения функции и ;

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

 

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

При составлении суточного рациона кормления скота можно использовать свежее сено не более 50 кг и силос не более 85 кг. Рацион должен содержать не менее 30 кормовых единиц, 1000 г белка, 100 г кальция и 80 г фосфора.

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

 

В таблице приведены данные о содержании указанных компонентов в 1 кг каждого корма и себестоимость этих кормов.

 

Таблица – Исходные данные задачи о рационе

Корм	Компоненты				Себестоимость, ден. ед.
	кормовые единицы	белок, г/кг	кальций, г/кг	фосфор, г/кг
Сено свежее, кг	0,5	40	1,25	2	1,2
Силос, кг	0,5	10	2,5	1	0,8

 

Этап 1. Составление математической модели задачи

Введем переменные и - количество кг сена и силоса, которое предполагается включить в рацион. Естественно, что , . Из условия задачи следует, что (кг); (кг).

Количество кормовых единиц в рационе можно выразить суммой , что должно быть, по условию, не меньше 30: (ед.), или .

Ограничения по содержанию в рационе белка, кальция и фосфора имеют вид:  

(г), или  (для белка);

(г), или  (для кальция); 

(г) (для фосфора).

Себестоимость рациона в принятых обозначениях можно выразить формулой (руб.).

Итак, математическая модель задачи построена.

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

и при которых целевая функция принимает наименьшее значение

.

 

 

Этап 2. Графическое решение стандартной ЗЛП

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

                

 

                    

                                      

                 

 

                       

        

                                                        

 

                                     

 

                       |                  |                                            

                                     

 

                                                               

Рисунок 3.9 – Графическое решение задачи о рационе

 

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

В точке целевая функция принимает наименьшее значение, равное .

Оптимальное решение , при котором

 

Этап 3. Анализ оптимального решения

Оптимальный рацион составляет 20 кг сена и 40 кг силоса, при этом себестоимость минимальная и составляет 56 ден. ед.

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

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

 

 

Вопросы для самоконтроля

1. Запишите задачу линейного программирования в общей форме.
2. Запишите задачу линейного программирования в канонической и стандартной формах.
3. С помощью каких преобразований можно перейти от общей или стандартной формы задачи линейного программирования к канонической?
4. Дайте определение допустимого и оптимального решений задачи линейного программирования.
5. Какое из решений и является «лучшим» для задачи минимизации функции , если ?
6. Какое из решений и является «лучшим» для задачи максимизации функции , если ?
7. Запишите стандартную форму математической модели задачи линейного программирования с двумя переменными.
8. Как построить полуплоскость, заданную линейным неравенством с двумя переменными ?
9. Что называется решением системы линейных неравенств с двумя переменными? Постройте на плоскости область допустимых решений такой системы линейных неравенств, которая:
1. имеет единственное решение;
2. имеет бесконечное множество решений;
3. не имеет ни одного решения.
10. Запишите для линейной функции вектор градиент, назовите вид линий уровня. Как расположены относительно друг друга градиент и линии уровня?
11. Сформулируйте алгоритм графического метода решения стандартной ЗЛП с двумя переменными.
12. Как найти координаты решения и значения , ?
13. Постройте область допустимых решений, градиент и линии уровня , для задач линейного программирования, в которых:
1. достигается в единственной точке, а - на отрезке ОДР;
2. достигается в единственной точке ОДР, а .
14. Дайте геометрическую иллюстрацию ЗЛП, если она:
1. имеет единственные оптимальные решения для и ;
2. имеет множество оптимальных решений для .