Практическое применение симплекс-метода

Исходные данные:

Задание 1. Пусть план выпуска товаров A, B и C соответственно. Составим в принятых обозначениях математическую модель задачи. Административное ограничение: продукция вида B должна быть в плане.[pic 1]

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

[pic 2]

Совокупность ограничений на ресурсы может быть представлена в качестве приведенной ниже системы неравенств:

                                                     (1)[pic 3]

Кроме того, по смыслу задачи [pic 4]

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

Решим составленную ЗЛП графическим методом. Для этого из первого уравнения системы (1) выразим переменную  и подставим её значение в целевую функцию:[pic 5]

[pic 6]

[pic 7]

[pic 8]

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

[pic 9]

В целях удобства построения графической иллюстрации ОДР перепишем каждое неравенство, задающее ресурсное ограничение, в виде уравнения прямой в отрезках:

[pic 10]

В этой же форме представим и уравнение линии уровня [pic 11]

[pic 12]

[pic 13]

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

[pic 14]

Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая , перпендикулярная вектору-градиенту, называется линией уровня целевой функции. Подчеркнем, что в любой точке линии уровня целевая функция принимает одно и то же значение.[pic 15]

Важное свойство линии уровня линейной функции состоит в следующем: при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в другую сторону — только убывает.

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

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

Анализируя графическую иллюстрацию, замечаем, что линия уровня параллельна одной из прямых, задающих ограничение в ЗЛП, а именно прямой . Для доказательства этого утверждения воспользуемся теорией, известной из курса линейной алгебры: прямые параллельны, если коллинеарны векторы их градиентов. В свою очередь, векторы являются коллинеарными, если абсцисса первого вектора относится к абсциссе второго так же, как ордината первого — к ординате второго.[pic 16]

Вектор градиента  прямой  равен , а градиент целевой функции был найден ранее.[pic 17][pic 18][pic 19]

Таким образом,

[pic 20]

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

Из всего множества точек, которые максимизируют целевую функцию и удовлетворяют заданным условиям, согласно условию задачи необходимо выбрать только те, обе координаты которых принадлежат множеству . [pic 21]

Очевидно, что такие точки находятся на пересечении прямых  и , а также прямых  и .[pic 22][pic 23][pic 24][pic 25]