Общая задача линейного программирования

↑

▷ Содержание

⇐ ПредыдущаяСтр 4 из 4

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

Дана система т линейных уравнений и неравенств с п переменными

(20)

и линейная функция

(21)

Необходимо найти такое решение системы , где

(22)

при котором линейная функция F (21) принимает оптимальное (т.е. максимальное или минимальное) значение.

Система (1.20) называется системой ограничений, а функция F — линейной функцией, линейной формой, целевой функцией или функцией цели.

Более кратко общую задачу линейного программирования можно представить в виде:

при ограничениях:

Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение системы ограничений (20), удовлетворяющее условию (22), при котором линейная функция (21) принимает оптимальное (максимальное или минимальное) значение.

Термины "решение" и "план" — синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй — о содержательной стороне (экономической интерпретации).

При условии, что все переменные неотрицательны , система ограничений (20) состоит лишь из одних неравенств, - такая задача линейного программирования называется стандартной; если система ограничений состоит из одних уравнений, то заданa называется канонической [1]. Так, в приведенных выше примерах задач линейного программирования задачи 1 и 2 — стандартные, задача 4 — каноническая, а задача 3 — общая.

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

Теорема 1.1. Всякому решению () неравенства

(23)

соответствует определенное решение () уравнения

(24)

в котором

(25)

и, наоборот, каждомурешению () уравнения (24) инеравенства (25)соответствует определенное решение ( неравенства (23).

Используя эту теорему (которую принимаем без доказательства), представим в качестве примера стандартную задачу (4)— (6) в каноническом виде. С этой целью в каждое из т неравенств системы ограничений (4) введем дополнительные неотрицательные переменные и система ограничений (4) примет вид:

(26)

Таким образом, стандартная задача (4)—(6) в канонической форме: найти такое решение , удовлетворяющее системе (26) и условию (5), при котором функция (6) принимает максимальное значение.

Замечание. В рассматриваемой задаче все неравенства вида "£", поэтому дополнительные неотрицательные переменные вводились со знаком "+". В случае неравенства вида "³", как, например, в задаче(10) — (12), соответствующие дополнительные переменные следовало бы ввести со знаком "—".

Задача о потребностях сырья

Для производства двух видов изделий А и В предприятие (участок работы) использует три вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в табл. 4. В ней же указаны прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое необходимо предприятию.

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

Таблица 4

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

.

Общая прибыль от реализации изделий вида А и изделий вида В составит . Это и будет целевая функция.

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

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

;

Эти прямые изображены на рис. 4.1. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой — нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае — другая полуплоскость. Найдем, например, полуплоскость, определяемую неравенством

Для этого, построив прямую , возьмем какую-нибудь точку, принадлежащую одной из двух полученных полуплоскостей, например, точку O(0,0). Координаты этой точки удовлетворяют неравенству

Значит, полуплоскость, которой принадлежит точка O(0,0), определяется неравенством

Это и показано стрелками на рис. 6.1.

Пересечение полученных полуплоскостей и определяет многоугольник решений данной задачи.

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

Чтобы найти указанную точку, построим вектор С = (30, 40) н прямую , где h — некоторая постоянная, такая, что прямая имеет общие точки с многоугольником решений. Положим, например, h = 480 и построим прямую (см. рис.1).

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

Далее, полагая h равным некоторому числу больше 480, мы будем получать различные параллельные прямые. Если они имеют общие точки с многоугольником решений, то эти точки определяют планы произ­водства изделий А и В, при которых прибыль от их реализации превзойдет 480 руб. Перемещая построенную прямую

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

Найдем координаты точки В как точки пересечения прямых

.

Решив эту систему уравнений, получим , . Следовательно, если предприятие изготовит 12 изделий вида А и 18 изделий вида В, то оно получит максимальную прибыль, равную

.

Варианты заданий

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Вариант 11

Вариант 12

Вариант 13

Вариант 14

Вариант 15

Вариант 16

Вариант 17

Вариант 18

Вариант 19

Вариант 20

Вариант 21

Вариант 22

Вариант 23

Вариант 24

[1] В ряде работ по математическому программированию стандартную задачу называют симметричной, а каноническую – основной.

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры