LP

Линейное программирование
Определение

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

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

Линейное программирование
6) Построить вектор направления (градиент целевой функции). Начало – в точке с координатами (0; 0), конец – в точке, координаты которой являются коэффициентами целевой функции;
7) Провести линию уровня функции, перпендикулярную градиенту. Для этого построить прямую из семейства целевых функций, приравняв выражение целевой функции к нулю;
8) Найдем точку оптимального решения. Для этого параллельным переносом перенесем линию уровня, соответствующую целевой функции по направлению вектора направлений до касания с множеством допустимых решений. Точки касания являются точками экстремума. Для максимума – самая последняя точка допустимой области; для минимума – начальная точка допустимой области;
9) Найдем координаты точки экстремума. Для этого решим систему уравнений, содержащую уравнения прямых, которые пересекаются в этой точке;
10) Полученную точку подставим в уравнение целевой функции и найдем экстремум функции.

Линейное программирование
Виды областей допустимых решений :
Примеры:

Линейное программирование
Если область допустимых решений ограничена, то:
максимум целевой функции находится в одной точке
2) максимальное значение целевой функции находится на ребре MN, то есть в любой точке этого отрезка
В случае, когда область допустимых значений является неограниченной могут встретиться 3 варианта:
1) целевая функция имеет экстремум
2) целевая функция неограниченна
3) задача линейного программирования не имеет решения, так как система ограничений несовместна

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

Областью решений задачи линейного программирования является пересечение всех решений ограничения (*). Пересечением полученных полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенств системы (*) ограничений задачи.
Обозначим границы области многоугольника решений АВС

Линейное программирование
Графическим методом решить задачи линейного программирования:
3) Задача технического контроля:
В отделе технического контроля (ОТК) некоторой фирмы работают контролеры разрядов 1 и 2. Нормы выработки ОТК за 8-часовой рабочий день составляет не менее 1800 изделий.
Контролер разряда 1 проверяет 25 изделий в час, причем не ошибается в 98% случаев. Контролер разряда 2 проверяет 15 изделий в час; его точность составляет 95%.
Заработная плата контролера разряда 1 равна 4 грн. в час, контролер разряда 2 получает 3 грн. в час. При каждой ошибке контролера фирма несет убыток в размере 2 грн. Фирма может использовать 8 контролеров разряда 1 и 10 контролеров разряда 2. Руководство фирмы хочет определить оптимальный состав ОТК, при котором общие затраты на контроль будут минимальны.

Линейное программирование

Линейное программирование
В системе уравнений (7) число переменных (неизвестных) n больше, чем число уравнений m. Будем считать, что ранг этой системы равен m (система избыточна) и система совместна. Тогда m переменных из общего числа n образуют базисные переменные, а остальные (n-m) – свободные переменные.
Система в этом случае будет иметь бесчисленное множество решений, так как свободным переменным можно придавать любые значения, для которых определяют базисные переменные.
Определение
Решение системы уравнений (7) называют базисным, если все
свободные переменные равны нулю.
Базисное допустимое решение соответствует крайним точкам выпуклого многогранника, образованного множеством допустимых решений, то есть грани или вершине этого многогранника.
Целевая функция задачи линейного программирования описывает уравнение плоскости (или гиперплоскости для числа переменных больше трех). Решение задачи линейного программирования лежит в вершинах выпуклого многогранника или на его гранях.

Линейное программирование
Для решения задачи линейного программирования в 1949 году американским математиком Дж.Данцигом был разработан симплекс-метод.
Определение

Линейное программирование
Определение

Линейное программирование
Лемма 1
Доказательство
Ч.Т.Д.

Линейное программирование
Доказательство
Ч.Т.Д.
Лемма 2

Теорема
Доказательство
На основании леммы 1 имеем:
Ч.Т.Д.
Теорема
Доказательство
Ч.Т.Д.

Доказательство
Теорема

Ч.Т.Д.

Линейное программирование
ОПИСАНИЕ СИМПЛЕКС МЕТОДА
СИМПЛЕКС
ТАБЛИЦА

Линейное программирование
Алгоритм 1 решения невырожденной задачи линейного программирования

Линейное программирование
Замечание

Линейное программирование
Замечание

Линейное программирование
Теорема
Доказательство:

Линейное программирование
Ч.Т.Д.
Замечание

Линейное программирование
Алгоритм 2 решения вырожденной задачи линейного программирования

Линейное программирование
Замечание
На практике алгоритм 2 используется редко, поскольку он требует значительно больше времени для решения задачи линейного программирования по сравнению с алгоритмом 1, а зацикливание процесса решения вырожденной задачи алгоритмом 1 мало вероятно. Если же при решении задачи алгоритмом 1 произошло зацикливание, то следует использовать алгоритм 2 для получения нового базисного решения и дальше продолжить решение задачи с помощью алгоритма 1.
Пример решения задачи линейного программирования симплекс-методом:
Решение: