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

Линейное программирование -
направление математического программирования, изучающее методы решения экстремальных (оптимизационных) задач, которые характеризуются линейной зависимостью между переменными и линейным показателем эффективности.
Критерий эффективности операции (функция цели) - линейная функция нескольких переменных
f (х1, х2,…, хn)= с1х1+ с2х2 + …+ сnхn ;
Условия, которыми должны обладать переменные, определяют некоторую область G, задаваемую системой линейных равенств и/или неравенств (система ограничений).

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

Формы задач линейного программирования
В канонической форме ЗЛП имеет систему ограничений в виде системы линейных уравнений.
При этом переменные задачи х1, х2, ..., хn являются неотрицательными:

Формы задач линейного программирования
В стандартной форме ЗЛП имеет систему ограничений в виде системы линейных неравенств.
При этом переменные задачи х1, х2, ..., хn являются неотрицательными:

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

Пример задачи линейного программирования
Предприятие рекламирует свою продукцию с использованием четырех источников массовой информации: телевидения, радио, Internet и печатной продукции .
Анализ рекламной деятельности в прошлом показал, что эти средства приводят к увеличению прибыли соответственно на 10, 5, 7 и 4 усл. ед., в расчете на 1 усл. ед., затраченную на рекламу. На рекламу выделено 50 000 усл. ед. Администрация предприятия не намерена тратить на телевидение более 40 %, а на радио и Internet— более 50 % от общей суммы выделенных средств. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль?

Составим математическую модель задачи.
Цель – максимизация прибыли с помощью использования рекламы товара.
Управляющие переменные:
х1 – количество средств, вложенных в рекламу на телевидение;
х2 – количество средств, вложенных в рекламу на радио;
х3 – количество средств, вложенных в рекламу в Internet;
х4 – количество средств, вложенных в рекламу в виде печатной продукции

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

Решение данной задачи:
вектор оптимального решения (20000; 20000; 5000; 0) дает оптимальное значение целевой функции 395 000 у.е.
То есть, для получения максимальной прибыли в размере 395 000 усл. ед. надо распределить средства на рекламу следующим образом:
20 000 усл. ед. вложить в рекламу на телевидении;
20 000 усл. ед. вложить в рекламу в Internet;
5000 усл. ед. вложить в рекламу, организованную с помощью печатной продукции;
рекламу на радио организовывать не следует.

Задача линейного программирования с двумя неизвестными может быть решена графически
Замечание:
К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2

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

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

Возможны следующие варианты областей допустимых решений:

2. Построить градиент целевой функции
F = с1х1+с2х2
(вектор нормали к прямой с1х1+с2х2 = F)
Алгоритм графического решения ЗЛП

3. Построить опорную прямую, перпендикулярную вектору нормали – линию уровня целевой функции
Алгоритм графического решения ЗЛП

4. Перемещая опорную прямую в направлении вектора нормали, определить «точку входа» и «точку выхода» (первая встретившаяся опорной прямой точка из ОДР и последняя встретившаяся опорной прямой точка из ОДР соответственно)
В точке входа: F → min
В точке выхода: F → max
Алгоритм графического решения ЗЛП

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

Минимальное значение целевая функция достигает в точке В: Fmin = F(B)
Максимальное значение: Fmax = ∞
Частные случаи

Минимальное значение целевая функция достигает в точке E: Fmin = F(E)
Максимальное значение целевая функция достигает во всех точках отрезка ВС :
Fmin = F(B)= F(C)
Частные случаи

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

Решить графически ЗЛП
2. Построим вектор нормали N(3;4) и перпендикулярную ему опорную прямую

Решить графически ЗЛП
3. Перемещаем опорную прямую в направлении вектора нормали и определяем «точку выхода»
В – точка выхода

Решить графически ЗЛП
4. Точка В - точка пересечения прямых (1) и (3)

Решить графически ЗЛП
5. Для вычисления координат точки В решим систему уравнений: