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

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

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

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

Операция – система управляемых действий, объединенная единым замыслом и направленная на достижение определенной цели.

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

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

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

Целевая функция – это количественный показатель предпочтительности или эффективности решений.

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

Математическая модель задачи ИО включает в себя:

1) описание переменных, которые необходимо найти;

2) описание критериев оптимальности;

3) описание допустимых решений (ограничений, накладываемых на переменные)

Цель ИО – количественно и качественно обосновать принимаемое решение. Окончательное решение принимает ответственное лицо либо группа лиц, называемое ЛПР – лицо, принимающее решение.

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

Привести общую ЗЛП к основной очень просто, используя следующие очевидные правила.

Минимизация целевой функции f равносильна максимизации функции g = – f .

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

Если на некоторую переменную x j не накладывается условие неотрицательности, то делают замену переменной,.

Линия уровня функции f , т. е. линию, вдоль которой эта функция принимает одно и то же фиксированное значение с , т. е. f (x 1 , x 2)= c

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

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

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

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

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

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

ОЗЛП будем называть канонической (КЗЛП), если система линейных уравнений этой задачи – каноническая, а целевая функция выражена только через свободные неизвестные.

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

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

Теорема 3 . (достаточное условие оптимальности) . Если все элементы индексной строки симплекс-таблицы задачи максимизации неотрицательны, то базисный план этой задачи является оптимальным, а с 0 есть максимум целевой функции на множестве планов задачи.

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

Симплекс-метод:

Записываем данную КЗЛП в исходную симплекс-таблицу.

Если все элементы индексной строки симплекс-таблицы неотрицательны, то базисный план задачи является оптимальным (теорема 3).

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

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

выбираем в таблице ключевой столбец, в основании которого находится какой-либо отрицательный элемент индексной строки;

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

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

При рассмотрении полученной симплекс-таблицы непременно представится один из трех случаев, описанных в пп. 2, 3, 4. Если при этом возникнут ситуации пп. 2 или 3, то процесс решения задачи завершается, если же возникнет ситуация п. 4, то процесс продолжается.

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

через конечное число шагов задача будет решена (возникнут ситуации пп. 2 или 3);

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

Эти задачи называются симметричными двойственными задачами . Отметим следующие особенности, связывающие эти задачи:

Одна из задач является задачей максимизации, а другая – минимизации.

В задаче максимизации все неравенства – ≤, а в задаче минимизации – ≥.

Число неизвестных одной задачи равно числу неравенств другой.

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

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

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

1. Привести все неравенства системы ограничений исходной задачи к одном смыслу – к каноническому виду.

2. Составить расширенную матрицу системы А, в которую включить столбец b i и коэффициенты целевой функции F.

3. Найти транспонированную матрицу А Т.

4. Записать двойственную задачу.

Теорема 5. Значение целевой функции задачи максимизации для любого ее плана не превосходит значения целевой функции двойственной к ней задачи минимизации для любого ее плана, т. е. имеет место неравенство:

f (x ) ≤ g (y ),

называемое основным неравенством двойственности .

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

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

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

Ценности ресурсов прямой ЗЛП представляет собой значения переменных в оптимальном решении двойственной задачи.

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

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

а) для всех базисных клеток плана (>0);

б) для всех свободных клеток (=0).

Метод потенциалов

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

Шаг 2. Найти исходное опорное решение (исходный опорный план) закрытой транспортной задачи.

Шаг 3. Проверить полученное опорное решение на оптимальность:

вычислить для него потенциалы поставщиков u i и потребителей v j

для всех свободных клеток (i , j ) вычислить оценки;

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

Шаг 4. Выбрать клетку (i * ,j * ) с наибольшей положительной оценкой и для нее построить замкнутый цикл перераспределения груза. Цикл начинается и заканчивается в выбранной клетке. Получим новое опорное решение, в котором клетка (i * , j * ) окажется занятой. Возвращаемся к третьему шагу.

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

Точка называется точкой локального максимума , если существует окрестность этой точки такая, что

Необходимые условия оптимальности

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

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

Если в точке x * первая производная функции равна нулю, а вторая производная >0, то функция в точке x * имеет локальный минимум, если 2 произв,<0 то функция в точке x * имеет локальный максимум.

Теорема 4. Если функция одной переменной имеет в точке x * производные до (n - 1) порядка, равные нулю, и производная n порялка не равна 0, то тогда,

если n четно, то точка x * является точкой минимума, если,fn(x)>0

точкой максимума, если fn(x)<0.

Если n нечетно, то точка x * – точка перегиба.

Числовая матрица называется матрицей квадратичной формы .

Квадратичная форма (5) называется положительно определенной , если для Q(X) >0 и отрицательно определенной , если для.Q(X)<0

Симметричная матрица A называется положительно определенной , если построенная по ней квадратичная форма (5) положительно определена.

Симметричная матрица называется отрицательно определенной , если построенная по ней квадратичная форма (6) отрицательно определена.

Критерий Сильвестра: матрица является положительно определенной, если все ее угловые миноры больше нуля.

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

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

Собственные числа – корни многочлена .

Достаточное условие оптимальности задается следующей теоремой.

Теорема 5. Если в стационарной точке матрица Гессе положительно определена, то эта точка – точка локального минимума, если матрица Гессе отрицательно определена, то эта точка – точка локального максимума.

Конфликт - это противоречие, вызванное противоположными интересами сторон.

Конфликтная ситуация – ситуация, в которой участвуют стороны, интересы которых полностью или частично противоположны.

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

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

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

Парная игра – игра, в которой участвуют только две стороны (два игрока).

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

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

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

Случайный ход – это случайно выбранное действие (например, выбор карты из перетасованной колоды).

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

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

Платежная матрица – полученная матрица A или, иначе, матрица игр ы.

Конечной игрой размерности (m  n) называется игра, определенная матрицей А размерности (m  n).

Максимином или нижней ценой игры назовем число alpa = max(i)(min aij)(j)

а соответствующая ему стратегия (строка) максиминной .

Минимаксом или верхней ценой игры назовем число Beta = min(j)(max aij)i

а соответствующая ему стратегия (столбец) минимаксной .

Нижняя цена игры всегда не превосходит верхнюю цену игры.

Игрой с седловой точкой называется игра для которой. Alp = beta

Ценой игры называется величина, v если.v = alp = beta

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

Теорема 2 . Основная теорема теории матричных игр.

Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

Т 3

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

игрой с природой – игра, в которой мы не обладаем информацией о поведении партнера

Риском r ij игрока при выборе стратегии А i в условиях H j называется разность

r ij = b j - a i ,

где b j - максимальный элемент в j - м столбце.

Графом называется совокупность непустого множества, называемого

множеством вершин графа и множества пар вершин, которые называются

ребрами графа.

Если рассматриваемые пар вершин являются упорядоченными, то граф

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

неориентированным. В

Маршрутом (путем) в графе, соединяющем вершины А и В, называется

последовательность ребер, первое из которых выходит из вершины А, начало

последующего совпадает с концом предыдущего, а последнее ребро входит в

вершину В.

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

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

Граф называется конечным, если число его вершин конечно.

Если вершина является началом или концом ребра, то вершина и ребро

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

Эйлеров путь (эйлерова цепь) в графе - это путь, проходящий по всем

рѐбрам графа и притом только по одному разу.

Эйлеров цикл - это эйлеров путь, являющийся циклом.

Эйлеров граф - граф, содержащий эйлеров цикл.

Полуэйлеров граф - граф, содержащий эйлеров путь (цепь).

Теорема Эйлера.

Эйлеров цикл существует тогда и только тогда, когда граф связный и в нѐм

отсутствуют вершины нечѐтной степени.

Теорема. Эйлеров путь в графе существует тогда и только тогда, когда граф

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

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

(корень) и крайние вершины (степени 1); пути от исходной вершины к крайним вершинам называются ветвями.

Сетью (или сетевым графиком) называется ориентированный конечный

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

Весом пути в графе будем называть сумму весов его ребер.

Кратчайшим путем из одной вершины в другую будем называть путь

минимального веса. Вес этого пути будем называть расстоянием между

вершинами.

Работа – это протяженный во времени процесс, требующий затрат ресурсов,

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

Событие – результат выполнения одной или нескольких работ

Путь – это цепочка следующих друг за другом работ, соединяющих

начальную и конечную вершины.

Продолжительность пути определяется суммой продолжительностей

составляющих его работ.

Правила составления сетевых графиков.

1. В сетевом графике не должно быть тупиковых событий (кроме

завершающего), т. е. таких, за которыми не следует ни одной работы.

2. Не должно быть событий (кроме исходного), которым не предшествует хотя

бы одна работа.

3. В сетевом графике не должно быть циклов.

4. Любые два события связаны не более, чем одной работой.

5. Сетевой график должен быть упорядочен.

Любой путь, начало которого совпадает с исходным событием, а конец – с

завершающим, называется полным путем. Полный путь, имеющий максимальную

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

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

Описание метода анализа иерархий

Построение матриц парных сравнений

Находим лямбда макс и решаем систему относительно вектора весов

Синтез локальных приоритетов

Проверка согласованности матриц парных сравнений

Синтез глобальных приоритетов

Оценка согласованности всей иерархии

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

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

Точка Х называетсявыпуклой линейной комбинацией точек , если выполняются условия

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

Можно доказать следующую теорему о представлении выпуклого многогран­ника.

Теорема 1.1. Выпуклый п-мерный многогранник является выпук­лой линейной комбинацией своих угловых точек.

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

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

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

Матричная форма записи:

Здесь С – матрица-строка, А – матрица системы, Х – матри­ца-столбец переменных, В – матрица-столбец свободных членов:

Векторная форма записи:

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

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

Теорема 1.2. Множество всех допустимых решений системы ог­раничений задачи линейного программирования является выпуклым.

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

и покажем, что она также является допустимым решением систе­мы (1.3). В самом деле

т.e. решение X удовлетворяет системе (1.3). Но так как , то и Х >0, т.е. решение удовлетворяет условию неотрицательности.

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

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

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

Доказательство: Будем полагать, что многогранник решений является огра­ниченным. Обозначим его угловые точки через , а оптимальное решение - через X* . Тогда F(X*) ³ F(X) для всех то­чек Х многогранника реше­ний. Если X* – угловая точка, то первая часть тео­ремы доказана.

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

Так как F(X) – линейная функция, получаем

В этом разложении среди значений выбе­рем максимальное. Пусть оно соответствует угловой точке X k (1 £ k £ р) ; обозначим его через М, т.е. . Заменим в выражении (1.5) каждое значение этим максимальным значением М. Тогда

По предположению Х * – оптимальное решение, поэтому, с одной стороны, ,но, с другой стороны, доказано, что
F(X*) £ М, следовательно, , где X k – угловая точка. Итак, существует угловая точка X k , в которой линейная функция принимает максимальное значение.

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

Пусть Х – выпуклая линейная комбинация этих угловых точек, т.е.

В этом случае, учитывая, что функция F(X) – линейная, полу­чим

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

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

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

Следующая теорема посвящена аналитическому методу нахождения угловых точек.

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

Доказательство: Пусть – допустимое базисное решение системы ограничений ЗЛП (1.4), в котором первые т компонент - основные переменные, а остальные п - т компо­нент – неосновные переменные, равные нулю в базисном реше­нии (если это не так, то соответствующие переменные можно перенумеровать). Покажем, что Х

Предположим противное, т.е. что Х не является угловой точ­кой. Тогда точку Х можно представить внутренней точкой отрез­ка, соединяющего две различные, не совпадающие с X, точки

другими словами, – выпуклой линейной комбинацией точек многогранника решений, т.е.

где (полагаем, что , ибо в противном случае точка Х совпадает с точкой Х 1 или Х 2).

Запишем векторное равенство (1.6) в координатной форме:

Т.к. все переменные и коэффициенты неотрицательны, то из последних п-т равенств следует, что , т.е. в решениях Х 1 , Х 2 и Х системы уравнений (1.4) значения п - т компонент равны в данном случае нулю. Эти компоненты можно считать значениями неосновных переменных. Но значения неосновных переменных однозначно определяют значения основных, следовательно,

Таким образом, все п компонент в решениях Х 1 , Х 2 и Х совпада­ют, и значит, точки Х 1 и Х 2 сливаются, что противоречит допуще­нию. Следовательно, X – угловая точка многогранника решений.

Докажем обратное утверждение. Пусть – угловая точка многогранника решений и первые ее т координат положительны. Покажем, что Х – допустимое базис­ное решение. не является угловой точкой, что противоречит условию. Следовательно, наше допуще­ние неверно, т.е. векторы линейно независимы и Х – допустимое базисное решение задачи (1.4).

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

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

Общая задача линейного программирования (ОЗЛП) формулируется следующим образом – найти переменные задачи x 1 , x 2 , ..., x n , которые обеспечивают экстремум целевой функции

Допустимым решением (планом) задачи линейного программирования (ЗЛП) называется любой n -мерный вектор X =(x 1 , x 2 , ..., x n), удовлетворяющий системе ограничений равенств и неравенств. Множество допустимых решений задачи образует область допустимых решений D .

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

Каноническая задача линейного программирования (КЗЛП) имеет вид

(1.2)

Она отличается от ОЗЛП тем, что её система ограничений является системой только уравнений и все переменные неотрицательные.

Приведение ОЗЛП к каноническому виду ЗЛП:

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

Если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных x n +1 ≥ 0 они преобразуются в равенства:

неравенство a i 1 x 1 +…+a in x n ≥ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ,

неравенство a i 1 x 1 +…+a in x n ≤ b i заменяется на равенство a i 1 x 1 +…+a in x n + x n +1 = b i ;

Если некоторая переменная x k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательны-ми переменными: x k = x " k – x ” k , где x " k ≥ 0. x ” k ≥ 0.

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

ЗЛП с двумя неизвестными имеет вид:

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

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

Областью решения неравенства a i 1 x 1 +a i 2 x 2 ≤ b i является одна из двух полуплоскостей, на которые прямая a i 1 x 1 +a i 2 x 2 = b i , соответствующая этому неравенству, делит координатную плоскость. Чтобы определить, какая из двух полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на разделяющей прямой подставить в неравенство:

Если неравенство справедливо, то областью решений является полуплоскость, содержащая эту точку;

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

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

Линией уровня называется прямая с 1 x 1 +с 2 x 2 = l , где l = const, на которой целевая функция задачи принимает постоянное значение. Все линии уровня параллельны между собой.

Градиент целевой функции grad Z (X ) задает вектор нормали C = (c 1 , c 2) линий уровня. Целевая функция на линиях уровня возрастает, если линии уровня перемещать в направлении их нормали, и убывает – в противоположном направлении.

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

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

Алгоритм графического метода решения ЗЛП с двумя неизвестными:

Построить ОДР.

Построить вектор нормали C = (c 1 , c 2) и линию уровня с 1 x 1 +с 2 x 2 = 0, проходящую через начало координат и перпендикулярную вектору С .

Передвигать линию уровня до опорной прямой в направлении вектора С в задаче на max, или в противоположном направлении – в задаче на min.

Если при перемещении линии уровня в направлении экстремума ОДР уходит в бесконечность, то ЗЛП не имеет решения ввиду неограниченности целевой функции.

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

Вычислить значение целевой функции в точке экстремума.

Симплекс-метод решения ЗЛП

Симплекс-метод основывается на следующих положениях:

ОДР задачи линейного программирования является выпуклым множеством с конечным числом угловых точек;

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

Базисным (опорным) решением ЗЛП называется такое допустимое решение X 0 =( x 10 , x 20 , ..., x m 0 , 0,…0), для которого векторы условий (столбцы коэффициентов при неизвестных в системе ограничений) линейно независимы.

Ненулевые координаты x 10 , x 20 , ..., x m 0 решения X 0 называются базисными переменными, оставшиеся координаты решения X 0 - свободными переменными. Число отличных от нуля координат опорного решения не может быть больше ранга r системы ограничений ЗЛП (числа линейно независимых уравнений в системе ограничений ЗЛП). Далее считаем, что система ограничений ЗЛП состоит из линейно независимых уравнений, т.е. r = m .

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

Найти начальное опорное решение;

Осуществить переход от одного опорного решения к другому;

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

Алгоритм выполнения Симплекс-метода ЗЛП

Алгоритм симплекс-метода осуществляет переход от одного опорного решения ЗЛП к другому в направлении экстремума целевой функции.

Пусть ЗЛП задана в каноническом виде (1.2) и выполнено условие

b i ≥ 0, i =1,2,…,m , (1.3)

соотношение (1.3) всегда можно выполнить, домножив соответствующее уравнение на «-1» в случае отрицательности b i . Также считаем, что система уравнений в ограничениях задачи (1.2) линейно независима и имеет ранг r = m . При этом вектор опорного решения имеет m ненулевых координат.

Пусть исходная задача (1.2), (1.3) приведена к виду, где базисные переменные x 1 , x 2 , ..., x m выражены через свободные переменные x m + 1 , x m + 2 , ..., x n

(1.4)

На основе этих соотношений построим таблицу 1

Таблица 1.

Таблица 1 называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменениями содержания этой таблицы.

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

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

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

3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

4. Если имеется несколько одинаковых по величине симплекс - отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симлекс - таблицы.

5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс - таблица преобразуется следующим образом (таблица 2):

Таблица 2

6. Элемент таблицы 2, соответствующий разрешающему элементу таблицы 1, равен обратной величине разрешающего элемента.

7. Элементы строки таблицы 2, соответствующие элементам разрешающей строки таблицы 1, получаются путем деления соответствующих элементов таблицы 1 на разрешающий элемент.

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

9. Остальные элементы вычисляются по правилу прямоугольника : мысленно вычерчиваем прямоугольник в таблице 1, одна вершина которого совпадает с разрешающим элементом (Рэ), а другая – с элементом, который мы ищем; обозначим элемент в новой таблице 2 через (Нэ), а элемент, стоящий на этом же месте в старой таблице 1 – через (Сэ). Остальные две вершины А и В дополняют фигуру до прямоугольника. Тогда искомый элемент Нэ из таблицы 2 равен Нэ = Сэ – А*В/Рэ.

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

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

Метод искусственного базиса решения ЗЛП

Алгоритм симплекс-метода применим, если выделено какое-либо опорное решение ЗЛП, т. е, исходная ЗЛП (1.2) приведена к виду (1.4). Метод искусственного базиса предлагает процедуру построения такого опорного решения.

Метод искусственного базисаоснован на введении искусственных базисных переменных y 1 , y 2 ,…, y m , с помощью которых система ограничений ЗЛП (2.2)

(1.5)

может быть преобразована к виду

(1.6)

Системы (1.5) и (1.6) будут эквивалентны в том случае, если все y i будут равны нулю. Как и раньше мы считаем, что все b i ≥ 0. Для того чтобы у i были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные базисные переменные y i перешли в свободные переменные. Такой переход можно сделать алгоритмом симплекс метода относительно дополнительной целевой функции

F (y ) = y 1 + y 2 + ... + y m = d 0 – (d 1 x 1 + d 2 x 2 +…+d n x n). (2.7)

Исходная симплекс таблица для данного метода имеет вид

Сначала симплекс таблица преобразуется относительно целевой функции F (y ) до получения опорного решения. Опорное решение найдено, когда выполнен следующий критерий: F (y ) = 0 и все искусственные переменные у i переведены в свободные переменные. Затем из симплекс таблицы вычеркивается строка для F (y ) и столбцы для у i и решают задачу для исходной целевой функции Z (x ) до получения оптимального решения.

Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных x1, x2, …, xn, удовлетворяющие m условиям - равенствам

и обращающие в максимум линейную функцию этих переменных

Для простоты предположим, что все условия (1) линейно независимы (r=m), и будем вести рассуждения в этом предположении.

Назовём допустимым решением ОЗЛП всякую совокупность неотрицательных значений x1, x2, …, xn, удовлетворяющую условиям (1).Оптимальным назовём то из допустимых решений, которое обращает в максимум функцию (2). Требуется найти оптимальное решение.

Всегда ли эта задача имеет решение? Нет, не всегда.

ЗЛП неразрешима (не имеет оптимального решения):

Из-за несовместности системы ограничений. Т.е. система не имеет ни одного решения, как показано на рисунке 1.

Рисунок 1 - Несовместность системы ограничений

Из-за неограниченности целевой функции на множестве решений. Другими словами при решении ЗЛП на max значение целевой функции стремится к бесконечности, а в случае ЗЛП на min - к минус бесконечности, как показано на рисунке 2.

Рисунок 2 - Неограниченность целевой функции на множестве решений

ЗЛП разрешима:

Множество решений состоит из одной точки. Она же и является оптимальной, как показано на рисунке 3.

Рисунок 3 - Множество решений состоит из одной точки

Единственное оптимальное решение ЗЛП. Прямая, соответствующая целевой функции в предельном положений пересекается с множеством решений в одной точке, как показано на рисунке 4.

Рисунок 4 - Единственное оптимальное решение

Оптимальное решение ЗЛП не единственно. Вектор N перпендикулярен к одной из сторон множества решений. В этом случае оптимальной является любая точка на отрезке АВ, как показано на рисунке 5.

Рисунок 5 - Оптимальное решение не единственно

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

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

Использование этого метода в дипломном проекте для решения задачи ЛП обусловлено следующими факторами:

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

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

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

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

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

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

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

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

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

Таким образом, применение симплексного метода распадается на два этапа:

Нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности;

Нахождение оптимального решения в случае совместности системы ограничений.

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

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

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

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

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

Условие оптимальности плана при решении задачи на максимум: среди коэффициентов целевой функции нет отрицательных элементов .

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

В силу этих определений задача ЛП может быть сформулирована следующим образом: среди всех точек выпуклой области, являющейся решением системы ограничений, выбрать такую, координаты которой минимизируют (максимизируют) линейную функцию F = с 1 x + с 2 y .
Заметим, что переменные x , y в ЗЛП принимают, как правило, неотрицательные значения (x ≥ 0, y ≥ 0), поэтому область расположена в I четверти координатной плоскости.

Рассмотрим линейную функцию F = с 1 x + с 2 y и зафиксируем какое-нибудь ее значение F . Пусть, к примеру, F = 0, т.е. с 1 x + с 2 y = 0. Графиком этого уравнения будет прямая, проходящая через начало координат (0;0) (рис.).
Рисунок
При изменении этого фиксированного значения F = d , прямая с 1 x + с 2 y = d будет смещаться параллельно и «зачертит» всю плоскость. Пусть D – многоугольник – область решения системы ограничений. При изменении d прямая с 1 x + с 2 y = d , при некотором значении d = d 1 достигнет многоугольника D , назовем эту точку А «точкой входа», и затем, пройдя многоугольник, при некотором значении d = d 2 будем иметь с ним последнюю общую точку В , назовем В «точкой выхода».
Очевидно, что своего наименьшего и наибольшего значения целевая функция F =с 1 x + с 2 y достигнет в точках «входа» А и «выхода» В .
Учитывая, что оптимальное значение на множестве допустимых решений целевая функция принимает в вершинах области D , можно предложить следующий план решения ЗЛП:

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

Заметим, что вектор (с 1 , с 2), перпендикулярный прямой, показывает направление роста целевой функции.

При графическом решении ЗЛП возможны два случая, которые требуют особого обсуждения.

Случай 1
Рисунок 6
При перемещении прямой с 1 x + с 2 y = d «вход» или «выход» (как на рисунке) произойдет по стороне многоугольника. Это случится, если в многоугольнике есть стороны, параллельные прямой с 1 х + с 2 у = d .
В этом случае точек «выхода» (« входа») бесчисленное множество, а именно – любая точка отрезка АВ . Это означает, что целевая функция принимает максимальное(минимальное) значение не в одной точке, а во всех точках, лежащих на соответствующей стороне многоугольника D .

Случай 2
Рассмотрим случай, когда область допустимых значений неограниченна.
В случае неограниченной области целевая функция может быть задана таким образом, что соответствующая ей прямая не имеет точки «выхода» (или «входа»). Тогда максимальное значение функции (минимальное) не достигается никогда – говорят, что функция не ограничена.
Рисунок
Необходимо найти максимальное значение целевой функции F = 4x + 6y → max , при системе ограничений
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
x + y = 18

x	12	9
y	6	9

0,5x + y = 12

x	12	18
y	6	3

x = 12 – параллельна оси OY ;
y = 9 – параллельна оси OX ;
x = 0 – ось OY ;
y = 0 – ось OX ;
x OY ;
y ≥ 0 – полуплоскость выше оси OX ;
y ≤ 9 – полуплоскость ниже y = 9;
x ≤ 12 – полуплоскость левее x = 12;
0,5x + y x + y = 12;
x + y x + y = 18.
Рисунок
Пересечением всех этих полуплоскостей является очевидно, пятиугольник ОАВСД , с вершинами в точках О (0; 0), А (0; 9), В (6; 9), С (12; 6), Д (12; 0). Этот пятиугольник и образует область допустимых решений задачи.

F = 4x + 6y → max.

x	3	0
y	–2	0

F = 0: 4x + 6y x + 6y С (12; 6). Именно в ней F = 4x + 6y
Значит, при x = 12, y = 6 функция F F = 4 ∙ 12 + 6 ∙ 6 = 84, равного 84. Точка с координатами (12; 6) удовлетворяет всем неравенствам системы ограничений, и в ней значение целевой функции оптимально F * = 84 (оптимальное значение будем обозначать «*»).
Задача решена. Итак, необходимо выпустить 12 изделий I вида и 6 изделий II вида, при этом прибыль составит 84 тыс. руб.

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

Пример №2 . Шахта разрабатывает два пласта. Выход штыба по первому пласту составляет а1 %; по второму - а2 %. Максимальная производительность очистного забоя по первому пласту составляет В1 тыс.тонн в год, по второму пласту - В2 тыс.тонн в год. По технологии работ добыча со второго пласта не может превышать добычу с первого пласта. Выход штыба по шахте не должен превышать С1 тыс.тонн в год. Общая нагрузка по двум пластам за год должна быть не меньше С2 тыс.тонн в год. Составить математическую модель и построить множество допустимых значений нагрузки по первому и второму пластам за год.

Пример №3 . Магазин продает 2 вида безалкогольных напитков: Колу и лимонад. Доход от одной банки колы составляет 5 центов, тогда как доход от одной банки лимонада 7 центов. В среднем магазин за день продает не более 500 банок обоих напитков. Несмотря на то, что колу выпускает известная торговая марка, покупатели предпочитают лимонад, поскольку он значительно дешевле. Подсчитано, что объем продаж колы и лимонада должны соотноситься не менее 2:1 кроме того, известно что магазин продает не менее 100 банок колы в день. Сколько банок каждого напитка должен иметь магазин в начале рабочего дня для максимизации дохода?

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

Пример №5 . Туристской фирме требуется не более а трехтонных автобусов и не более в пятитонных автобусов. Отпускная цена автобусов первой марки 20000 у.е., второй марки 40000 у.е. Туристская фирма может выделить для приобретения автобусов не более с у.е. Сколько следует приобрести автобусов каждой марки в отдельности, чтобы их общая (суммарная) грузоподъёмность была максимальной. Решить задачу графическим методом.

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

Пример №7 . Решить графическим методом задачу линейного программирования, подвергнув систему ограничений задачи преобразованиям Жордано-Гаусса. Система ограничений задачи имеет вид:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
Методические рекомендации . Преобразования Жордано-Гаусса можно выполнить с помощью этого сервиса или через исследование СЛАУ .

Пример №8 . Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов. На изготовление единицы изделия А требуется затратить сырья каждого вида а1, а2, а3 кг соответственно, а для единицы изделия В - в1, в2, в3 кг. Производство обеспечено сырьем каждого вида в количестве Р1, Р2, Р3 кг, соответственно. Стоимость единицы изделия А составляет С1 руб., а единицы изделия В - С2 руб. Требуется составить план производства изделий А и В, обеспечивающий максимальную стоимость готовой продукции.

Пример №2 . Необходимо найти максимальное значение целевой функции F = 4x + 6y → max, при системе ограничений:

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

Затем заполняем коэффициенты при переменных и сами ограничения (рисунок 2).
Рисунок 2

Рисунок 3
x = 12 – параллельна оси OY ;
y = 9 – параллельна оси OX ;
x > = 0 – ось OY
y = 0 – ось OX ;
x ≥ 0 – полуплоскость правее оси OY ;
y ≥0 – полуплоскость выше оси OX ;
y ≤ 9 – полуплоскость ниже y = 9;
x ≤ 12 – полуплоскость левее x = 12;
0,5x + y ≤ 12 – полуплоскость ниже прямой 0,5x + y = 12;
x + y ≤ 18 – полуплоскость ниже прямой x + y = 18.

Пересечением всех этих полуплоскостей является пятиугольник ABCDE , с вершинами в точках A (0; 0), B (0;9), C (6; 9), D (12;6), E (12;0). Этот пятиугольник и образует область допустимых решений задачи.

Рассмотрим целевую функцию задачи F = 4x + 6y → max.

x	3	0
y	–2	0

Построим прямую, отвечающую значению функции F = 0: 4x + 6y = 0. Будем двигать эту прямую параллельным образом. Из всего семейства прямых 4x + 6y = const последней вершиной, через которую пройдет прямая при выходе за границу многоугольника, будет вершина С (12; 6). Именно в ней F = 4x + 6y достигнет своего максимального значения.

Значит, при x = 12, y = 6 функция F достигает своего максимального значения F = 4 ∙ 12 + 6 ∙ 6 = 84, равного 84. Точка с координатами (12;6) удовлетворяет всем неравенствам системы ограничений, и в ней значение целевой функции оптимально F * = 84.