Файл: В. А.МАТВЕЕВ.pdf

f (x ) =3x1 +5x 2 → max; 4x1 +5x 2 ≤ 20 3x1 +10x2 ≤30, 2x1 + x 2 ≤8, 10x1 +3x 2 ≤30, x1 ≥ 0; x2 ≥0.

Постоим область X на плоскости. Она расположена в первой четверти, т.к. x1 ≥ 0, x2 ≥ 0 , и ограничена прямыми m, n, p, q. Для удобства построения приведём уравнения этих прямых в отрезках.

Рис. 8.2.

68

OY. Соответствующий чертёж представлен на рис.8.2. Здесь m представлена прямой СF, n представлена прямой DE, p представлена прямой BG, и, наконец, q представлена прямой AH. Каждая прямая, как решение соответствующего неравенства, определяет полуплоскость. Для всех прямых CF, DE, BG, AH это будут полуплоскости, содержащие начало отсчёта O. Тогда область допустимых значений в задаче линейного программирования представляется пятиугольником OALKE.

Построим прямые уровня, которые касаются области X. Таких прямых две

l1 : 3x1 +5x2 = 0, l2 : 3x1 +5x2 =18.

Прямая l1 касается области X в точке О(0, 0), а прямая l2 - в точке

K(2, 2,4). Отметим, что точка K является пересечением прямых m, n и её координаты аналитически находятся как решение системы уравнений

4x1 +5x2 = 20,

3x1 +10x2 = 30.

Решение системы x1 = 2, x2 = 2,4, значит K(2, 2,4). Точки

касания K(2, 2,4) определяют решение задачи линейного программирования. Именно,

fmax = f (x*) =18 при x* = (2, 2.4).

Отметим, что в этой задаче в определении допустимого множества X не использовалась ограничение

2x1 + x2 ≤ 8.

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

69

Задачи для самостоятельного решения

Задача 8.1. Предприятие производит два вида продукции: П1, П2, которые потом поступают в оптовую продажу. В производстве продукции используются два вида сырья – А, В.

Максимальные запасы сырья составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П1, П2 представлен в таблице 8.1 Оптовые цены на продукцию П1 равны 3 руб., дляпродукцииП2 – 4 руб. Какоеколичествопродукциикаждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?

Таблица 8.1.

Ответ: x* = (4,2; 0,2), f* = 13,2.

Задача 8.2. Решить графически задачу линейного программирования, с ограничениями в форму равенств

f (x ) = 4x1 −2x 2 + x3 −x4 →max; 3x1 + 2x 2 −x3 +4x4 =3,

x1 −x 2 +4x3 −2x4 = 2, xi ≥ 0; i =1,...,4.

70

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

Вместе с задачей линейного программирования изучается тесно с ней связанная двойственная или сопряжённая задача. Исходную задачу часто называют прямой задачей линейного программирования. Использование теории двойственности позволяет удвоить полезные свойства задач математического программирования. Особенно важна эта теория для матричных игр. Матричная игра в определённом смысле эквивалентна паре из стандартной и двойственной ей задачи линейного программирования.

Пусть рассматривается стандартная прямая задача линейного программирования (8.1) – (8.3).

Двойственной ей является задача

Особенно удобно запоминать прямую и двойственную задачи линейного программирования, записанные в матричной форме. Задачу (8.1) – (8.3) можно представить

CmT X m → max,

Аналогично для задачи (9.1) – (9.3) верна запись

71

BnT Yn → min,

Здесь индексы у матриц – их размерности, т.е. число строк, затем число столбцов. Векторы X m , Yn представлены столбцовыми

матрицами. Знак T – транспонирование.

Для двойственной задачи условия (9.2) и (9.3) определяют область допустимых значений Y Rn. Целевая функция fd(y) задаёт прямые уровня в пространстве Rn. Значит, для двойственной задачи можно применять графический метод решения. Следует помнить, что, несмотря на формальное сходство задачи (8.1) – (8.3) и (9.1) – (9.3), их решения находятся, вообще говоря, в разных пространствах, т.е. x* X Rm и y* Y Rn.

По аналогичной схеме можно определить двойственную задачу для задачи линейного программирования (на минимизацию целевой функции) (9.1) – (9.3). В этом случае двойственная задача будет задача линейного программирования (на максимизацию целевой функции), представленная в (8.1) – (8.3). В этом смысле можно говорить о задаче (8.1) – (8.3) и о задаче (9.1) – (9.3), как о паре двойственных (сопряжённых) задач линейного программирования.

Прямая (8.1) – (8.3) и двойственная (9.1) – (9.3) задачи линейного программирования (пара двойственных задач) имеют общие свойства:

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

2°. Матрица коэффициентов системы ограничений получается одна из другой путём транспонирования;

3°. Неравенства в системах ограничений имеют противоположный смысл;

4°. Свободные члены системы ограничений одной задачи становятся коэффициентами целевой функции и наоборот.

72