Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными. Рассмотрим задачу ЛП в стандартной форме:
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)
Условия (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). Помимо исходных и конечных значений изменяемых и целевой ячеек, в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.
Решение задачи линейного программирования (ЗЛП) графическим методом
Общая постановка злп
Найти значения n переменных x 1 , x 2 , …,x n , доставляющих экстремум (минимум или максимум) линейной функции Z=C 1 x 1 ,+ C 2 x 2+…+ C n x n
и одновременно удовлетворяющих m ограничениям вида
a 1,1 x 1 +a 1,2 x 2 +…+a 1,n x n £ =≥b 1 ,
a 2,1 x 1 +a 2,2 x 2 +…+a 2,n x n £ = ≥b 2 ,
. . . . . . . . . . . . . . . . . . . . . . .,
a m,1 x 1 +a m,2 x 2 +…+a m,n x n £ = ≥b m ,
при заданных a i,j , b i, C j (i=1,2,…,m; j=1,2,…,n). Знак отношения может принимать любое из трех приведенных значений.
Пример задачи линейного программирования
Рассмотрим следующую задачу. Менеджер предприятия, изготавливающего два вида красок, описал исследователю операций ситуацию, сложившуюся на производстве и рынке сбыта красок. Оказалось, что фабрика изготавливает два вида красок: для внутренних и внешних работ. Обе краски поступают в оптовую продажу. Для производства красок используются два исходных продукта – А и В. Максимально возможные суточные запасы этих продуктов 6 и 8 тонн соответственно. Опыт показал, что суточный спрос на внешнюю краску никогда не превышает спрос на внутреннюю более чем на 1 тонну. Кроме того, установлено, что спрос на внешнюю краску никогда не превышает 2 тонны в сутки. Оптовые цены одной тонны красок сложились следующим образом: 3 тысячи рублей на внешнюю краску и 2 тысячи рублей – на внутреннюю. Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации был максимальным?
Чтобы решить поставленную перед исследователем задачу, сначала необходимо разработать математическую модель описанной ситуации.
При построении математической модели специалист по исследованию операций ставит перед собой три вопроса.
- Для каких величин должна быть построена модель? Иначе говоря, нужно идентифицировать переменные задачи.
- Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?
- В чем состоит цель, для достижения которой из всех возможных (допустимых) значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?
Введем переменные:
x 1 – суточный объем производства внешней краски (в тоннах),
x 2 – суточный объем производства внутренней краски (в тоннах).
Учитывая оптовые цены на тонну каждого вида краски, суточный доход от продажи произведенной продукции задается линейной целевой функцией Z = 3x 1 + 2x 2 .
Целью производства является получение максимальной прибыли, значит, необходимо найти значения x 1 и x 2 , которые максимизируют целевую функцию Z.
Поскольку производитель красок не может распорядиться значениями переменных произвольным образом, постольку необходимо выделить множество возможных значений этих переменных, которое определяется конкретными условиями производства и сбыта. Это множество называется областью допустимых значений.
Первый тип ограничений определяется запасами продуктов А и В, из которых производятся краски. Из технологии производства известно, что на производство тонны внешней краски идут две части продукта А, а на тонну внутренней – одна часть. Для продукта В соотношение обратное. Эти технологические условия описываются неравенствами
2x 1 + x 2 £ 6 (на складе 6 тонн продукта А),
x 1 + 2x 2 £ 8 (на складе 8 тонн продукта В).
Последние два ограничения означают очевидное обстоятельство: нельзя использовать для производства красок больше продуктов А и В, чем их имеется фактически на складе.
Ситуация с реализацией красок на рынке приводит к следующим ограничениям: x 1 – x 2 £ 1 (внешней краски реализуется не более, чем на одну тонну больше внутренней), x 1 £ 2 (внешней краски продается не более двух тонн в день).
Суммируя все сказанное, можно математическую модель, описывающую сложившуюся производственную ситуацию, задать в следующей форме:
найти ® max{ Z=2× x 1 + 3× x 2 } при следующих ограничениях на значения переменных x 1 и x 2
2 × x 1 + x 2 £ 6 ограничение (1),
X 1 + 2 × x 2 £ 8 ограничение (2),
X 1 - x 2 £ 1 ограничение (3),
X 1 £ 2 ограничение (4)
и требование неотрицательности переменных x 1 ³ 0 (5), x 2 ³ 0 (6).
Полученная математическая модель представляет собой задачу линейного программирования.
Графический метод решения злп
Графический метод решения злп может быть реализован только в двумерном случае.
Математическая модель, полученная для сформулированной типовой задачи, требует исследования, так как заранее не известно, имеет ли она (как математическая задача) решение. Исследование проведем с использованием графических построений. Одновременно с таким исследованием найдем (если оно есть) и решение.
1 этап. Построение области допустимых решений
Цель – построить область, каждая точка которой удовлетворяет всем ограничениям.
Каждое из шести ограничений геометрически задает полуплоскость. Для того, чтобы ее построить, нужно:
- · заменить в ограничении знак неравенства на равенство (получим уравнение прямой);
- · построить прямую по двум точкам;
- · определить, какую полуплоскость задает знак неравенства. Для этого подставить в неравенство какую-нибудь точку (например, начало координат). Если она удовлетворяет неравенству – закрашиваем полуплоскость, ее содержащую.
Такие действия выполняем для всех ограничений. Каждую из прямых обозначим номерами, принятыми при нумерации ограничений (см. рис).
Областью допустимых решений (удовлетворяющей всем ограничениям) является множество точек первого квадранта координатной плоскости (x 1 , x 2), представляющее собой пересечение всех полуплоскостей, определяемых неравенствами ограничений.
Множество точек, удовлетворяющих всем шести ограничениям задачи – многоугольник AFEDCB.
2 этап Построение линий уровня целевой функции и определение точки максимума
Цель - найти в построенном многоугольнике A FEDCB точку, в которой функция цели Z=2x 1 + 3x 2 принимает максимальное значение.
Проведем прямую 2x 1 + 3x 2 = Сonst (линию уровня) так, чтобы она пересекала многоугольник AFEDCB (например, Const=10). Эта линия уровня на рисунке изображена пунктирной линией.
Если рассматривать значения линейной целевой функции Z на множестве точек (x 1 ,x 2), принадлежащих отрезку пунктирной прямой, расположенному внутри шестиугольника, то все они равны одному и тому же значению (Const=10).
Определим направление возрастания функции. Для этого построим линию уровня с бОльшим значением. Это будет прямая, параллельная с построенной, но расположенная правее. Значит, в заданном направлении значение целевой функции возрастает, и в наших интересах сдвинуть ее как можно дальше в этом направлении.
Сдвиг можно продолжать до тех пор, пока перемещаемая прямая пересекает многоугольник допустимых решений. Последнее положение прямой, когда она имеет одну общую точку с многоугольником AFEDCB (точка С), соответствует максимальному значению целевой функции Z и достигается в точке С с координатами x 1 = 4/3 (» 1.333), x 2 =10/3 (» 3.333). При этом Z = 38/3 (» 12.667).
Поставленная задача полностью решена. Из проведенных геометрических рассуждений видно, что решение единственное. Сделаем некоторые обобщения, вытекающие из геометрической интерпретации задачи.
Первое . Область допустимых решений – выпуклый многоугольник (Почему выпуклый? Может ли область допустимых решений представлять собой пустое множество? Точку? Отрезок? Луч? Прямую? Если да, приведите пример системы ограничений ).
Второе . Максимум целевой функции достигается в вершине многоугольника допустимых решений (а может ли быть не единственное решение? Может ли решения не быть? )
Задание 1 (выполнить на занятии, показать преподавателю)
Решить графическим методом
|
А) F =2 x 1 +3 x 2 è max При ограничениях x 1 +3 x 2 ≤ 18 2 x 1 + x 2 ≤ 16 x 2 ≤ 5 3 x 1 ≤ 21 x 1 ≥ 0 x 2 ≥ 0 |
B ) F =4 x 1 +6 x 2 è min При ограничениях 3 x 1 + x 2 ≥ 9 x 1 +2 x 2 ≥ 8 x 1 +6x 2 ≥ 12 x 1 ≥ 0 x 2 ≥ 0 |
|
C ) F =3 x 1 +3 x 2 è max При ограничениях x 1 +x 2 ≤ 8 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 2 x 1 ≥ 0 x 2 ≥ 0 |
D ) F =2 x 1 -3 x 2 è min При ограничениях x 1 +x 2 ≥ 4 2x 1 -x 2 ≥ 1 x 1 -2x 2 ≤ 1 x 1 ≥ 0 x 2 ≥ 0 |
A) x1=6 x2=4 F=24
B) x1=2 x2=3 F=26
C) x1Î x2=8-x1 F=24
Задание 2 (выполнить на занятии, показать преподавателю)
Ответить на вопросы, выделенные курсивом.
Задание 3 (домашнее)
Написать программу.
Дан текстовый файл вида
2 3 (коэффициенты целевой функции)
4 (количество ограничений)
2 2 12 (ограничения)
1 2 8
4 0 16
0 4 12
Построить прямые так, чтобы многоугольник допустимых решений был целиком на экране (определение масштаба см. в кн. Онегова). Прямые могут быть параллельны осям!
Построить несколько линий уровня целевой функции (нажимаем клавишу – прямая перемещается, отображается значение целевой функции). Отобразить масштаб.
Пример 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-документа:
построение области допустимых решений задачи
Ответ: рассматриваемая задача линейного программирования не имеет решения в силу несовместности системы ограничений.
Если после подстановки координат контрольной точки в неравенство его смысл нарушается, то решением данного неравенства является полуплоскость не содержащая данную точку (т.е. расположенная по другую сторону прямой).
Направление, обратное вектору-градиенту, соответствует направлению минимизации целевой функции.
Наиболее простым и наглядным методом решения задачи линейного программирования (ЗЛП) является графический метод. Он основан на геометрической интерпретации задачи линейного программирования и применяется при решении ЗЛП с двумя неизвестными:
Будем рассматривать решение этой задачи на плоскости. Каждое неравенство системы функциональных ограничений геометрически определяет полуплоскость с граничной прямой а п х, + + a j2 х 2 = b n i = 1, т. Условия неотрицательности определяют полуплоскости с граничными прямыми х { = 0, х 2 = 0 соответственно. Если система совместна, то полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек; координаты каждой из этих точек являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограниченным многоугольником.
Геометрически ЗЛП представляет собой отыскание такой угловой точки многоугольника решений, координаты которой доставляют максимальное (минимальное) значение линейной целевой функции, причем допустимыми решениями являются все точки многоугольника решений.
Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую область на плоскости.
Определим, какую часть плоскости описывает неравенство 2х { + Зх 2 12.
Во-первых, построим прямую 2х, + Зх 2 =
12. Она проходит через точки (6; 0) и (0; 4). Во-вторых, определим, какая полуплоскость удовлетворяет неравенству. Для этого выбираем любую точку на графике, не принадлежащую прямой, и подставляем ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать начало координат. Подставим х { = х 2 =
0 в неравенство 2х, + Зх 2 12. Получим 2 0 + 3 0
Аналогично графически можно изобразить все ограничения задачи линейного программирования.
Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений (ОДР) или областью определения.
Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (Xj > 0, j = 1, п). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.
Для нахождения экстремального значения целевой функции при графическом решении ЗЛП используют вектор-градиент, координаты которого являются частными производными целевой функции:
Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая c [ x l + с 2 х 2 = f(x 0), перпендикулярная вектору-градиенту, является линией уровня целевой функции (рис. 2.2.2). В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине а. Меняя значение а, получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.
Рис. 2.2.2.
Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в д р у г у ю сторону - только убывает.
Графический метод решения ЗЛП состоит из четырех этапов:
- 1. Строится область допустимых решений (ОДР) ЗЛП.
- 2. Строится вектор-градиент целевой функции (ЦФ) с началом в точке х 0 (0; 0): V = (с, с 2).
- 3. Линия уровня CjXj + с 2 х 2 = а (а - постоянная величина) - прямая, перпендикулярная вектору-градиенту V, - передвигается в направлении вектора-градиента в случае максимизации целевой функции f(x v х 2) до тех пор, пока не покинет пределов ОДР. При минимизации /(*, х 2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Крайняя точка (или точки) ОДР при этом движении и является точкой максимума (минимума) f(x p jc 2).
Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимума (максимума) функции f(x р х 2) не существует.
Если линия уровня целевой функции параллельна функциональному ограничению задачи, на котором достигается оптимальное значение ЦФ, то оптимальное значение ЦФ будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением ЗЛП.
4. Определяются координаты точки максимума (минимума). Для этого достаточно решить систему уравнений прямых, дающих в пересечении точку максимума (минимума). Значение f(x { , х 2), найденное в полученной точке, является максимальным (минимальным) значением целевой функции.
Возможные ситуации графического решения ЗЛП представлены в табл. 2.2.1.
Таблица 2.2.1
|
Вид ОДР |
Вид оптимального решения |
|
Ограниченная |
Единственное решение |
|
Бесконечное множество решений |
|
|
Неограниченная |
ЦФ не ограничена снизу |
|
ЦФ не ограничена сверху |
|
|
Единственное решение |
|
|
Бесконечное множество решений |
|
|
Единственное решение |
|
|
Бесконечное множество решений |
Пример 2.2.1. Планирование выпуска продукции пошивочного предприятия (задача о костюмах).
Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человекодень трудозатрат; на мужской - 3,5 м шерсти, 0,5 м лавсана и 1 человекодень трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человекодней трудозатрат.
Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 ден. ед., а от мужского - 20 ден. ед. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.
Экономико-математическая модель задачи
Переменные : х, - число женских костюмов; х 2 - число мужских костюмов.
Целевая функция :
Ограничения :
Первое ограничение (по шерсти) имеет вид х { + 3,5х 2 х { + 3,5х 2 = 350 проходит через точки (350; 0) и (0; 100). Второе ограничение (по лавсану) имеет вид 2х { + 0,5х 2 2х х + 0,5х 2 = 240 проходит через точки (120; 0) и (0; 480). Третье ограничение (по труду) имеет вид х у +х 2 150. Прямая х { + х 2 = 150 проходит через точки (150; 0) и (0; 150). Четвертое ограничение (по количеству мужских костюмов) имеет вид х 2 > 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х 2 = 60.
В результате пересечения построенных четырех полуплоскостей получаем многоугольник, который и является областью допустимых решений нашей задачи. Любая точка этого многоугольника удовлетворяет всем четырем функциональным неравенствам, а для любой точки вне этого многоугольника хотя бы одно неравенство будет нарушено.
На рис. 2.2.3 затенена область допустимых решений (ОДР). Для определения направления движения к оптимуму построим вектор- градиент V, координаты которого являются частными производными целевой функции:
Чтобы построить такой вектор, нужно соединить точку (10; 20) с началом координат. Для удобства можно строить вектор, пропорциональный вектору V. Так, на рис. 2.2.3 изображен вектор (30; 60).
Затем построим линию уровня 10xj + 20х 2 = а. Приравняем целевую функцию постоянной величине а. Меняя значение а , получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.
Задача. Решить графически задачу линейного программирования, определив экстремальное значение целевой функции:
при ограничениях
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение 3x 1 +x 2 = 9
по двум точкам
.
Для нахождения первой точки приравниваем x 1 = 0. Находим x 2 = 9. Для нахождения второй точки приравниваем x 2 = 0. Находим x 1 = 3. Соединяем точку (0;9) с (3;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 3 . 0 + 1 . 0 - 9 ≤ 0, т.е. 3x 1 +x 2 - 9≥ 0 в полуплоскости выше прямой.
Построим уравнение x 1 +2x 2 = 8
по двум точкам
.
Для нахождения первой точки приравниваем x 1 = 0. Находим x 2 = 4. Для нахождения второй точки приравниваем x 2 = 0. Находим x 1 = 8. Соединяем точку (0;4) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 . 0 + 2 . 0 - 8 ≤ 0, т.е. x 1 +2x 2 - 8≥ 0 в полуплоскости выше прямой.
Построим уравнение x 1 +x 2 = 8
по двум точкам
.
Для нахождения первой точки приравниваем x 1 = 0. Находим x 2 = 8. Для нахождения второй точки приравниваем x 2 = 0. Находим x 1 = 8. Соединяем точку (0;8) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 . 0 + 1 . 0 - 8 ≤ 0, т.е. x 1 +x 2 - 8≤ 0 в полуплоскости ниже прямой.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.
Проверить правильность построения графиков функций можно с помощью калькулятора
Рассмотрим целевую функцию задачи F = 4x 1 +6x 2 → min.
Построим прямую, отвечающую значению функции F = 0: F = 4x 1 +6x 2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора - точка (0; 0), конец - точка (4; 6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Прямая F(x) =
4x 1 +6x 2 пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1)
и (2)
, то ее координаты удовлетворяют уравнениям этих прямых:
3x 1 +x 2 =9
x 1 +2x 2 =8
Решив систему уравнений, получим: x 1 = 2, x 2 = 3
Откуда найдем минимальное значение целевой функции:
F(X) = 4*2 + 6*3 = 26
