Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Общая задача линейного программирования ⇐ ПредыдущаяСтр 4 из 4
Рассмотренные выше примеры задач линейного программирования позволяют сформулировать общую задачу линейного программирования. Дана система т линейных уравнений и неравенств с п переменными
и линейная функция
Необходимо найти такое решение системы
при котором линейная функция F (21) принимает оптимальное (т.е. максимальное или минимальное) значение. Система (1.20) называется системой ограничений, а функция F — линейной функцией, линейной формой, целевой функцией или функцией цели. Более кратко общую задачу линейного программирования можно представить в виде:
при ограничениях:
Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение Термины "решение" и "план" — синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй — о содержательной стороне (экономической интерпретации). При условии, что все переменные неотрицательны Любая задача линейного программирования может быть сведена к канонической, стандартной или общей задаче. Рассмотрим вначале вспомогательную теорему. Теорема 1.1. Всякому решению (
соответствует определенное решение (
в котором
и, наоборот, каждомурешению ( Используя эту теорему (которую принимаем без доказательства), представим в качестве примера стандартную задачу (4)— (6) в каноническом виде. С этой целью в каждое из т неравенств системы ограничений (4) введем дополнительные неотрицательные переменные
Таким образом, стандартная задача (4)—(6) в канонической форме: найти такое решение
Замечание. В рассматриваемой задаче все неравенства вида "£", поэтому дополнительные неотрицательные переменные вводились со знаком "+". В случае неравенства вида "³", как, например, в задаче(10) — (12), соответствующие дополнительные переменные следовало бы ввести со знаком "—". Задача о потребностях сырья Для производства двух видов изделий А и В предприятие (участок работы) использует три вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в табл. 4. В ней же указаны прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое необходимо предприятию. Принимаем, что сбыт обеспечен и что изделия А и В могут производиться в любых соотношениях. Перед менеджером по выпуску товара поставлена задача составить такой план выпуска, при котором прибыль предприятия (участка работы) от реализации всех изделий была бы максимальной.
Таблица 4
Решение. Предположим, что предприятие изготовит
Общая прибыль от реализации Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значение. Найдем решение сформулированной задачи, используя ее геометрическую интерпретацию. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств и найдем соответствующие прямые:
Эти прямые изображены на рис. 4.1. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой — нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае — другая полуплоскость. Найдем, например, полуплоскость, определяемую неравенством
Для этого, построив прямую
Значит, полуплоскость, которой принадлежит точка O(0,0), определяется неравенством
Это и показано стрелками на рис. 6.1. Пересечение полученных полуплоскостей и определяет многоугольник решений данной задачи. Как видно из рис. 6.1, многоугольником решений является пятиугольник OABCD. Координаты любой точки, принадлежащей этому пятиугольнику, удовлетворяют данной системе неравенств и условию неотрицательности переменных. Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую пятиугольнику OABCD, в которой функция F принимает максимальное значение. Чтобы найти указанную точку, построим вектор С = (30, 40) н прямую
Если теперь взять какую-нибудь точку, принадлежащую построенной прямой и многоугольнику решений, то ее координаты определяют такой план производства изделий А и В, при котором прибыль от их реализации равна 480 руб. Далее, полагая h равным некоторому числу больше 480, мы будем получать различные параллельные прямые. Если они имеют общие точки с многоугольником решений, то эти точки определяют планы производства изделий А и В, при которых прибыль от их реализации превзойдет 480 руб. Перемещая построенную прямую
в направлении вектора С, видим, что последней общей точкой ее с многоугольником решений задачи служит точка В. Координаты этой точки и определяют план выпуска изделий А и В, при котором прибыль от их реализации будет максимальной. Найдем координаты точки В как точки пересечения прямых
Решив эту систему уравнений, получим
Варианты заданий
Вариант 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] В ряде работ по математическому программированию стандартную задачу называют симметричной, а каноническую – основной.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Последнее изменение этой страницы: 2017-02-06; просмотров: 331; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.220.160.216 (0.057 с.) |
(20)
(21)
, где
(22)
, система ограничений (20) состоит лишь из одних неравенств, - такая задача линейного программирования называется стандартной; если система ограничений состоит из одних уравнений, то заданa называется канонической [1]. Так, в приведенных выше примерах задач линейного программирования задачи 1 и 2 — стандартные, задача 4 — каноническая, а задача 3 — общая.
) неравенства
(23)
) уравнения
(24)
(25)
и система ограничений (4) примет вид:
(26)
, удовлетворяющее системе (26) и условию (5), при котором функция (6) принимает максимальное значение.
изделий вида А и 
изделий вида В. Поскольку производство продукции ограничено имеющимся в распоряжении предприятия сырьем каждого вида и количество изготавливаемых изделий не может быть отрицательным, должны выполняться следующие неравенства:
.
. Это и будет целевая функция.
; 
, возьмем какую-нибудь точку, принадлежащую одной из двух полученных полуплоскостей, например, точку O(0,0). Координаты этой точки удовлетворяют неравенству
, где h — некоторая постоянная, такая, что прямая 
(см. рис.1).
.
, 
. Следовательно, если предприятие изготовит 12 изделий вида А и 18 изделий вида В, то оно получит максимальную прибыль, равную
.
