Пример 6.1.

Решение:

Задача линейного программирования задана в стандартной форме и имеет два проектных параметра, следовательно

Воз-можно ее решение геометрическим методом.

1 этап: ( ОДР ).

Рассмотрим первое ограничение, заменим знак неравенства знаком равенства и выразим переменную х2 через х1 :

.

Аналогично определяем точки для остальных ограничений системы и строим по ним прямые, соответствующие каждому неравенству (рис. 1). Прямые пронумеруем согласно принятой ранее схеме.

2 этап: .

Определим полуплоскости – решения каждого из неравенств.

Рассмотрим первое неравенство системы ограничений задачи. Возьмем какую-либо точку (контрольную точку), не принадлежащую соответствующей данному неравенству прямой, например, точку (0; 0). Подставим ее в рассматриваемое неравенство:

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

Аналогично определяем решения других неравенств и соответственно помечаем их графике. В результате график примет следующий вид:

3 этап: .

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

Рис. 1. Область допустимых решений задачи

4 этап:
Вектор-градиент показывает направление максимизации целевой функции . Определим его координаты: координаты начальной его точки (точки приложения) – (0; 0), координаты второй точки:

Построим данный вектор на графике (рис. 2).

5 этап: .

Рассмотрим целевую функцию данной задачи:

.

Зададим ей какое-либо значение, к примеру, . Выразим переменную х2 через х1 :

.

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

Построим прямую соответствующую целевой функции (рис. 2).

Рис. 2. Построение целевой функции F(X) и вектора-градиента С

6 этап: определение максимума целевой функ-ции .

Перемещая прямую F (X ) параллельно са-мой себе по направлению вектора-градиента, определяем крайнюю точку (точки) ОДР. Согласно графику (рис. 3), такой точкой является точка С ­– точка пересечения прямых I и II .

Рис. 3. Определение точки максимума целевой функции F(X)

Определим координаты точки С, с этой целью, решим сле-дующую систему линейных уравнений:

Подставим найденные координаты в целевую функцию и найдем ее оптимальное (максимальное) значение:

Ответ: при заданных ограничениях макси-мальное значение целевой функции F (Х )=24, которое достигается в точке С, координаты которой х1 =6, х2 =4.

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

Решение:

Этапы 1-3 аналогичны соответствующим этапам предыдущей задачи.
4 этап: построение вектора-градиента.
Построение вектора-градиента осуществляется аналогично, как и в предыдущей задаче. Построим данный вектор на графике (рис. 4). Отметим также на данном графике стрелкой направление, обратное вектору-градиенту, – направление минимизации целевой функцииF (X ).

5 этап: построение прямой целевой функ-ции .

Построение прямой целевой функции F (X ) осуществляется аналогично, как и в предыдущей задаче (результат построения приведен на рис. 4).

Рис. 4. Построение целевой функции F(x) и вектора-градиента С

6 этап: определение оптимума целевой функ-ции .

Перемещая прямую F (x ) параллельно са-мой себе в направлении, обратном вектору-градиенту, опреде-ляем крайнюю точку (точки) ОДР. Согласно графику (рис. 5), та- кой точкой является точка О с координатами (0; 0).

Рис. 5. Определение точки минимума целевой функции

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

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

Решение:

Рассматриваемая задача линейного программирования задана в канонической форме, выделим в качестве базисных переменные x 1 и x 2 .

Составим расширенную матрицу и выделим с помощью метода Жордана- Гаусса базисные переменныеx 1 и x 2 .

Умножим (поэлементно) первую строку на –3 и сложим со вто-рой:
.

Умножим вторую строку на :

.

Сложим вторую с первой строкой:

.

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

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

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

Запишем полученную задачу линейного программирования:

Так как переменные x 1 и x 2 неотрицательные, то полученную систему ограничений можно записать в следующем виде:

Тогда исходную задачу можно записать в виде следующей эк- вивалентной ей стандартной задаче линейного программирования:

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

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

Рассмотрим систему ограничений задачи линейного програм-мирования (для удобства пронумеруем неравенства):

Построим прямые, соответствующие каждому неравенству (рис. 6). Прямые пронумеруем согласно принятой ранее схе-ме.

2 этап: определение решения каждого из нера-венств системы ограничений .

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

3 этап: определение ОДР задачи линейного про- граммирования .

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

Рис. 6. Фрагмент MathCAD-документа:

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

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

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

Направление, обратное вектору-градиенту, соответствует направлению минимизации целевой функции.

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

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

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

Однако для выработки наглядных представлений о решениях задач линейного программирования графический метод представляет определённый интерес. Кроме того, он позволяет геометрически подтвердить справедливость теорем линейного программирования .

Теоретические основы графического метода

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

при которых линейная форма принимает оптимальное значение.

Пример 3.

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

Продолжаем решать задачи графическим методом вместе

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

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

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

Легко заметить, что функция F может неограниченно возрастать при заданной системе ограничений, поэтому можно условно записать, что .

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

Цель работы

1. Изучить понятие математической модели.

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

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

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

Теоретическое введение

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

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

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

Построение математической модели задачи включает следующие этапы:

1) выбор переменных задачи;

2) составление системы ограничений;

3) выбор целевой функции.

Переменными задачи называются величины х 1 , х 2 , …х n , которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора A = (х 1 , х 2 , …х n).

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

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

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

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

Функция (1.1) называется целевой функцией, а ограничения (1.2) – системой ограничений задачи.

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

Обратите внимание на полученный результат. Целевая функция является линейной функцией переменных х 1 , х 2 , …х n ; сами ограничения на значения переменных х 1 , х 2 , …х n имеют вид линейных неравенств. Все это и определило название этого класса задач – задачи линейного программирования .

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

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

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

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

Методика выполнения работы

Примеры задач ЛП

Пример 1.1. Предприятие химической промышленности выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты – 25 денежных единиц (ден. ед.)., выпуск одной тонны серной кислоты – 40 ден. ед. Для выполнения государственного заказа необходимо выпустить не менее 200 т соляной и не менее 100 т серной кислоты. Кроме того, необходимо учитывать, что выпуск кислот связан с образованием опасных отходов. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов, при выпуске одной тонны серной кислоты – 1,2 т опасных отходов. Общее количество опасных отходов не должно превышать 600 т, так как превышение этого ограничения приведет к выплате предприятием крупного штрафа.

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

Составим математическую модель задачи . Для этого введем переменные. Обозначим через x 1 количество выпускаемой соляной кислоты (в тоннах), через x 2 – количество серной кислоты.

Составим ограничения, связанные с необходимостью выполнения государственного заказа. Предприятию необходимо выпустить не менее 200 т соляной кислоты. Это ограничение можно записать следующим образом: x 1 200. Аналогично составим ограничение, устанавливающее, что предприятие должно выпустить не менее 100 т серной кислоты: x 2 100.

Составим ограничение на опасные отходы. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов; значит, общее количество опасных отходов при выпуске соляной кислоты составит 0,5x 1 т. При выпуске серной кислоты образуется 1,2x 2 т опасных отходов. Таким образом, общее количество опасных отходов составит 0,5x 1 +1,2x 2 т. Эта величина не должна превышать 600 т. Поэтому можно записать следующее ограничение: 0,5x 1 +1,2x 2 600 .

Кроме того, переменные по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество выпускаемых кислот. Поэтому необходимо учитывать ограничения неотрицательности: x 1 0; x 2 0.

В данной задаче требуется определить выпуск кислот, при котором прибыль будет максимальной. Прибыль от выпуска одной тонны соляной кислоты составляет 25 ден. ед.; значит прибыль от выпуска соляной кислоты составит 25x 1 ден. ед. Прибыль от выпуска серной кислоты составит 40x 2 ден. ед. Таким образом, общая прибыль от выпуска кислот составит 25x 1 +40x 2 ден. ед. Требуется найти такие значения переменных x 1 и x 2 , при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:

Е=25x 1 +40x 2 → max.

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

0,5x 1 +1,2x 2 600

Е=25x 1 +40x 2 → max.

В этой задаче имеется два ограничения «больше или равно» и одно ограничение «меньше или равно». Целевая функция подлежит максимизации.

Пример 1.2. Пусть в условиях задачи 1.1 из-за ужесточения требований к экологической безопасности требуется свести к минимуму количество опасных отходов. В то же время необходимо учитывать, что для того, чтобы производство кислот было экономически целесообразным, необходимо получить прибыль не менее 20 тыс. ден. ед.

Математическая модель такой задачи имеет следующий вид:

25x 1 +40x 2 20000

Е= 0,5x 1 +1,2x 2 → min.

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

Графический метод решения задач ЛП

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

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

Как отмечено выше, ОДР – это множество значений переменных, удовлетворяющих ограничениям (1.2). Таким образом, для задач с двумя переменными ОДР представляет собой множество точек (x 1 ; x 2), т.е. некоторую область на плоскости (обычно многоугольник). Для задач с тремя переменными ОДР представляет собой многогранник в пространстве, для задач с большим количеством переменных – некоторую область многомерного пространства. Можно доказать, что экстремум (минимум или максимум) целевой функции всегда достигается при значениях переменных, соответствующей одной из угловых точек ОДР. Другими словами, оптимальное решение всегда находится в угловой точке ОДР. Поэтому задачу линейного программирования с двумя переменными можно решить следующим образом: построить ОДР на плоскости в системе координат (x 1 ; x 2), определить все угловые точки ОДР, вычислить значения целевой функции в этих точках и выбрать оптимальное решение.

Решим графическим методом задачу из примера 1.1.

Решение показано на рис. 1.1.

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

Ограничение x 1 200 задается вертикальной линией x 1 =200. Все точки (x 1 ; x 2), расположенные справа от этой линии, удовлетворяют ограничению x 1 200, расположенные слева – не удовлетворяют. Ограничение x 2 100 задается горизонтальной линией x 2 =100. Все точки, расположенные сверху от этой линии, удовлетворяют ограничению x 2 100, расположенные снизу – не удовлетворяют.

Для построения линии, задающей ограничение 0,5x 1 +1,2x 2 600, удобно записать его в виде равенства: 0,5x 1 +1,2x 2 =600 . Выразим одну из переменных через другую: x 2 =-0,41x 1 +500. это уравнение прямой. Построим эту прямую. Она разбивает координатную плоскость на две полуплоскости. В одной из этих полуплоскостей находятся точки, удовлетворяющие ограничению, в другой – не удовлетворяющие. Чтобы найти полуплоскость, удовлетворяющую ограничению 0,5x 1 +1,2x 2 600, подставим в него координаты любой точки, например, (0; 0). Для этой точки ограничение выполняется. Значит, она находится в полуплоскости, удовлетворяющей ограничению.

Пересечение всех полуплоскостей, удовлетворяющих ограничениям задачи, представляет собой ОДР. На рис. 1.1 она выделена серым цветом.

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

Е(А) = 25∙200 + 40∙100=9000;

Е(В) = 25∙200 + 40∙416,67 = 21666,8;

Е(С) = 25∙960 + 40∙100 = 28000.

Таким образом, оптимальное решение находится в точке С= (960; 100). Это означает, что предприятию следует выпустить 960 т соляной кислоты и 100 т серной кислоты. Прибыль при этом составит 28000 ден.ед. Можно также найти количество опасных отходов, которое будет получено при производстве кислот: 0,5 960 + 1,2∙100 = 600 т.

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

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

В данном случае ОДР имеет только две угловые точки (А и В). Найдем для них значение целевой функции:

Е(А)= 0,5 ∙200+1,2 ∙ 375 =550;

Е (В) = 0,5 ∙640+1,2∙100 =440.

Таким образом, оптимальное решение находится в точке В(640; 100). Это означает, что предприятию следует выпустить 640 т соляной и 100 т серной кислоты. При этом образуется 440 т опасных отходов. Можно также найти прибыль от производства кислот: 25 ∙ 640 + 40 ∙100 = 20 000 ден.ед.

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

Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц.

Наименование ресурса	A	B	Объем ресурсов
Часы маш.обработки	3	10	330
Единиц сырья	16	4	400
Единиц труда	6	6	240

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

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

Этап 1. Определение переменных

Существует целевая переменная (обозначим её Z), которую необходимо оптимизировать, то есть максимизировать или минимизировать (например, прибыль, выручка или расходы). Николай стремится максимизировать маржинальную прибыль, следовательно, целевая переменная:

Z - это суммарная маржинальная прибыль (в рублях), полученная в следующем месяце в результате производства продуктов А и В.

Существует ряд неизвестных искомых переменных (обозначим их х 1 , х 2 , х 3 и пр.), чьи значения необходимо определить для получения оптимальной величины целевой функции, которая, в нашем случае является суммарной маржинальной прибылью. Эта маржинальная прибыль зависит от количества произведенных продуктов А и В. Значения этих величин необходимо рассчитать, и поэтому они представляют собой искомые переменные в модели. Итак, обозначим:

х 1 - количество единиц продукта А, произведенных в следующем месяце.

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

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

Этап. 2. Построение целевой функции

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

В нашем примере каждый изготовленный продукт А приносит 2500 руб. маржинальной прибыли, а при изготовлении х 1 единиц продукта А, маржинальная прибыль составит 2500х 1 . Аналогично маржинальная прибыль от изготовления х 2 единиц продукта В составит 3500х 2 . Таким образом, суммарная маржинальная прибыль, полученная в следующем месяце за счет производства х 1 единиц продукта А и х 2 единиц продукта В, то есть, целевая переменная Z составит: Z = 2500х 1 +3500х 2 .

Николай стремится максимизировать этот показатель. Таким образом, целевая функция в нашей модели:

Этап. 3. Определение ограничений

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

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

Изготовление каждой единицы продукта В требует 10 часов и, следовательно, если произведено х 2 продуктов, то потребуется 10х 2 часов. Таким образом, общий объем машинного времени, необходимого для производства х 1 единиц продукта А и х 2 единиц продукта В, составляет 3х 1 +10х 2 . Это общее значение машинного времени не может превышать 330 часов. Математически это записывается следующим образом:

3х 1 +10х 2 ≤330

Аналогичные соображения применяются к сырью и труду, что позволяет записать еще два ограничения:

16х 1 +4х 2 ≤400

6х 1 +6х 2 ≤240

Наконец следует отметить, что существует условие, согласно которому должно быть изготовлено не менее 12 единиц продукта В:

Этап. 4. Запись условий неотрицательности

Искомые переменные не могут быть отрицательными числами, что необходимо записать в виде неравенств х 1 ≥0 и х 2 ≥0. В нашем примере второе условия является избыточным, так как выше было определено, что х 2 не может быть меньше 12.

\[\left\{ {\begin{array}{}
{3{x_1} + 10{x_2} \le 330}\\
{16{x_1} + 4{x_2} \le 400}\\
{6{x_1} + 6{x_2} \le 240}\\
{{x_1} \ge 0}\\
{{x_2} \ge 12}
\end{array}} \right.\]

Решение симплекс-методом

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

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

Алгорим симплексного метода можно описать следующим образом:

1. Привести задачу к каноническому виду
2. Найти неотрицательное базисное решение системы ограничений
3. Рссчитать оценки свободных переменных по формуле:

\[{\Delta}_j = \sum\limits_{i = 1}^r {{c_i}{h_{ij}} – {c_j}} ,\;j = \overline {1,n} ,\]

где h ij – коэффициенты при свободной переменной x j ,

c i – коэффициенты при базисных переменных в целевой функции,

c j – коэффициенты при свободной переменной в целевой функции,

1. Проверить найденное опорное решение на оптмальность:

а) если все оценки \({\Delta}_j \ge 0\) , то найденное решение оптимально и задача решена;

б) если хотя бы одна оценка \({\Delta}_j < 0\) , а при соответствующей переменной x j нет ни одного положительного коэффициента, то задача не имеет оптимального решения из-за ограниченности целевой функции

в) если хотя бы одна оценка \({\Delta}_j < 0\) , а при соответствующей переменной x j есть хотя бы один положительный коэффициент, то решение не оптимально и его можно улучшить переходом к новому базису. Если отрицательных оценок несколько,то в базис ввести переменную с наибольшей по абсолютной величине отрицательной оценкой.

Приведем задачу к каноническому виду .

Полная модель линейного программирования для производственной задачи Николая может быть записана в виде:

\[\left\{ {\begin{array}{}
{3{x_1} + 10{x_2} + {x_3} = 330}\\
{16{x_1} + 4{x_2} + {x_4} = 400}\\
{6{x_1} + 6{x_2} + {x_5} = 240}\\
{-{x_2} +{x_6} = 12}\\
{{x_j} \ge 0\;j = \overline {1,n}}
\end{array}} \right.\]

Б.п.	x 1	x 2	x 3	x 4	x 5	x 6	b i
x 3	3	10	1	0	0	0	330
x 4	16	4	0	1	0	0	400
x 5	6	6	0	0	1	0	240
x 6	0	-1	0	0	0	1	12

\[\bar{x}_{\text{опор}}=(0;0;330;400;20;12)\]

Проверим данное решение на оптимальность, для этого найдем свободные переменные в симплексной таблице. Вычисления представлены в файле lp_simplex.xlsx .

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

Преобразуем таблицу и повторим расчет.

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

Полученное решение (10; 30) является оптимальным.

Решение с помощью Excel и LibreOffice

Решение в Excel осуществляется с помощью надстройки “Поиск решения”, также использующей симплекс-метод.

Анологично даную задач можно решить с помощью Решателя в LibreOffice. Следует отметить, что в LibreOffice нет ограничений на число переменных, в отличии от Excel.

Решение в R

Для решения задач линеного программирования в GNU R можно использовать следующие пакеты:

• lpSolve
• linprog

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

Решение с пакетом lpSolve

library(lpSolve) # Подключили библиотеку f.obj <- c(2500, 3500) # Описали целевую функцию names(f.obj) <-c("A","B") a.mat<-rbind(c(3,10), # матрица c(16,4), # коээфициентов c(6,6), # при ограничениях c(1,0), c(0,1)) a.dir<-c("<=","<=","<=",">=",">=") b.vec<-c(330,400,240,0,12) # вектор ограничений result<-lp ("max", f.obj, a.mat, a.dir, b.vec)

Результат

result ## Success: the objective function is 130000 result$solution ## 10 30

Таким образом, максимальное значение целевой функции равно 130000 и оно достигается при x 1 и x 2 равными, соответственно: 10 и 30.

Решение с пакетом linprog

Поскольку пакет linprog является дополнением к предыдущему пакету, то переменные уже все инициализированы.

Library(linprog) ## Warning: package "linprog" was built under R version 3.2.2 (result<-solveLP(f.obj, b.vec, a.mat, TRUE,const.dir=a.dir,lpSolve=T)) ## ## ## Results of Linear Programming / Linear Optimization ## (using lpSolve) ## ## Objective function (Maximum): 130000 ## ## Solution ## opt ## A 10 ## B 30 ## ## Constraints ## actual dir bvec free ## 1 330 <= 330 0 ## 2 280 <= 400 120 ## 3 240 <= 240 0 ## 4 10 >= 0 10 ## 5 30 >= 12 18

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

Вконтакте