Пособие линейное программирование. Пример отсутствия решения

Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу .

Решение происходит в три этапа:

1. Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b (F(X) → extr) сводится к виду ax = b , F(X) → max ;
2. Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
3. Решение симплексным методом;

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 1 2 3 4 5 6 7 8 9 10

Переход от задачи минимизации целевой функции к задаче максимизации

Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .
Проиллюстрируем этот факт графически:

F(x) → min

F(x) → max

Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).

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

Переменные x 1 , …, x m , входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми - в остальные, называются базисными или зависимыми . В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса-Жордана . Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x m +1 ,…, x n) называются небазисными или независимыми переменными .

Базисное решение называется допустимым базисным решением , если значения входящих в него базисных переменных x j ≥0, что эквивалентно условию неотрицательности b j ≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом .
Если среди неотрицательных чисел b j есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной .

Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x 1 + 2x 2 - 2x 3 → min при ограничениях:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x 4 ; во втором неравенстве смысла (≥) вводим базисную переменную x 5 со знаком минус.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Переход к СЗЛП .
Расширенная матрица системы ограничений-равенств данной задачи:

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x 4 .
2. В качестве базовой переменной выбираем x 2 .
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x 2 , получена в результате деления всех элементов строки x 2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(0 3):-2	3-(-2 3):-2	-1-(5 3):-2	1-(0 3):-2	0-(-1 3):-2	10-(3 3):-2
0: -2	-2: -2	5: -2	0: -2	-1: -2	3: -2
1-(0 0):-2	0-(-2 0):-2	2-(5 0):-2	0-(0 0):-2	0-(-1 0):-2	9-(3 0):-2

Получаем новую матрицу:

4	0	6 1 / 2	1	-1 1 / 2	14 1 / 2
0	1	-2 1 / 2	0	1 / 2	-1 1 / 2
1	0	2	0	0	9

3. В качестве базовой переменной выбираем x 3 .
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x 3 , получена в результате деления всех элементов строки x 3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(1 6 1 / 2):2	0-(0 6 1 / 2):2	6 1 / 2 -(2 6 1 / 2):2	1-(0 6 1 / 2):2	-1 1 / 2 -(0 6 1 / 2):2	14 1 / 2 -(9 6 1 / 2):2
0-(1 -2 1 / 2):2	1-(0 -2 1 / 2):2	-2 1 / 2 -(2 -2 1 / 2):2	0-(0 -2 1 / 2):2	1 / 2 -(0 -2 1 / 2):2	-1 1 / 2 -(9 -2 1 / 2):2
1: 2	0: 2	2: 2	0: 2	0: 2	9: 2

Получаем новую матрицу:

3 / 4	0	0	1	-1 1 / 2	-14 3 / 4
1 1 / 4	1	0	0	1 / 2	9 3 / 4
1 / 2	0	1	0	0	4 1 / 2

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1 / 4 x 1 + x 2 + 1 / 2 x 5 = 9 3 / 4
1 / 2 x 1 + x 3 = 4 1 / 2
Выразим базисные переменные через остальные:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4
x 3 = - 1 / 2 x 1 +4 1 / 2
Подставим их в целевую функцию:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
или

Система неравенств:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4 ≥ 0
- 1 / 2 x 1 +4 1 / 2 ≥ 0
Приводим систему неравенств к следующему виду:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 5 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Упростим систему.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 2 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max

Пример №2 . Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) при ограничениях:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(1.1) ;
(1.2)
Здесь , есть произвольные числа. Задача может быть как на нахождение максимума (max), так и на нахождение минимума (min). В системе ограничений могут присутствовать как знаки , так и знаки .

Построение области допустимых решений

Графический метод решения задачи (1) следующий.
Вначале мы проводим оси координат и и выбираем масштаб. Каждое из неравенств системы ограничений (1.2) определяет полуплоскость, ограниченную соответствующей прямой.

Так, первое неравенство
(1.2.1)
определяет полуплоскость, ограниченную прямой . С одной стороны от этой прямой , а с другой стороны . На самой прямой . Чтобы узнать, с какой стороны выполняется неравенство (1.2.1), мы выбираем произвольную точку, не лежащую на прямой. Далее подставляем координаты этой точки в (1.2.1). Если неравенство выполняется, то полуплоскость содержит выбранную точку. Если неравенство не выполняется, то полуплоскость расположена с другой стороны (не содержит выбранную точку). Заштриховываем полуплоскость, для которой выполняется неравенство (1.2.1).

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

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

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

Если хотя бы одно неравенство не выполняется, то выбираем другую точку. И так далее, пока не будет найдены одна точка, координаты которой удовлетворяют системе (1.2).

Нахождение экстремума целевой функции

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

Теперь мы можем искать экстремум целевой функции
(1.1) .

Для этого выбираем любое число и строим прямую
(3) .
Для удобства дальнейшего изложения считаем, что эта прямая проходит через ОДР. На этой прямой целевая функция постоянна и равна . такая прямая называется линией уровня функции . Эта прямая разбивает плоскость на две полуплоскости. На одной полуплоскости
.
На другой полуплоскости
.
То есть с одной стороны от прямой (3) целевая функция возрастает. И чем дальше мы отодвинем точку от прямой (3), тем больше будет значение . С другой стороны от прямой (3) целевая функция убывает. И чем дальше мы отодвинем точку от прямой (3) в другую сторону, тем меньше будет значение . Если мы проведем прямую, параллельную прямой (3), то новая прямая также будет линией уровня целевой функции, но с другим значением .

Таким образом, чтобы найти максимальное значение целевой функции, надо провести прямую, параллельную прямой (3), максимально удаленную от нее в сторону возрастания значений , и проходящую хотя бы через одну точку ОДР. Чтобы найти минимальное значение целевой функции, надо провести прямую, параллельную прямой (3) и максимально удаленную от нее в сторону убывания значений , и проходящую хотя бы через одну точку ОДР.

Если ОДР неограниченна, то может возникнуть случай, когда такую прямую провести нельзя. То есть как бы мы ни удаляли прямую от линии уровня (3) в сторону возрастания (убывания) , то прямая всегда будет проходить через ОДР. В этом случае может быть сколь угодно большим (малым). Поэтому максимального (минимального) значения нет. Задача решений не имеет.

Рассмотрим случай, когда крайняя прямая, параллельная произвольной прямой вида (3), проходит через одну вершину многоугольника ОДР. Из графика определяем координаты этой вершины. Тогда максимальное (минимальное) значение целевой функции определяется по формуле:
.
Решением задачи является
.

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

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

Условие задачи

Фирма выпускает платья двух моделей А и В. При этом используется ткань трех видов. На изготовление одного платья модели А требуется 2 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. На изготовление одного платья модели В требуется 3 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. Запасы ткани первого вида составляют 21 м, второго вида - 10 м, третьего вида - 16 м. Выпуск одного изделия типа А приносит доход 400 ден. ед., одного изделия типа В - 300 ден. ед.

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

Решение

Пусть переменные и означают количество произведенных платьев моделей А и В, соответственно. Тогда количество израсходованной ткани первого вида составит:
(м)
Количество израсходованной ткани второго вида составит:
(м)
Количество израсходованной ткани третьего вида составит:
(м)
Поскольку произведенное количество платьев не может быть отрицательным, то
и .
Доход от произведенных платьев составит:
(ден. ед.)

Тогда экономико-математическая модель задачи имеет вид:

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 7) и (10,5; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 10) и (10; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (8; 0).

Заштриховываем область, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.

(П1.1) .
При .
При .
Проводим прямую через точки (0; 4) и (3; 0).

Далее замечаем, что поскольку коэффициенты при и целевой функции положительны (400 и 300), то она возрастает при увеличении и . Проводим прямую, параллельную прямой (П1.1), максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку четырехугольника OABC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Решение задачи: ;

Ответ

.
То есть, для получения наибольшего дохода, необходимо изготовить 8 платьев модели А. Доход при этом составит 3200 ден. ед.

Пример 2

Условие задачи

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

Решение

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 6) и (6; 0).

Строим прямую .
Отсюда .
При .
При .
Проводим прямую через точки (3; 0) и (7; 2).

Строим прямую .
Строим прямую (ось абсцисс).

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

Заштриховываем область по границам построенных прямых, чтобы точка (4; 1) попала в заштрихованную часть. Получаем треугольник ABC.

Строим произвольную линию уровня целевой функции, например,
.
При .
При .
Проводим прямую линию уровня через точки (0; 6) и (4; 0).
Поскольку целевая функция увеличивается при увеличении и , то проводим прямую, параллельную линии уровня и максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку треугольника АВC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Решение задачи: ;

Ответ

Пример отсутствия решения

Условие задачи

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

Решение

Решаем задачу графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (2,667; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 3) и (6; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (3; 0) и (6; 3).

Прямые и являются осями координат.

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

Заштриховываем область, чтобы точка (3; 3) попала в заштрихованную часть. Получаем неограниченную область, ограниченную ломаной ABCDE.

Строим произвольную линию уровня целевой функции, например,
(П3.1) .
При .
При .
Проводим прямую через точки (0; 7) и (7; 0).
Поскольку коэффициенты при и положительны, то возрастает при увеличении и .

Чтобы найти максимум, нужно провести параллельную прямую, максимально удаленную в сторону возрастания , и проходящую хотя бы через одну точку области ABCDE. Однако, поскольку область неограниченна со стороны больших значений и , то такую прямую провести нельзя. Какую бы прямую мы не провели, всегда найдутся точки области, более удаленные в сторону увеличения и . Поэтому максимума не существует. можно сделать сколь угодно большой.

Ищем минимум. Проводим прямую, параллельную прямой (П3.1) и максимально удаленную от нее в сторону убывания , и проходящую хотя бы через одну точку области ABCDE. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:

Ответ

Максимального значения не существует.
Минимальное значение
.

Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Такие задачи находят обширные приложения в различных сферах человеческой деятельности. Систематическое изучение задач такого типа началось в 1939 – 1940 гг. в работах Л.В. Канторовича.

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

Круг задач, решаемых при помощи методов линейного программирования достаточно широк.Это, например:

задача об оптимальном использовании ресурсов при производственном планировании;

задача о смесях (планирование состава продукции);

задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или);

транспортные задачи (анализ размещения предприятия, перемещение грузов).

Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

математические модели большого числа экономических задач линейны относительно искомых переменных;

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

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

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

Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.

В общем виде модель записывается следующим образом:

целевая функция

(1.1) при ограничениях

(1.2) требования неотрицательности

(1.3) где x j – переменные (неизвестные);

- коэффициенты задачи линейного программирования.

Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3).

Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми.

Вектор, удовлетворяющий ограничениям (1.2) и (1.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (1.1) достигает своего максимального (минимального) значения, называется оптимальным.

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

Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

Допустимым решением (допустимым планом) задачи ЛП, данной в стандартной форме, называется упорядоченное множество чисел (х1, х2, …, хn), удовлетворяющих ограничениям; это точка в n-мерном пространстве.

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

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

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

Опорное решение - это базисное неотрицательное решение. Опорное решение может быть невырожденным и вырожденным. Опорное решение называется невырожденным, если число его ненулевых координат равно рангу системы, в противном случае оно является вырожденным.

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

Решить данные задачи графически, когда количество переменных более 3 весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.

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

С его помощью можно решить любую задачу линейного программирования.

В основу симплексного метода положена идея последовательного улучшения получаемого решения.

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

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

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

способ определения какого-либо первоначального допустимого базисного решения задачи;

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

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

Симплексный метод включает в себя ряд этапов и может быть сформулирован в виде четкого алгоритма (четкого предписания о выполнении последовательных операций). Это позволяет успешно программировать и реализовывать его на ЭВМ. Задачи с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.

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

Задачи линейного программирования можно решить следующими методами:

алгоритмом Флойда;

алгоритм Дейкстры на графах;

графический метод;

метод симплекс-таблиц и др.

Алгоритм решения задач линейного программирования методом Дейкстры на графах.

В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U - массив булевых переменных.

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

На каждом шаге цикла необходимо найти вершину U с минимальным расстоянием и флагом равным нулю. Затем нужно установить в ней флаг в 1 и проверяем все соседние с ней вершины U. Если расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то необходимо уменьшить его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0. Последний случай возможен тогда и только тогда, когда граф G не связан.

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

Графический метод решения задачи линейного программирования основан на геометрической интерпретации задачилинейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задачтрёхмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трёх изобразить графически вообще невозможно.

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

Минимальное значение функции определено формулой (1).

(1)

Ограничения представлены формулами (2) и (3).

(2)

(3)

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

Линейная функция (1) при фиксированных значениях Z является уравнением прямой линии:

Необходимо построить многоугольник решений системыограничений (2) и графиклинейной функции(1) при Z=0. Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию:

Найти точку многоугольника решений, в которой прямая
опорная и функция Z при этом достигает минимума.

Значения
уменьшаются в направлениивектора
, поэтому прямую Z=0 необходимо передвигать параллельно самой себе в направлении вектора N.

Если многоугольникрешений ограничен, то прямая дважды становится опорной по отношению к многоугольнику решений (в точкахB и E), причём минимальное значение принимает в точке E. Координаты точки
необходимо найти, решая систему уравнений прямых DE и EF.

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

Случай 1. Прямая
, передвигаясь в направлении вектораN или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функцияне ограничена на многоугольнике решений как сверху, так и снизу.

Случай 2. Прямая, передвигаясь, всё же становится опорной относительно многоугольника решений. Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху.

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

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

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

Рисунок 1 – Начальное преобразование системы ограничений

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X1, X2, ..., Xr и что при этом b1, b2,..., br ≥ 0 (соответствующее базисное решение является опорным).

Для составления симплекс-таблицы во всех равенствах в условии задачи члены, содержащие переменные, переносятся в левую часть, свободные оставляются справа, т.е. задача записывается в виде системы равенствкак показано на рисунке 2.

Рисунок 2 – Преобразование системы неравенств

Алгоритм перехода к следующей таблице такой:

просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

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

среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой он находится ключевой;

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

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

строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.

в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.

столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же.

в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы, как показано на рисунке 3.

Рисунок 3 – Составление нового элемента в симплекс-таблице

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

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

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

После анализа собранной информации, была составлена задача линейного программирования по цеху №8 в ОАО «НефАЗ».На покрасочном конвейере, на котором окрашиваются детали. Необходимо покрасить оптимальное количество деталей за одну рабочую смену, чтобы прибыль была максимальной.

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

Симплекс - метод представляет собой итеративную процедуру решения задач ЛП, в каноническом виде (любую задачу ЛП можно привести к каноническому виду:

Всего в задаче будет n+m переменных.

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

Пример 1.

Решим задачу:

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

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

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

1). Получим на первом шаге:

Базисные переменные	Не базисные переменные
х 3 , х 4 х 5 х 6

Выразим неосновные переменные через основные:

(*)

Получим базисное решение системы Х 1 =(0; 0; 18; 16; 5; 21). Если сравнить с графическим решением этой задачи, то Х 1 соответствует точке О(0;0) многоугольника ОАВСДЕ (см. рис. 1).

Так как это решение допустимое, нельзя исключать, что оно оптимальное.

,z(X 1)=0.

Функцию z можно увеличить за счет неосновной переменной (обе они входят в уравнение с коэффициентом >0). Это можно осуществить, перейдя к новому допустимому базисному решению, в котором одна из этих переменных станет основной. Если новое решение будет вырожденным, то целевая функция сохранит свое значение. Геометрически это переход к другой соседней вершине, в которой целевая функция будет по крайней мере не хуже. В рассматриваемой задаче можно переводить в базисные переменные как х 1 так и х 2 , так как обе входят в целевую функцию со знаком «+».

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

Система ограничений (*) накладывает ограничения на рост х 2 , так как необходимо сохранять допустимость решения (все переменные должны быть »0). Поэтому следующие неравенства должны быть выполнены при х 1 =0:

Любое уравнение системы (*) (кроме последнего) определяет оценочное отношение – границу роста переменной х 2 , сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при х 2 , если они имеют разные знаки. Так как в последнее ограничение х 2 не входит (входит с коэффициентом 0), то рост х 2 не ограничен, х 2 <∞. Будем так же считать, сто граница переменной х 2 равно ∞, если коэффициент перед х 2 и свободный член имеют одинаковые знаки. Нет ограничений на рост х 2 и в том случае, если свободные член равен 0. Но если при этом коэффициент при х 2 отрицательный, то рост этой переменной ограничен 0.

Так как неотрицательность должны сохранять все переменные, по новая базисная переменная х 2 =min(6; 16; 5; ∞)=5. Уравнение, которое соответствует минимальной оценке, называется разрешающим. В этом примере – это третье уравнение

Следовательно, переменная х 5 =0 и переходит в небазисные переменные.

2). Получим на втором шаге:

Базисные переменные	Не базисные переменные
х 3 , х 4 х 2 х 6

Из третьего уравнения системы выразим:х 2:

Подставляя правую часть равенства во все остальные уравнения вместо х 2 получим:

Получим новое базисное решение системы Х 2 =(0; 5; 3; 11; 0; 21). Это соответствует точке А(0;5) многоугольника ОАВСДЕ (см. рис. 1).

Выразим целевую функцию через неосновные переменные:
,z(X 2)=15.

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

х 1 =min(∞; 13; 11/2; ∞)=3, следовательно второе уравнение разрешающее и х 3 выводится из базиса.

3). Получим на третьем шаге:

Базисные переменные	Не базисные переменные
х 1 , х 4 х 2 х 6

Из второго уравнения системы выразим:х 1:

Подставляя правую часть равенства во все остальные уравнения вместо х 1 получим:

Получим новое базисное решение системы Х 3 =(3; 5; 0; 5; 0; 12). Это соответствует точке В(3;5) многоугольника ОАВСДЕ (см. рис. 1).

Выразим целевую функцию через неосновные переменные:
,z(X 3)=21.

Аналогично первым двум шагам введем в базисные переменные х 5 .

х 5 =min(∞; 5; 1;4/3)=1, следовательно, третье уравнение разрешающее и х 4 выводится из базиса.

4). Получим на четвертом шаге:

Базисные переменные	Не базисные переменные
х 1 , х 5 х 2 х 6

Из третьего уравнения системы выразим:х 5:

Подставляя правую часть равенства во все остальные уравнения, вместо х 5 получим:

Получим новое базисное решение системы Х 4 =(6; 4; 0; 0; 1; 6). Это соответствует точке С(6;4) многоугольника ОАВСДЕ (см. рис. 1).

Выразим целевую функцию через неосновные переменные: ,z(X 4)=24.

Целевую функцию нельзя улучшить переходя к другому базисному решению, так как все коэффициенты при небазисных переменных меньше 0, следовательно, задача решена. Максимальная прибыль при этом равна 24, а оптимальный план производства: 6 единиц первой продукции и 4 единицы второй продукции. Дополнительные переменные показывают разницу между затратами ресурсов каждого вида и их потреблением. х 3 =х 4 =0, следовательно ресурсы S 1 иS 2 расходуются полностью в процессе производства, а остатки S 3 иS 4 равны 1 и 3 соответственно.

На практике расчеты при решении задач симплекс-методом выполняются с помощью симплекс-таблиц. Рассмотрим алгоритм симплекс-метода с использованием симплекс-таблиц.

Алгоритм симплекс - метода:

Определяем . Если конечного минимума нет, то задача не имеет конечного оптимума (z max =). Если минимум конечен, то выбираем строку q, на которой он достигается (если их несколько, то любую), и называем ее разрешающей строкой. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент a qs .

Переходим к следующей таблице по правилам (преобразования Гаусса-Жордана или правило прямоугольника):

1. в левом столбце записываем новый базис: вместо основной переменной x q – переменную x s ;

   в столбцах, соответствующих базисным переменным, проставляем нули и единицы: 1- на пересечении строки и столбца, соответствующих одной и той же базисной переменной; 0 – во всех других позициях столбцов базисных переменных;

   Новую строку q получаем из старой делением на разрешающий элемент a qs ;

   все остальные элементы а ij " вычисляем по правилу:

(2)

Пример 6.

Решим задачу:

Приведем систему ограничений к каноническому виду. Получим расширенную систему:

Целевую функцию представим в виде z-2x 1 -3x 2 =0.

Базисными переменными будут являться дополнительные переменные x 3 ,x 4 ,x 5 ,x 6 .

Заполним первую симплекс-таблицу:

	Свободный член	Переменные						Оценочные отношения

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

Находим оценочные отношения и выбираем из них минимальное (=5). Следовательно, q=3, переменная х 5 является выводимой из базиса, а соответствующая ей строка – разрешающей.

в новом базисе основные переменные x 3 ,x 4 ,x 2 ,x 6 ;

расставляем 0 и1; например, на пересечении столбца и строки, соответствующих переменной х 3 ставим 1, а остальные элементы столбца х 3 равны 0 и т.д. Третья строка получается делением на разрешающий элемент а 33 =1. Остальные клетки таблицы заполняем по формулам (2). Например:

Получаем вторую симплекс таблицу:

	Свободный член	Переменные						Оценочные отношения

Критерий оптимальности вновь не выполнен. Теперь разрешающий первый столбец и х 1 – вводимая переменная. Считаем оценочные отношения и находим разрешающую строку – первая и выводимую из базиса переменную – х 3 . Разрешающий элемент а 11 .

Переходим к новой симплекс-таблице:

	Свободный член	Переменные						Оценочные отношения

И на этот раз критерий оптимальности не выполнен.

Выводимая переменная х 4 ; вводимая х 5 . Переходим к новой таблице.

	Свободный член	Переменные						Оценочные отношения

Критерий оптимальности выполнен, значит z max =24. Оптимальное решение (6; 4; 0; 0; 1; 3).