Рассмотрим сначала простейший случай, когда в ЗЛП включены ровно две переменные:
Каждое из неравенств (a)-(b) системы ограничений задачи (3.8) геометрически определяет полуплоскость соответственно с граничными прямыми , Х 1 =0 и Х 2 =0. Каждая из граничных прямых делит плоскость х 1 Ох 2 на две полуплоскости. Все решения исходного неравенства лежат в одной из образованных полуплоскостей (все точки полуплоскости) и, следовательно, при подстановке координат любой ее точки в соответствующее неравенство обращает его в верное тождество. С учетом этого и определяется та полуплоскость, в которой лежат решения неравенства, т.е. путем выбора любой точки из какой-либо полуплоскости и подстановки ее координат в соответствующее неравенство. Если неравенство выполняется для данной точки, то оно выполняется и для любой другой точки из этой же полуплоскости. В противном случае решения неравенства лежат в другой полуплоскости.
В том случае, если система неравенств (a)-(b) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей выпуклое, то область допустимых решений задачи (3.8) является выпуклое множество, которое называется многоугольником решений (введённый ранее термин “многогранник решений” обычно употребляется, если n 3). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.
Таким образом, исходная ЗЛП состоит в нахождении такой точки многоугольника решений, в которой целевая функция F принимает максимальное (минимальное) значение.
Эта точка существует тогда, когда многоугольник решений не пуст и на нём целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины строят линию уровня L: c 1 x 1 +c 2 x 2 =h (где h – некоторая постоянная), перпендикулярную вектору-градиенту и проходящую через многоугольник решений, и передвигают её параллельно вдоль вектора-градиента до тех пор, пока она не пройдёт через последнюю её общую точку пересечения с многоугольником решений (при построении вектора-градиента откладывают точку (с 1 ; с 2) в плоскости х 1 Ох 2 и проводят к ней из начала координат направленный отрезок). Координаты указанной точки и определяют оптимальный план данной задачи.
Суммируя все выше изложенное, приведем алгоритм графического метода решения ЗЛП.
Алгоритм графического метода решения ЗЛП
1. Построить многоугольник решений, задаваемый системой ограничений исходной ЗЛП.
2. Если построенный многоугольник решений – пустое множество, то исходная ЗЛП решений не имеет. В противном случае построить вектор-градиент и провести произвольную линию уровня L, перемещая которую при решении задачи на максимум в направлении вектора (или в обратном направлении для задачи на минимум) определить крайнюю точку многоугольника решений, где и достигается максимум (минимум) целевой функции задачи.
3. Вычислить координаты найденной оптимальной точки , решив систему уравнений двух граничных прямых, пересекающихся в ней.
4. Подстановкой найденного оптимального решения в целевую функцию задачи вычислить оптимальное ее значение, т.е.: .
При графическом построении множества допустимых решений ЗЛП (многоугольника решений) возможны следующие ситуации.
Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными. Рассмотрим задачу ЛП в стандартной форме:
max f(x 1 , x 2 , ..., x n) = ,
, i = 1, 2, …, m,
x j 0, j = 1, 2, …, n.
Положим n=2 и будем рассматривать задачу на плоскости. Пусть система неравенств совместна (имеет хотя бы одно решение).
Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой а i 1 х 1 + а i 2 х 2 = b i , i = 1, 2,…, m. Условия неотрицательности определяют полуплоскости с граничными прямыми х 1 = 0, х 2 = 0 соответственно. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, где координаты каждой точки являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограниченным многоугольником.
Таким образом, геометрически ЗЛП представляет собой отыскание такой точки многоугольника решений, координаты которой доставляют линейной функции цели максимальное (минимальное) значение, причем допустимыми решениями являются все точки многоугольника решений.
Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую область на плоскости. Определим, какую часть плоскости описывает неравенство 2х 1 + Зх 2 12.
Во-первых, построим прямую 2х 1 + Зх 2 = 12. Она проходит через точки (6; 0) и (0; 4). Для того чтобы определить, какая полуплоскость удовлетворяет неравенству, необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением, и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать точку начала координат. Подставим х 1 = х 2 = 0 в неравенство 2х 1 + Зх 2 12. Получим 2х0 + 3х0 12. Данное утверждение является верным, следовательно, неравенству 2х 1 + Зх 2 12 соответствует нижняя полуплоскость, содержащая точку (0; 0). Это отражено на графике, изображенном на рис. 1.1.
Аналогично графически можно изобразить все ограничения задачи ЛП.
Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений, или областью определения. Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (х j 0, j = 1, 2, …, n). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.
Для нахождения экстремального значения целевой функции при графическом решении задач ЛП используют вектор-градиент, координаты которого являются частными производными целевой функции, т.е.
Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая с 1 х 1 + с 2 х 2 = f(х 0) , перпендикулярная вектору-градиенту, является линией уровня целевой функции. В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине «а» . Меняя значение «а», получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.
Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в другую сторону - только убывает.
С геометрической точки зрения в задаче линейного программирования ищется такая угловая точка или набор точек из допустимого множества решений, на котором достигается самая верхняя (нижняя) линия уровня, расположенная дальше (ближе) остальных в направлении наискорейшего роста.
Графический метод решения ЗЛП состоит из следующих этапов.
1. Строится многоугольная область допустимых решений (ОДР) ЗЛП.
2. Строится вектор-градиент целевой функции (ЦФ) в какой-нибудь точке х 0 , принадлежащей ОДР:
3. Линия уровня с 1 х 1 + с 2 х 2 = а (а - постоянная величина) - прямая, перпендикулярная вектору-градиенту , - передвигается в направлении этого вектора в случае максимизации f(x 1 , х 2) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x 1 , х 2).
4. Для нахождения координат точки максимума достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x 1 , х 2), найденное в получаемой точке, является максимальным.
При минимизации (максимизации) функции f(x 1 , х 2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимум (максимум) функции f(x 1 , х 2) не существует.
Если линия уровня параллельна какому-либо функциональному ограничению задачи, то оптимальное значение ЦФ будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением ЗЛП. Возможные ситуации графического решения задач ЛП представлены в табл. 1.3.
Таблица 1.3
| № | Вид ОДР | Вид оптимального решения | Примечания |
| Многоугольная замкнутая | Единственное решение | ||
| Единственное решение | |||
| Многоугольная | ЦФ не ограничена снизу | ||
| ЦФ не ограничена сверху | |||
| Многоугольная незамкнутая | Единственное решение | ||
| Бесконечное множество решений | |||
| Отрезок | Единственное решение |
Рассмотрим графическое решение задач линейного программирования на следующем примере.
Пример 1.1. Планирование выпуска продукции пошивочного предприятия (задача о костюмах).
Намечается выпуск двух видов костюмов – мужских и женских. На женский костюм требуется 1м шерсти, 2м лавсана и 1 чел./день трудозатрат. На мужской костюм – 3,5м шерсти, 0,5м лавсана и 1 чел./день трудозатрат. Всего имеется 350м шерсти, 240м лавсана и 150 чел./дней трудозатрат. Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского – 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.
Введем следующие обозначения: х 1 - число женских костюмов; х 2 – число мужских костюмов. Прибыль от реализации женских костюмов составляет 10х 1 , а от реализации мужских - 20х 2 , т.е. необходимо максимизировать целевую функцию:
10х 1 + 20х 2
Ограничения задачи имеют вид:
х 1 + х 2 150,
2 х 1 + 0,5х 2 240,
х 1 + 3,5х 2 350,
х 2 60,
х 1 0.
Первое ограничение по труду х 1 + х 2 150. Прямая х 1 + х 2 = 150 проходит через точки (150; 0) и (0; 150) (рис. 1.2).
Второе ограничение по лавсану 2 х 1 + 0,5х 2 240. Прямая 2 х 1 + 0,5х 2 = 240 проходит через точки (120; 0) и (0; 480). Третье ограничение по шерсти х 1 + 3,5х 2 350. Добавим четвертое ограничение по количеству мужских костюмов х 2 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х 2 = 60. На рис. 1.3 заштрихована область допустимых решений. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е.
Чтобы построить такой вектор, нужно соединить точку (10;20) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации – в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору . Так, на рис. 1.4 изображен вектор-градиент (30;60).
Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е.
В нашем случае движение линии уровня будем осуществлять до ее выхода из области допустимых решений. В крайней, угловой, точке достигается максимум целевой функции. Для нахождения координат этой точки достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума:
х 1 + 3,5х 2 = 350,
х 1 + х 2 = 150.
Отсюда легко записать решение исходной ЗЛП: max f(x) = 2300 и достигается при х 1 = 70 и х 2 = 80 (см. рис. 1.4).
1.3.ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ В СРЕДЕ EXCEL
1.3.1. Общие сведения о работе с табличным процессором Excel
Рассмотрим некоторые аспекты работы с табличным процессором Excel, которые позволят упростить расчеты, необходимые для решения оптимизационных задач. Табличный процессор - это программный продукт, предназначенный для автоматизации обработки данных табличной формы.
Элементы экрана Excel. После запуска Excel на экране появляется таблица, вид которой показан на рис 1.5.
Это изображение называют рабочим листом. Оно представляет собой сетку строк и столбцов, пересечения которых образуют прямоугольники, называемые ячейками. Рабочие листы предназначены для ввода данных, выполнения расчетов, организации информационной базы и т.п. Окно Excel отображает основные программные элементы: строку заголовка, строку меню, строку состояния, кнопки управления окнами.
Работа с формулами. В программах электронных таблиц формулы служат для выполнения множества разнообразных расчетов. С помощью Excel можно быстро создать формулу. Формула состоит из трех основных частей:
1) знака равенства;
2) совокупности значений или ссылок на ячейках, с которыми выполняются расчеты;
3) операторов.
4) Если знак равенства отсутствует, то Excel интерпретирует данные не как формулу, а как ввод данных в ячейку. Формулы можно вводить непосредственно в ячейку или в строку формул – как текст, так и число. При этом нужно выполнить следующие действия:
· выделить ячейку, которая должна содержать формулу и ввести знак (=);
· ввести оператор или знак действия;
· выделить другую ячейку, включаемую в формулу;
· нажать на клавишу Enter.
В строке формул появится введенная формула, в ячейке – результат расчета.
Использование в формулах функций. Чтобы облегчить ввод формул, можно воспользоваться функциями Excel. Функции - это встроенные в Excel формулы. Excel содержит множество формул. Они сгруппированы по различным типам: логические, математические, инженерные, статистические и др.
Для активизации той или иной формулы следует нажать кнопки Вставка, Функции. В появившемся окне Мастер функций слева содержится перечень типов функций. После выбора типа справа будет помещен список самих функций. Выбор функции осуществляется щелчком клавиши мыши на соответствующем названии.
Различные функции выполняют разные типы вычислений по определенным правилам. Когда функция является единичным объектом в ячейке рабочего листа, она начинается со знака (=), далее следует название функции, а затем - аргументы функции, заключенные в скобки.
Поиск решения - это надстройка Excel, которая позволяет решать оптимизационные задачи. Если в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервис => Надстройки и активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.
После выбора команд Сервис => Поиск решения появится диалоговое окно Поиск решения.
В диалоговом окне Поиск решения есть три основных параметра;
Установить целевую ячейку.
Изменяя ячейки.
Ограничения.
Сначала нужно заполнить поле Установить целевую ячейку. Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или установить конкретное значение.
Второй важный параметр средства Поиск решения - это параметр Изменяя ячейки. Здесь указываются ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К этим ячейкам предъявляется два основных требования: они не должны содержать формул и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависит от изменяемых ячеек.
Третий параметр, который нужно вводить на вкладке Поиск решения, - это ограничения.
Для решения задачи необходимо:
1) указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки);
2) ввести исходные данные;
3) ввести зависимость для целевой функции;
4) ввести зависимости для ограничении,
5) запустить команду Поиск решений;
6) назначить ячейку для целевой функции (установить целевую ячейку);
7) ввести ограничения;
8) ввести параметры для решения ЗЛП.
Рассмотрим технологию решения, используя условия примера 1.1 (задача о костюмах).
Экономико-математическая модель задачи
Пусть х 1 - число женских костюмов; х 2 - число мужских костюмов,
10 х х 1 + 20 х х 2 max
Ограничения задачи имеют вид:
х 1 + х 2 150 - ограничение по труду;
2 x х 1 + 0,5 х х 2 240 - ограничение по лавсану;
х 1 + 3,5 х х 2 350 - ограничение по шерсти;
х 2 60 - ограничение по мужским костюмам;
х 1 0 - ограничение по женским костюмам.
1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).
Обозначьте через x 1 , х 2 количество костюмов каждого типа. В нашей задаче оптимальные значения вектора = (х 1 , х 2) будут помещены в ячейках А2:В2, оптимальное значение целевой функции - в ячейке СЗ.
2. Ввести исходные данные.
Введите исходные данные задачи, как показано на рис. 1.6.
3. Ввести зависимость для целевой функции.
· Поместить курсор в ячейку «СЗ», произойдет выделение ячейки.
· Поместить курсор на кнопку Мастер функций, расположенную на панели инструментов.
· Ввести Enter. На экране появляется диалоговое окно Мастер функций шаг 1 из 2.
· В окне Функции выбрать строку СУММПРОИЗВ (рис. 1.7). На экране
· появляется диалоговое окно СУММПРОИЗВ (рис. 1.8).
· В строку Массив 1 ввести А2:В2 .
· В строку Массив 2 ввести АЗ:ВЗ.
Массив 1 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку. На рис. 1.9 показано, что в ячейку СЗ введена функция.
5. Ввести зависимости для ограничений (рис 1.10).
· Поместить курсор в ячейку СЗ.
· На панели инструментов кнопка Копировать в буфер.
· Поместить курсор в ячейку С4.
· Поместить курсор в ячейку С5.
· На панели инструментов кнопка Вставить из буфера.
· Поместить курсор в ячейку Сб.
· На панели инструментов кнопка Вставить из буфера.
· Поместить курсор в ячейку С7.
· На панели инструментов нажать кнопку Вставить из буфера. (Содержимое ячеек С4-С7 необходимо проверить. Они обязательно должны содержать информацию, как это показано для примера на рис. 1.11; в качестве примера представлено содержимое ячейки С5.)
· В строке Меню указатель мышки поместить на Сервис. В развернутом меню выбрать команду Поиск решения. Появляется диалоговое окно Поиск решения (рис. 1.12).
5. Запустить команду Поиск решения.
6. Назначить ячейку для целевой функции (установить целевую ячейку), указать адреса изменяемых ячеек.
· Поместить курсор в строку Установить целевую ячейку.
· Ввести адрес ячейки $С$3.
· Ввести тип целевой функции в зависимости от условия вашей задачи. Для этого отметьте, чему равна целевая функция - Максимальному значению или Минимальному значению.
· Поместить курсор в строку Изменяя ячейки.
· Ввести адреса искомых переменных А$2:В$2 (рис. 1.13).
7. Ввести ограничения.
· Поместить указатель мыши на кнопку Добавить. Появляется диалоговое окно Добавление ограничения.
· Ввести знак ограничения.
· В строке Ограничение ввести адрес $D$4 (рис. 1.14).
· Поместить указатель мыши на кнопку Добавить. На экране вновь появится диалоговое окно Добавление ограничения.
· Ввести остальные ограничения задачи по вышеописанному алгоритму.
· После введения последнего ограничения нажать на кнопку ОК. На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 1.15).
8. Ввести параметры для решения задачи линейного программирования.
· В диалоговом окне поместить указатель мышки на кнопку Параметры. На экране появится диалоговое окно Параметры поиска решения (рис. 1.16).
· Установить флажки в окнах Линейная модель (это обеспечит применение симплекс-метода) и Неотрицательные значения.
· Поместить указатель мыши на кнопку ОК. На экране появится диалоговое окно Поиск решения.
· Поместить указатель Мыши на кнопку Выполнить.
Через непродолжительное время появятся диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками АЗ:ВЗ для значений х i и ячейка СЗ с максимальным значением целевой функции (рис. 1.17).
Если указать тип отчета Устойчивость, то можно получить дополнительную информацию об оптимальном решении (рис. 1.18).
В результате решения задачи был получен ответ: необходимо сшить 70 шт. женских костюмов и 80 шт. мужских костюмов, чтобы получить максимальную прибыль 2300 у.е.
1.4. ДВОЙСТВЕННОСТЬ В ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. АНАЛИЗ ПОЛУЧЕННЫХ ОПТИМАЛЬНЫХ РЕШЕНИЙ
В 1975 г. наш соотечественник Л.В. Канторович был удостоен Нобелевской премии по экономике (совместно с американским экономистом Т. Купмансом) за разработку теории оптимального использования ресурсов (см. Приложение 1).
С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной; первоначальная задача называется исходной, или прямой. Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.
Переменные двойственной задачи y i называются объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.
Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой.
Двойственная задача по отношению к исходной составляется согласно следующим правилам:
1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи - на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид (), в задаче на минимум - вид ( );
2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица А Т в двойственной задаче получаются друг из друга транспонированием;
3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной;
4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи - коэффициенты при неизвестных в целевой функции исходной; j 0.
Две приведенные задачи образуют пару симметричных двойственных задач. Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.
Первая теорема двойственности. Для взаимно двойственных задач имеет место один из взаимоисключающих случаев.
1. В прямой и двойственной задачах имеются оптимальные решения,
при этом значения целевых функций на оптимальных решениях
совпадают
2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.
3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.
4. Обе из рассматриваемых задач имеют пустые допустимые множества.
Вторая теорема двойственности (теорема о дополняющей нежесткости). Пусть = (x 1 ,х 2 ,..., х п) - допустимое решение прямой задачи, a = (у 1 ,у 2 ,…,у т) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач, необходимо и достаточно, чтобы выполнялись следующие соотношения:
Условия (1.4) и (1.5) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.
Рассмотрим еще одну теорему, выводы которой будут использованы в дальнейшем.
Теорема об оценках. Значения переменных y i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b i системы ограничений (неравенств) прямой задачи на величину
Решая ЗЛП симплекс-методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи y i называют объективно обусловленными оценками.
Рассмотрим экономическую интерпретацию двойственной задачи на примере задачи о коврах.
Пример 1.2. Используя постановку задачи о коврах, выполнить следующие задания.
1. Сформулировать экономико-математическую модель задачи о коврах на максимум общей стоимости продукции, используя данные табл. 1.1.
2. Используя Поиск решения, найти такой план выпуска продукции, при котором общая стоимость продукции будет максимальной.
3. Сформулировать экономико-математическую модель двойственной задачи к задаче о коврах.
4. Найти оптимальный план двойственной задачи, используя теоремы двойственности, пояснить равенство нулю Х 1 и Х 4 .
5. Используя протоколы Поиска решения, выполнить анализ полученного оптимального решения исходной задачи.
6. Определить, как изменится общая стоимость и план выпуска продукции при увеличении запаса ресурса труб на 12 ед.
1. Сформулируем экономико-математическую модель задачи.
Обозначим через Х 1 , Х 2 , Х 3 , Х 4 число ковров каждого типа. Целевая функция имеет вид
F(X) = ЗХ 1 + 4Х 2 + ЗХ 3 + Х 4 max,
а ограничения по ресурсам
7Х 1 + 2Х 2 + 2Х 3 + 6Х 4 80,
5Х 1 + 8Х 2 + 4 Х 3 + ЗХ 4 480,
2Х 1 + 4 Х 2 + Х 3 + 8X 4 130,
Х 1 , X 2 , X 3 , Х 4 0.
2. Поиск оптимального плана выпуска.
Решение задачи выполним с помощью надстройки Excel Поиск решения. Технология решения задачи была подробно рассмотрена в задаче о костюмах. В нашей задаче оптимальные значения вектора Х=(Х 1 , X 2 , X 3 , Х 4) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции - в ячейке F4 .
Введем исходные данные. Сначала опишем целевую функцию с помощью функции - СУММПРОИЗВ (рис. 1.19). А потом введем данные для левых частей ограничений. В Поиске решения введем направление целевой функции, адреса искомых переменных, добавим ограничения. На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 1.20).
После ввода параметров для решения ЗЛП следует нажать кнопку Выполнить. На экране появится сообщение, что решение найдено (рис. 1.21).
Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы «труд» и «оборудование» будут использованы полностью, а из 480 кг пряжи (ресурс «сырье») будет использовано 280 кг.
Создание отчета по результатам поиска решения. Excel позволяет представить результаты поиска решения в форме отчета (табл. 1.4). Существует три типа таких отчетов:
· Результаты (Answer). В отчет включаются исходные и конечные значения целевой и изменяемых ячеек, дополнительные сведения об ограничениях.
· Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений.
· Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек, в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.
Цех изготавливает изделия А и Б. Расход сырья, его запас и прибыль от реализации каждого изделия указаны в таблице.
| Вид сырья | Расход на изделие | Запас | А | Б | 48 | 12 | 600 | 24 | 21 | 840 | 15 | 27 | 1350 | Прибыль | 12 | 18 |
Найти план производства изделий, обеспечивающий предприятию максимальную прибыль от их реализации. Решить задачу графическим методом.
Решение задачи
Экономико-математическая модель задачи
Через и обозначим количество выпускаемой продукции вида А и Б соответственно.
Тогда ограничения на ресурсы:
Кроме того, по смыслу задачи
Целевая функция, выражающая получаемую прибыль от реализации изделий:
Получаем следующую экономико-математическую модель:
Построение чертежа
Для построения области допустимых решений строим в системе координат соответствующие данным ограничениям-неравенствам граничные прямые:
Найдем точки, через которые проходят прямые:
Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее.
Для определения полуплоскости возьмём любую точку, например точку не принадлежащую прямой (1), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:
Области решений соответствующего 1-го неравенства соответствует левая полуплоскость
Возьмём любую точку, например точку не принадлежащую прямой (2), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:
Области решений соответствующего 2-го неравенства соответствует левая полуплоскость
Для определения полуплоскости возьмём любую точку, например точку не принадлежащую прямой (3), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:
Области решений соответствующего 3-го неравенства соответствует нижняя полуплоскость
Областью допустимых решений является фигура .
Строим вектор , координаты которого пропорциональны коэффициентам целевой функции.
Перпендикулярно к построенному вектору проводим линию уровня .
Нахождение оптимального плана
Перемещаем линию уровня в направлении вектора так, чтобы она касалась области допустимых решений в крайней точке. Решением на максимум является точка D, координаты которой находим как точку пересечения прямой (2) и оси .
Таким образом, необходимо выпускать 40 ед. изделия Б. Изделие а выпускать невыгодно. При этом прибыль будет максимальной и составит 720 д.е.
Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.
Каждое из неравенств задачи ЛП определяет на координатной плоскости (х 1 ,х 2 ) некоторую полуплоскость (рис. 1), а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена, выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.
Примечание № 1. Все вышесказанное относится и к случаю, когда система ограничений (1.1) включает равенства, поскольку любое равенство
a il x 1 +a i 2 x 2 =b
можно представить в виде системы двух неравенств (рис. 1)
A i 2 x 2 <Ь 1э +a i 2 x 2 >bj.
ЦФ L(x)= с1х1 + с2х2 при фиксированном значении L(х)=L определяет на плоскости прямую линию с1х1 + с2х2 = L. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.
Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси х2 (начальная ордината), а угловой коэффициент прямой tgа = -- останется постоянным (рис. 1).
Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.
Вектор C = (c1;c2) с координатами из коэффициентов ЦФ при х1 и х2 перпендикулярен к каждой из линий уровня (см. рис. 1). Направление вектора С совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора С.
Суть графического метода заключается в следующем. По направлению (против направления) вектора С в ОДР производится поиск оптимальной точки X = (х1; х2). Оптимальной считается точка, через которую проходит линия уровня L max (L min), соответствующая наибольшему (наименьшему) значению функции L(x). Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.
Допустимая область - полуплоскость
Рисунок 1
1.2. Методика решения задач лп графическим методом
I. Вограничениях задачи замените знаки неравенств на знаки точных равенств и постройте соответствующие прямые.
II. Найдите и заштрихуйте полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого подставьте в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверьте истинность полученного неравенства.
Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку х1 и х2 должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси х 1 и правее оси х2, т.е. в 1-м квадранте.
Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой, поэтому выделите на графике такие прямые.
Определите ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделите ее. При отсутствии ОДР задача не имеет решений, о чем сделайте соответствующий вывод.
Если ОДР - не пустое множество, то постройте целевую прямую, т.е. любую из линий уровня с 1 х 1 + с 2 х 2 = L, где L - произвольное число, например, кратное с 1 и с 2 , т.е. удобное для проведения расчетов. Способ построения аналогичен построению прямых ограничений.
V. Постройте вектор C = (c 1 ,с 2), который начинается в точке (0;0), заканчивается в точке (c 1 ,с 2). Если целевая прямая и вектор С построены верно, то они будут перпендикулярны.
VI. При поиске max ЦФ передвигайте целевую прямую в направлении вектора С, при поиске min ЦФ - против направления вектора С. Последняя по ходу движения вершина ОДР будет точкой max или min ЦФ. Если такой точки (точек) не существует, то сделайте вывод о неограниченности ЦФ на множестве планов сверху (при поиске шах) или снизу (при поиске min).
Определите координаты точки max (min) ЦФ X = (х1 * ; х2 * ) и вычислите значение ЦФ l(x *). Для вычисления координат оптимальной точки X * решите систему уравнений прямых, на пересечении которых находится X * .
Задача 1
Найдем оптимальное решение задачи, математическая модель которой имеет вид
L(Х) = 3x 1 + 2x 2 → max
х 1 + 2х 2 < 6, (1)
2х 1 + х 2 < 8, (2)
Х 1 +х 2 <1, (3)
х 2 < 2, (4)
х 1 >0,х 2 >0.
Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис. 2).
х 1 + 2х 2 = 6,(1)
2х1 + х2= 8,(2)
(1) х1=0, х1=6, х2=3, х2=0,
(2) х1=0, х1=4, х2=8, х2=0,
(3) х1=0, х1=-1, х2=1, х2=0,
Прямая (4) проходит через точку х 2 = 2 параллельно оси L(Х).
Рис. 2. Графическое решение задачи
Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (3), получим 0 < 1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (3). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (рис. 2). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDEF.
Целевую прямую можно построить по уравнению
Строим вектор С из точки (0;0) в точку (3;2). Точка Е- это последняя вершина многоугольника допустимых решений ABCDEF, через которую проходит целевая прямая, двигаясь по направлению вектора С. Поэтому Е -это точка максимума ЦФ. Определим координаты точки Е из системы уравнений прямых ограничений (1) и (2)
Х1 +2х 2 =6, (1) х1=10/3=3 1/3, х2=4/3=1 1/3
2 Х1 +х 2 =8, (2) Е 3 1/3; 1 1/3
Максимальное значение ЦФ равно L(E) = 3*10/3+2*4/3 = 12 2 / 3
Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 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.\]
Решение симплекс-методом
Симплексный метод является универсальным методом решения задачи линейного грограммирования, так как позволяет решить практически любую задачу, представленную в каноническом виде.
Идея симплексного метода заключатся в том, что, начиная с некоторого опорного решения, осуществляется последовательно направленное перемещение по опорным решениям системы к оптимальному опорному решению. Так как число опорных решений конечно, то через конечное число шагов оптимальное решение будет найдено.
Алгорим симплексного метода можно описать следующим образом:
- Привести задачу к каноническому виду
- Найти неотрицательное базисное решение системы ограничений
- Рссчитать оценки свободных переменных по формуле:
\[{\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 – коэффициенты при свободной переменной в целевой функции,
- Проверить найденное опорное решение на оптмальность:
а) если все оценки \({\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 предоставляет достаточно удобный механизм для решения задач линейного программирования.
Вконтакте