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

4.РЕШЕНИЕ ЗАДАЧИ ГРАФИЧЕСКИМ МЕТОДОМ

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

Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно.
Поэтому в нашем случае вполне обосновано применение графического метода, так как имеем две переменные.
Построим в декартовой системе координат многоугольник решений, или допустимых планов, который является пересечением полуплоскостей - решений каждого из неравенств системы ограничений.
(1): . Сначала строится разделяющая прямая . Для этого находим две точки, через которые она проходит:
0 1 0
Подставим точку (0;0) в неравенство (1): - верно, поэтому стрелки указывают на полуплоскость к нулю.
(2): . Разделяющая прямая , найдём точки:

0 14 7 0
Подставим точку (0;0) в неравенство (2): - верно, поэтому стрелки указывают на полуплоскость к нулю.
(3): . Разделяющая прямая , прямая, которая параллельна прямой .
Находим многоугольник, в котором пересекаются, накладываются друг на друга все построенные полуплоскости. Многоугольник допустимых решений заштриховывается.


Рисунок 1 - Графический метод решения задачи

Построим градиент и линию уровня функции цели: . Градиент всегда изображается с началом в т.(0;0). Любая линия уровня перпендикулярна градиенту. Удобно построить линию уровня , также проходящую через начало координат: .
Перемещаем мысленно или с помощью линейки так, чтобы найти угловые точки многоугольника допустимых планов, координаты которых доставляют максимальное значение функции цели. В данной задаче линия уровня перемещается в направлении за градиентом, поэтому её значения будут увеличиваться от линии к линии. Следовательно, в тоске А будет наибольшее значение. Найдём координаты точки А, как точки пересечения разделяющих прямых:



Следовательно, координаты т.А(0;7).
.
Таким образом, получили максимальное значение целевой функции в точке А(0;7), которое равно 49.




5.РЕШЕНИЕ ЗАДАЧИ СИМПЛЕКС МЕТОДОМ

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



Дальнейшее решение представим в виде симплекс – таблиц.
Таблица 1

Так как у нас задача на нахождение максимального значения целевой функции, тогда в индексной строке необходимо найти наибольшую по модулю отрицательную оценку. Но в нашей задаче, она единственная - столбец с переменной . Выделяем этот столбец. Далее необходимо найти оценочные отношения, среди которых выбираем наименьшее. У нас оно также единственно – это 7 – вторая строка. Выделяем её. Элементы второй строки делим на 4. Из базиса выводим переменную , при этом в базис вводим переменную . Все невыделенные элементы пересчитываем. Например, для элемента первой строки первого столбца: . И так все элементы.
В результате перейдём к таблице 2.
Таблица 2

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

ВЫВОД

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


Кузнецов А.В., Сакович В.А., Холод Н.И. Математическое программирование. Минск, Высш. шк., 2007.

Мезенцев Ю.А. Экономико–математические методы. Новосибирск: Изд. – во НГТУ, 2008.

Таха Х.А. Введение в исследование операций. М.: Издательский дом "Вильямс", 2005.

Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем. М.: Финансы и статистика, 2006.

Грешилов А.А. Прикладные задачи математического программирования. М.: Логос, 2006.













12