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

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(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. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:

Ответ

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

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

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

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

1. В задаче должен быть четко сформулирован и количественно определен критерий оптимальности, что не так легко сделать на практике. О работе предприятия чаще всего судят по ряду показателей: объему производства, ассортименту и качеству выпускаемой продукции, рентабельности производства и др. Выбор одного критерия может оказаться далеко не лучшим с точки зрения другого и наоборот.
2. Важной составной частью задачи линейного программирования являются ограничения, связанные с наличными ресурсами, потребностями или другими факторами. В реальной экономике не всегда можно учесть взаимодействие слишком большого количества факторов, поэтому составляется упрощенная модель, которая бы более близко отражала действительный характер.
3. Линейное программирование предполагает выбор вариантов и оно применимо только тогда, когда конкретные условия экономической задачи обусловливают эту свободу выбора.
4. Модель должна содержать только линейные уравнения или неравенства, т.е. все переменные задачи должны быть в первой степени. Реальные экономические зависимости не всегда носят линейный характер.

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

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

1. Универсальные методы. С их помощью могут решаться любые задачи линейного программирования. Самым распространенным из них является симплексный метод , предложенный Дж. Данцигом, метод раз- решаюших множителей , разработанный академиком Л. В. Канторовичем в 1939 г., примерно за 10 лет до его появления за рубежом.
2. Специальные методы. Эти методы проще универсальных, но применимы не для всех задач. К ним относятся распределительный метод для решения транспортной задачи, метод разрешающих слагаемых А. Л. Лурье, метод дифференциальных рент А. Л. Брудно, венгерский метод.

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

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

Пример 2.21

Имеется вспомогательное производство, которое использует остающиеся от основного производства материалы. На данном производстве налажен выпуск дверей различного ассортимента: с использованием стекла (ассортимент ЛВС) и без него (ассортимент ДВ). Сбыт данной продукции обеспечен, т.е. продукция может производиться в любых соотношениях, но есть ограничение по количеству рабочих мест в цехе и ресурсам основных материалов. Задача состоит в том, чтобы запланировать цеху ежемесячный выпуск продукции, обеспечивающий наибольшую возможную сумму прибыли.

В задаче не ставится условия обязательного использования всего объема ресурсов. Необходимо, чтобы расход рабочего времени был не больше заданных пределов.

Рассмотрим программу 1, которая предполагает выпуск только дверей ассортимента ДВ, нс используя при этом стекло для их производства.

Если выпускать только ДВ, используя при этом все имеющиеся ресурсы, то их хватит для выпуска:

- по рабочему времени: 520/9,2 = 56 (шт.);
- древесине: 24/0,3 = 80 (шт.).

Следовательно, всех ресурсов достаточно для выпуска только 56 дверей.

Прибыль при данном выпуске составит 168 000 руб. (56 3000).

Программа 2 предполагает выпуск только дверей ассортимента ЛВС. В данном случае ресурсов хватит для выпуска:

- но рабочему времени: 520/4 = 130 (шт.);
- древесине: 24/0,6 = 40 (шт.);
- стеклу: 40/2 = 20 (шт.).

Оптимально возможен выпуск только 20 дверей ЛВС, что ограничивается наличием стекла. При этом уйдет 12 м древесины, из оставшейся части возможен еще выпуск 40 шт. дверей ассортимента ДВ. На производство 20 шт. ДВС и 40 шт. ДВ будет потрачено 448 чел.-ч.

Прибыль составит 160 тыс. руб. (20 -2 + 40-3). Значит первая программа предпочтительней. Существуют и другие варианты.

Ограничения данной задачи таковы:

На графике проведем прямую L u соответствующую первому неравенству: Второму неравенству соответствует прямая Ь 2:

Третьему неравенству на графике соответствует прямая, параллельная оси абсцисс L 3:

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

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

Многоугольник ограничивает область допустимых решений задачи. Из массы решений нужно выбрать такое, где значение прибыли максимально. В нашем случае эго будет точка пересечения прямых L { и 1 2 . Далее решается система линейных уравнений:

Решая систему, получаем: отсюда прибыль равна:

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

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

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

При трех переменных пришлось бы строить многогранник в многомерной системе координат. При четырех и более переменных графическое изображение невозможно. Но можно представить многомерное пространство абстрактно. Если условие задачи непротиворечиво, то область допустимых значений (ОДЗ) образует выпуклый многоугольник в и-мерном пространстве.

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

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

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

Последовательность расчетов по симплексному методу рассмотрим на примере.

Пример 2.23

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

Имеются следующие ограничения:

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

Требуется получить максимальную прибыль.

Искомый выпуск: х { - изд. А; х 2 - изд. Б; х 3 - изд. В; х 4 - изд. Г.

Максимальная прибыль:

Ограничения:

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

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

В самой верхней строке записаны коэффициенты целевой функции. Дополнительным переменным соответствуют нулевые коэффициенты. Неиспользованное оборудование не приносит прибыль. Те же нулевые показатели - в столбце С против каждой дополнительной переменной.

В заполнении строки Zj - Cj имеются свои особенности. Рассматривается Zj для каждого столбца. Она получается как сумма произведений величин столбца С на соответствующие коэффициенты столбца j. Поскольку в первоначальном варианте в столбце С находятся 0, то величина Zj для всех столбцов равна 0, а величина Zj - Cj = -Cj. Поэтому в начальном варианте здесь поставлены коэффициенты целевой функции с обратным знаком. Все основные переменные приравнены к 0 и не входят в базис нашей задачи. Дополнительные переменные равны предельным значениям в соответствии с исходными уравнениями. Это означает, что ничего не производится, ресурсы не используются и значение целевой функции равно 0 (прибыль отсутствует).

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

Поскольку задача решается на max прибыли, начинать надо с наиболее прибыльного изделия. В нашем случае это изд. Г. В базис вводится х 4 . Определим, каким может быть предусмотрен выпуск изд. Г. Это зависит от объема ресурсов и нормативов затрат. На оборудовании группы I можно обработать 3000 изд. (24 000/8), группа II в изготовлении Г не участвует, а группа III может быть использована на обработку 30 000 изд. Принимаем наименьшее из значений (3000 изд.), в таблице в колонку «базис» х 4 ставится на место х 5 (оборудование группы I равняется нулю, так как использовано полностью). Число 8 на пересечении х А и х 5 называется направляющим элементом или генеральным , ключевым , разрешающим.

Строка х 4 в новой таблице получается путем деления строки выводящей переменной х 5 предыдущей таблицы на направляющий элемент. В столбце С проставляется 0,8 - величина прибыли с единицы изд. Г. После этого пересчитывается столбец «план». На оборудовании группы II изд. Г не обрабатывается и в новом варианте фонд его времени остается без изменений (12 000 мин).

Фонд времени оборудования группы III уменьшится на 3000 мин (1 мин х х 3000 шт.), следовательно остаются неиспользованными 27 000 мин. Следующее число столбца «план» - 2400 руб. (0,8 3000) - прибыль при данном варианте. После столбца «план» пересчитываются все остальные столбцы симплексной таблицы, кроме строки вводимой переменной. При этом, следует иметь в виду, что в столбцах всех переменных, входящих в базис, на пересечении одноименных строк и столбцов всегда находится единица, а остальные элементы столбца равны нулю.

Поэтому сразу можно заполнить столбцы х 4 , х 6 и х 7 . Пересчет целесообразно производить по «правилу треугольника». Для того, чтобы рассчитать в новом варианте какой-либо коэффициент, нужно в симплексной таблице найти три числа: число, стоящее на месте этого коэффициента в предыдущем варианте;

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

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

Например, для столбца.гр

Производим вычисление:

для коэффициента по строке

для коэффициента строки х 7:

Показатель для строки Zj - Cj можно рассчитать двумя способами:

а) по формуле

б) по правилу «треугольника»:

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

Теперь необходимо выяснить, является ли второй вариант оптимальным или он может быть улучшен. Для этого просматривается строка Zj - Cj. Если она содержит отрицательные числа, то вариант может быть улучшен.

На 0,3 руб. в расчете на каждую вводимую единицу изделий увеличится прибыль при введении в базис числах! (изд. А) и на 0,1 руб. при введении числах 3 (изд. В). Эти цифры могут показаться противоречащими исходным данным: согласно которым изд. А приносит 0,4 руб. прибыли, В - 0,5 руб. Но дело в том, что на данном этапе задачи введение в план этих изделий вытеснит известное количество ранее введенных изд. Г, чтобы для их производства высвободить оборудование группы I.

На следующем этане целесообразнее ввести х { (изд. А), гак как ему соответствует наибольшее по абсолютной величине отрицательное число. Аналогично предыдущему варианту установим сколько едении изд. А может быть включено в план с учетом того, что он уже содержит выпуск изд. Г. Для этого числа из столбца «план» делим на соответствующие (только положительные) коэффициенты из столбца вводимой переменной х { и из полученных частных выбираем наименьшее:

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

На пересечении столбца х х и строки х 6 находим и подчеркиваем направляющий элемент - 3. Далее рассчитываем строку введенной переменной путем деления элементов строки х 6 предыдущего варианта на направляющий элемент. Затем рассчитываем столбец «план»:

Прибыль при новом варианте составит:

По описанному правилу заполняем следующие столбцы. Просматривая строку Zj - Cj видим, что в ней содержатся только нули и положительные элементы, что означает, что вариант 3 является оптимальным решением и не может быть улучшен. В него входят лишь два вида изделий из четырех. Переменная х 3 соответствует в последней строке 0. Это означает, что введение в план на последующем шаге х 3 не увеличит прибыль, но и не уменьшит ее и полученный результат также будет оптимальным. Разделив числа столбца «план» на коэффициенты столбца х 3 и выбрав из полученных минимальное, определяем, что данная переменная должна вводиться в базис на место переменной^. В результате последующих преобразований получаем новый оптимальный план, в котором предусматривается выпуск 2182 изд. А (х {) и 5455 изд. В (.г 3). Найдем еще несколько оптимальных вариантов решения нашей задачи. Вариант /: 50% из первой программы и 50% из второй программы:

Вариант II: 80% из первой программы и 20% из второй программы:

Эти варианты также обеспечивают прибыль в размере 3600 руб.

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

При решении задач симплекс методом могут встретиться случаи «вырождения». При т ограничениях невырожденный план всегда содержит т положительных переменных, а остальные п - т переменных задачи в базис не входят и равняются нулю. Однако возможно равенство нулю и одной или нескольких переменных из входящих в базис, т.е. наличие одного или несколько нулей в столбце «план» симплексной таблицы. Такой план и называется вырожденным. При вырожденном плане наличие отрицательных чисел в строке Zj - Cj не означает, что следующий вариант обеспечит увеличение значения целевой функции. Оно может остаться неизмененным, причем на протяжении не только одного, но и нескольких последовательных шагов. Так происходит зацикливание , которое препятствует дальнейшим расчетам и может быть преодолено лишь с помощью специальных приемов.

В настоящее время при решении задач оптимизации широко применяются персональные компьютеры. При этом используется система электронных таблиц «Microsoft Excel ».

Для решения задач оптимизации в MS Excel используют надстройку Поиск решения, которая вызывается из пункта главного меню «Сервис».

Если в версии Excel , установленной на вашем компьютере, отсутствует данный подпункт меню «Сервис», необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения».

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

Пример 2.24

Предприятие выпускает продукты А, В, С, D из трех типов ресурсов. Математическая модель имеет следующий вид: шах/(Х) = 7,5я* 1 +3х 2 + 6дг 3 + 12.г 4 (целевая функция - суммарная стоимость выпуска).

Ограничения по запасам ресурсов и неотрицательности переменных таковы:

Составим шаблон в редакторе Excel.

Теперь занесем в данную задачу числовую информацию.

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

Ячейки С 4 - F a называются в Excel изменяемыми (в нашей модели это неизвестные переменные). Поиск решения при их изменении будет находить оптимальное значение целевой функции. Значения, которые первоначально вводят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие нулевые значения).

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

как произведение вектора (7, 5, 3, б, 12) на вектор (.г, х 2 , я-*, х А).

В Excel существует функция СУММПРОИЗВ, которая позволяет найти скалярное произведение векторов. Данную функцию необходимо вызвать в ячейку #5, а в качестве перемножаемых векторов задать адреса ячеек, содержащих коэффициенты уравнений (в данном случае, это С5: F5 ), и ячеек, в которые в результате решения будут помещены значения х и х 2 , х 3 , х 4 (ячейки СА : FA).

Каждая левая часть ограничения тоже представляет собой произведение двух векторов: соответствующей строки матрицы затрат и вектора неизвестных. Выражение 2х х + х 2 + 0Дг 3 + 4х л (для первого ограничения 2х, + х 2 + 0,5х 3 + 4 х 4 2400) будем рассматривать как произведение вектора коэффициентов (2,1,0,5,4) и вектора переменных (х и х 2 , х 3 , х 4).

В ячейке, отведенной для формулы левой части первого ограничения ((79), вызовем функцию СУММПРОИЗВ. В качестве адресов перемножаемых векторов занесем адрес строки коэффициентов С9: /0 и адрес значений переменных С4: FA.

В четыре оставшиеся ячейки графы «Левая часть» вводим аналогичные формулы, используя соответствующую строку матрицы затрат. Фрагмент экрана с введенными формулами выглядит следующим образом.

К моменту вызова сервиса «Поиск решения» на рабочий стол с задачей должны быть занесены формулы для левых частей ограничений и формула для значения целевой функции.

В меню «Сервис» выбираем «Поиск решения». В появившемся окне задаем следующую информацию:

а) в качестве целевой ячейки устанавливаем адрес ячейки для значения целевой функции #5;
б) «флажок» устанавливаем на вариант «максимальному значению», так как в данном случае целевая функция дохода подлежит максимизации;
в) в качестве изменяемых ячеек заносится адрес строки значений переменных С4: F4;
г) справа от окна, предназначенного для занесения ограничений, нажимаем кнопку «Добавить», появится форма для занесения ограничения;

д) в левой части формы «Ссылка на ячейку» заносится адрес формулы для левой части первого ограничения G 9, выбирается требуемый знак неравенства (в нашем случае,

е) аналогично заносятся все ограничения задачи, после чего нажимается кнопка «ОК».

Окно «Поиск решения» с занесенной информацией выглядит следующим образом.

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

Затем следует нажать «ОК», «Выполнить», после чего появляется окно результата решения.

Если в результате всех действий получено окно с сообщением «Решение найдено», то вам предоставляется возможность получения трех типов отчета, которые полезны при анализе модели на чувствительность. В данном примере достаточно сохранить найденное решение, нажав «ОК». В результате получено решение задачи.

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

В окне «Поиск решения» имеется кнопка «Параметры».

Установим флажок «Показывать результаты итераций», нажмем «ОК».

Затем нажмем кнопку «Выполнить».

Ms Excel выдаст следующее окно.

На рабочем листе будут показаны результаты первой итерации.

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

Снова нажимаем кнопку «Продолжить», на рабочем листе отображаются результаты третьей итерации.

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

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

Отчеты выглядят следующим образом.

1. Отчет по результатам.

2. Отчет по устойчивости.

3. Отчет по пределам.

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

Пример 2.25

Л. Допустим, математическая модель такова: Она имеет следующие ограничения:

Отчет по устойчивости.

Б. Теперь предположим, что математическая модель имеет другие ограничения:

В данном случае имеем следующие результаты по отчетам.

Отчет по устойчивости.

Воспользуемся для решения этой же задачи одним из методов линейного программирования - графическим. Пример 2.22 Введем обозначения: х{ - искомое количество дверей ДВ, х2 - искомое количество дверей ДВС.

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

В качестве примера рассмотрим решение задачи рациональности использования времени работы производственного оборудования.
В соответствии с оперативным планом участок шлифовки за первую неделю декабря выпустил 500 колец для подшипников типа А, 300 колец для подшипников типа Б и 450 колец для подшипников типа В. Все кольца шлифовались на двух взаимозаменяемых станках разной производительности. Машинное время каждого станка составляет 5000 мин. Трудоемкость операций (в минутах на одно кольцо) при изготовлении различных колец характеризуется следующими данными (табл. 6.5).
Таблица 6.5
Следует определить оптимальный вариант распределения операций по станкам и время, которое было бы затрачено при этом оптимальном варианте. Задачу выполним симплексным методом.
Для составления математической модели данной задачи введем следующие условные обозначения: jc, х2, хъ, - соответственно количество колец для подшипников типов Л, Б, В, производимых на станке I; х4, х5, х6, - соответственно количество колец для подшипников типов А, Б, В, производимых на станке II.
Линейная форма, отражающая критерий оптимальности, будет иметь вид:
min а(х) = 4x,-f 10x2-f 10x3-f 6x4-f 8х5+20х6 при ограничениях
4х, -f 10х2 -f 10;t3 lt; 5000
6х4 -f 8х5 -f 20х6 ~lt; 5000
х, = 500
х2 +х5 = 300
х3 +х6 = 450
Xj^0,j=l, ..., 6

Преобразуем условие задачи введением дополнительных (вспомогательных) и фиктивных переменных. Условие запишем так:
шіп lt;х(х) = 4дг, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Мх9 + Мх{0+Мх{,
Система уравнений, отражающая ограничительные условия машинного времени и количество произведенной продукции:
4х, + l(bc2 + 10х3 +х1 = 5000
6х4 + 8х5 + 20х6 + xs = 5000
Xj +х4 +х9 = 500
х2 +х5 +х10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Решение этой задачи представлено в табл. 6.6. Оптимальный вариант получен на седьмом этапе (итерации). Если бы на станке I производилось 125 колец подшипников типа А, 450 колец подшипников типа В, на станке II - 375 колец подшипников типа А и 300 колец подшипников типа Б, то при такой загрузке оборудования было бы высвобождено 350 мин машинного времени станка II. Общие затраты времени по оптимальному варианту составили бы 9650 мин, тогда как фактически затрачено 10000 мин машинного времени.
Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. Ее смысл заключается в минимизации грузооборота при доставке товаров широкого потребления от производителя к потребителю, с оптовых складов и баз в розничные торговые предприятия. Она решается симплекс-методом или распределительным методом.
Решение транспортной задачи распределительным методом было дано в третьем издании учебника «Теория экономического анализа» («Финансы и статистика», 1996).

Решение задачи рациональности использования станков симплексным методом

Базис	с	Ро	4	10	10	6	8	20	0	0	м	м	м
Базис	с	Ро	Л	Рг	Ръ	Л	Р ъ		Pi	Р8	р*	Л 0	Л,
Л	0	5000	4	10	0	0	0	0	і	0	0	0	0
Р,	0	5000	0	0	0	6	8	20	0	1	0	0	0
Л	м	500	1	0	0	1	0	0	0	0	1	0	0
Л 0	м	300	ш	0	0	0	1	0	0	0	0	1	0
Л.	м	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		1250М	М-4	М-10	М-10	М-6	М-8	М-20	0	0	0	0	0
Pi	0	3000	0	10	10	-4	0	0	0	0	-4	0	0
р*	0	5000	0	0	0	6	8	20	1	1	0	0	0
Ро	4	500	1	0	0	1	0	0	0	0	1	0	0
Ло	м	300	0	1	0	0	ш	0	0	0	0	1	0
Л.	м	450	0	0	1	0	0	1	0	0	0	0	1
zr-9		750Л/+2000	0	М-10	М-10	-2	М-8	О 2	0	0	-М + 4	0	0

Базис	С	Р0	4	Pi	10	6	8	20	0	0	м	м	М
		Р0	Pi	10	^3	л	Р5	р6	Pi	р«	р9	Pi 0	Рц
Pi	0	3000	0	10	10	-4	0	0	1	0	-4	0	0
Р*	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
Pi	4	500	1	0	0	1	0	0	0	0	1	0	0
Р5	8	300	0	1	0	0	1	0	0	0	0	1	0
РП	М	450	0	0	1	0	0	1	0	0	0	0	1
Zj-Cj		450Л/+4400	0	-2	М-10	-2	0	М-20	0	0	-М+4	-М+8	0
Ръ	10	300	0	1	1	4 10	0	0	1 10	0	4 10	0	0
Р%	0	2600	0	-8	0	6	0	20	0	1	0	-8	0
Pi	4	500	1	0	0	1	0	0	0	0	1	0	0
Р5	8	300	0	1	0	0	1	0	0	0	0	1	0
Рц	М	150	0	-1	0	j4_ 10	0	1	_ J_ 10	0	4 10	0	1
zrCj		150Л/+7400	0	-M+S	0	- М-6 10	0	М-20	- ~М+1 10	0	-±м 10	- Af+8"	0

Базис	с	Л,	4	10	10	6	8	20	0	0		М	М	м
Базис	с	Л,	Л	Рг	Л	л	PS	р6	Pi	рamp;		Р9	Ло	л.
Л	10	300	0	1	1	4	0	0	1		0	4	0	0
						“10			То			“ 10
р6	20	130	0	4	0	3	0	1	0		1	0	4	0
				~Ї0		10					20		10
л	4	500	1	0	0	1	0	0	0		0	1	0	0
Ps	8	300	0	1	0	0	1	0	0		0	0	1	0
Р\\	М	20	0	6	0	1	0	0	1		1	4	4	1
				10		~10			То		20	То	10
Zj-Cj		20М+10000	0		0	-м	0	0	м+\		-м+\	--М	-*М	0
				10		10			10	20		10	10
л	10	380	0	14	1	0	0	0	3		2	12	0	0
				10					10		10	10
р%	20	70	0	14	0	0	0	1	3		2	12	16	-3
				10					10		10	10	10
Л	4	300	1	6	0	0	0	0	1		1	-3		-10
											2
р5	8	300	0	1	0	0	1	0	0		0	0	1	0
Р4	6	200	0	-6	0	1	0	0	-1		1	4	4	10
											’ 2
Z.-Ci		10000	0	0	0	0	0	0	1	1		-М	-М	-м

Базис		Лgt;	4	10	10	6	8	20	0	0	м	м	л/
Базис	о	Лgt;	Л	Рг	ръ	Р*	Р5	Р6	Л	Рamp;	р9	Л 0	л.
Рг	10	450	0	0	1	0	0	1	0	0
Р%	0	350	0	7	0	0	0	5	3 5	1
Л	4	125	1	5 2	0	0	0	5 2	1 4	0
Ps	8	300	0	1	0	0	1	0	0	0
Р4	6	375	0	5 2	0	1	0	5 2	1 4	0
Zj-Cj		9650	0	-7	0	0	0	-5	1 2	0

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

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

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

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

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

Задача минимизации целевой функции 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. Понятие математического программирования

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

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

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

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

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

задачи линейного программирования,
задачи нелинейного программирования .

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

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования . Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина " линейное программирование " возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

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

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

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

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

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

Общая форма задачи имеет вид: найти при условиях

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

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

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