Решение
Дадим математическую постановку задачи.
Пусть продукции А производится x1 единиц, а продукции В - x2 единиц.
Стоимость всех изделий А составит 4х1 рублей, изделий В -6х2 рублей, суммарная: Z = 4x1 + 6x2 .
Требуется затратить 16x1 кг – количество сырья первого вида, идущего на изготовление всех изделий вида A; 4x2 – количество сырья первого вида, идущего на изготовление всех изделий вида B.
Получим ограничение по сырью первого вида: 16x1+4x2£784.
Аналогично определяем ограничение по сырью 2 вида: 8x1+7x2£552 и ограничение по сырью 3 вида: 5x1+9x2£567.
Количество выпускаемых изделий не может быть отрицательным. Следовательно, условие неотрицательного решения: x1³0, x2³0.
Получим задачу линейного программирования.
Требуется максимизировать функцию доходов (стоимости готовой продукции):
Z = 4x1 + 6x2 
max.
При наличии системы ограничений:
Решим задачу графически.
Так как переменные x1, x2 неотрицательны, то допустимые решения лежат в первом координатном углу.
Для построения области допустимых решений (ОДР) для каждого ограничения строят прямую, соответствующую равенству.
Первому условию в системе ограничений соответствует равенство:
16x1+ 4x2=784.
Построим эту прямую по точкам:
| x1 | ||
| x2 |
Прямая разбивает плоскость на две полуплоскости. Для определения искомой полуплоскости берут произвольную точку, не принадлежащую прямой, и проверяют, удовлетворяют ли ее координаты рассматриваемому неравенству. Если удовлетворяют, то все точки полуплоскости, которому принадлежит взятая точка, есть решение данного неравенства. В противном случае рассматриваемому неравенству удовлетворяют все точки другой полуплоскости, которой не принадлежит выбранная точка.
Если прямая не проходит через начало координат, то в качестве произвольно выбранной точки удобно брать начало координат, то есть точку О (0, 0).
Для нашего случая возьмем начало координат О (0; 0) и, поставив ее координаты в неравенство, получим:
16×0 + 4×0 < 784.
Имеем верное равенство. Следовательно, полуплоскость, которой принадлежит точка О(0, 0) и есть геометрическое решение неравенства. Решением первого неравенства системы является полуплоскость, лежащая ниже прямой 16x1 + 4x2 = 784. Таким же образом найдем решения каждого неравенства системы (см. рис. 5).
Решением системы неравенств будет пересечение всех полуплоскостей. Это пересечение есть выпуклое множество, называемое областью допустимых решений(ОДР).
В общем случае, ОДР может быть замкнутым выпуклым многоугольником, незамкнутым или пустым.
Для нахождения оптимального решения, то есть такого, при котором целевая функция принимает свое максимальное (минимальное) значение, дадим целевой функции Z произвольное численное значение, то есть положим Z=С (стоимость постоянная).
Множество точек 4x1+6x2=С определяет прямую, называемой линией уровня функции цели Z(x1,x2). При различных значениях С получаем семейство линий уровня - параллельных прямых с одним и тем же нормальным вектором 
. С увеличением Z они будут передвигаться в одну сторону, с уменьшением - в противоположную.
Интерес представляют линии уровня, имеющие общие точки с ОДР. При С = 0 общая стоимость равна нулю. Так как коэффициенты функции цели Z положительны, ее значение увеличивается при движении прямых от линии уровня, проходящей через точку O (0,0), в направлении вектора 
. Крайняя прямая из семейства параллельных прямых имеет с многоугольником решений общую точку А.
Координатами нормального вектора являются коэффициенты при текущих координатах в уравнении прямой Z, то есть 
(4;6). Поэтому для определения оптимального плана на графике достаточно построить нормальный вектор (4;6), провести прямую, перпендикулярную через крайнюю точку ОДР (рис.5), то есть точку, в которой прямая Z касается ОДР.
Рис.5. Геометрическое решение задачи
линейного программирования
Из рисунка видно, что точкой, в которой прямая Z касается ОДР является точкой А. Находим ее координаты, решая систему уравнений:
Получим x1= 27, x2= 48.
Точка A (27;48).
Максимальный доход составляет Zmax = 4 
27 + 6 48 = 396 руб.
Ответ. Для получения максимальной стоимости изделий 396 рублей необходимо изготовить изделий А 27 единиц, изделий В 48 единиц.
При геометрическом решении задач линейного программирования следует знать следующие свойства:
1. Если оптимальное решение существует, то оно лежит на границе ОДР.
2. Если решение единственное, то оно достигается в одной из вершин ОДР.
3. Если решений множество, то они достигаются на одной из сторон выпуклого многоугольника ОДР.
4. Решение, лежащее в одной из вершин ОДР, является опорным решением, а сама вершина - опорной точкой.
5. Для того, чтобы найти опорное решение достаточно перебрать все вершины ОДР (опорные точки) и выбрать ту, где целевая функция достигает максимума.
2.3. Симплексный метод
Алгебраический метод решения (симплекс-метод) разработан американским математиком Д. Данцигом и опубликован в 1951 г. В его основе лежит использование элементарных преобразований матрицы ограничений канонической задачи линейного программирования (метод Жордана-Гаусса).
Переход от общей задачи линейного программирования (2.1), (2.2), (2.4) к задаче в канонической форме (2.1), (2.3), (2.4), осуществляется с помощью введения m неотрицательных дополнительных переменных 
. Эти переменные добавляются к каждому из неравенств системы (2.2), обращая их в равенства, и входят в функцию цели с коэффициентами, равными нулю. В этом случае задача линейного программирования в канонической форме формулируется так: требуется найти совокупность неотрицательных чисел
, 
, (2.5),
которые удовлетворяют системе линейных уравнений:
(2.6)
и дают экстремум функции цели: 
max(min)(2.7)
Правомерность перехода от общей задачи к задаче в канонической форме основывается на теореме: неотрицательное решение системы неравенств (2.2) является решением системы уравнений (2.6). Справедливо и обратное утверждение.
Рассмотрим задачу линейного программирования на нахождение минимума целевой функции.
Справедливы теоремы.
Теорема 1. Если для некоторого фиксированного индекса j выполняется условие Zj - Cj > 0, то можно построить хотя бы один опорный план, для которого значение целевой функции Z будет меньше первоначального, т. е. Z < Z0.
Теорема 2. Если для некоторого опорного плана`x выполняется соотношение Zj - Cj£ 0, то план`x является оптимальным.
Сформулируем алгоритм симплексного метода.
По условию задачи составляется экономико-математическая модель задачи в общем виде:
Z(x1,...xn) = c1x1+...+cnxn max
xj 
0, ( j = 1,….n) .
Переходят от задачи на максимум к задаче на минимум Z. Для этого целевую функцию умножают на (-1).
-Z(x1,...xn) = -c1x1 -...-cnxn min.
От общей задачи линейного программирования с помощью дополнительных переменных переходят к задаче в канонической форме.
xj 0, ( j = 1,….n+m) .
Запишем систему ограничений в векторной форме:
или 
.
Составляется первая симплексная таблица:
Таблица 2.1
| Базис | C | b | -C1 | -C2 | … | -Cn | Cn+1=0 | … | Cn+m=0 |
| a1 | a2 | … | an | an+1 | … | an+m | |||
| an+1 | Cn+1=0 | b1 | a11 | a12 | … | a1n | … | ||
| an+2 | Cn+2=0 | b2 | a21 | a22 | … | a2n | … | ||
| … | … | … | … | … | … | … | … | … | … |
| an+m | Cn+m=0 | bm | am1 | am2 | … | amn | … | ||
| Zj-Cj | Z0 | C1 | C2 | … | Cn | … |
Столбец “Базис” – столбец векторов, входящих в базис.
Столбец “С” – столбец коэффициентов, стоящих в целевой функции при векторах базиса.
Строка “Zj-Cj” - называется индексной строкой.
Столбец “b” - столбец ограничений по ресурсам, входящих в базис.
Столбцы a1 … am, …, am+1… an - это коэффициенты, стоящие при неизвестных в системе ограничений.
Заполним индексную строку “Zj-Cj”. Для столбца “b” это значение равно сумме попарных произведений элементов столбца “C” на элементы столбца “b”, т. е.
.
Решение находится в столбце “b”:
`x=(b1, b2 ,…, bm, 0,…, 0); Z = Z0..
Две верхние строки таблицы содержат коэффициенты функции цели и n+m векторов системы ограничений.
4. Просматриваются числа Zj-Сj индексной строки.
Если в задаче требуется найти минимум функции цели, то базисное решение будет минимальным, при условии, что все числа индексной строки неположительные, то есть отрицательные или нули. Если же среди чисел индексной строки есть хотя бы одно положительное, то план не оптимальный и его следует улучшить.
5. Предположим, что базисное решение не оптимальное. Из всех положительных чисел индексной строки выбирается наибольшее по абсолютной величине, то есть 
. Индекс j, которому соответствует такое число индексной строки, укажет вектор, который следует ввести в базис. Пусть им будет 
. Столбец, соответствующий этому вектору, будет направляющим (ведущим).
6. Определяем направляющую (ведущую) строку. Определяется число 
. С этой целью компоненты базисного решения делятся на положительные компоненты ведущего вектора-столбца. Индекс i, которому соответствует 
, укажет вектор, который следует исключить из базиса. Пусть им будет вектор 
. Строка, соответствующая этому вектору, будет направляющей (ведущей). Элемент xij, стоящий на пересечении ведущего столбца и ведущей строки, называется разрешающим элементом.
7. После выбора разрешающего элемента симплексная таблица преобразовывается по формулам прямоугольника:
, (2.8)
aij - разрешающий элемент матрицы, aij 
0.
После преобразования получим: 
все остальные элементы в столбце с разрешающим элементом преобразуются в нули. Тем самым, в соответствующей системе линейных уравнений неизвестное xj останется с коэффициентом, равным единице в i - м уравнении, а во всех остальных будет исключено.
Элементы, участвующие в процедуре преобразования, являются вершинами прямоугольника, причем в одной из них обязательно находится разрешающий элемент aij