Лекции по математическому программированию

Оглавление
n1.doc (8 стр.)
Скачать
1   2   3   4   5   6   7   8

Формы записи задач линейного программирования


Симметричной (стандартной) формой записи ЗЛП называется задача максимизации целевой функции (2.1) при ограничениях вида (2.2) и (2.5) или задача минимизации целевой функции (2.1) при ограничениях вида (2.4) и (2.5), т.е.

;

,



или ;

,

,

где – заданные действительные числа.

Канонической формой записи ЗЛП называется задача минимизации или максимизации целевой функции (2.1) при ограничениях вида (2.3) и (2.5), т.е.


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

  1. Переход от задачи на минимум к задаче на максимум осуществляется умножением целевой функции на «–1». Действительно, если функция достигает минимума при значениях , то функция достигает при тех же значениях переменных максимума.

  1. Переход от неравенства вида  к неравенствам вида  (и наоборот) также осуществляется умножением исходного неравенства на –1.

  1. Переход от неравенства к равенству осуществляется введением дополнительной неотрицательной переменной . К примеру, если первое ограничение имеет вид , то, вводя неотрицательную переменную , получим , если второе ограничение имеет вид , то, вводя неотрицательную переменную , получим

  2. При переходе от равенств к неравенствам можно руководствоваться следующим: если дано А=B, то это можно формально записать в виде двух неравенств А  В, А  В;

  3. Введение условий неотрицательности переменных. Пусть на переменную это условие не было наложено, тогда вместо этой переменной можно ввести две неотрицательные переменные и и представить , где . Это всегда возможно.

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

Пример 4

Пусть математическая модель задачи имеет следующий вид

;



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

Тогда ОЗЛП будет иметь вид

;



или (раскрыв скобки):

;



В симметричной (стандартной) форме записи задача будет иметь вид

;



Здесь ограничение (2.6) умножено на –1, а ограничение (2.7) заменено двумя ограничениями:



откуда, домножив второе ограничение на –1, получим ограничение (2.9) вида .

Таким образом, из ограничения (2.7) получены ограничения (2.8) и (2.9).

В канонической форме записи ЗЛП будет иметь вид

;



Пример 5

Экономико-математическую модель задачи, составленную в примере 2, представим в канонической форме записи:

;



Введенные дополнительные переменные и имеют экономический смысл, связанный с содержанием задачи. Здесь , – время простоя оборудования А1 и А2 соответственно.

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


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

Пример 6

Решим графически задачу ЛП, экономико-математическая модель которой составлена в примере 3.

;

(2.10)

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



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

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


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



Откуда . Это и есть оптимальный план задачи. Подставив значение и в целевую функцию Z, получаем

.

Таким образом, для того чтобы получить максимальную прибыль в размере 56 ден. ед., необходимо запланировать выпуск 8 ед. продукции вида П1 и 4 ед. продукции П2.

Портфель ученика
© lib.rushkolnik.ru
При копировании укажите ссылку.
обратиться к администрации