Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Общая постановка задачи линейного программированияСодержание книги Поиск на нашем сайте
В зависимости от вида целевой функции и системы ограничений выбираются различные методы нахождения оптимального плана. Рассмотрим математические модели изучаемых процессов, представленных в виде совокупности линейных соотношений. В этом случае оптимальное решение будет находиться методами линейного программирования. Термин “линейное программирование” впервые появился в 1951г. в работах американских ученых Дж. Данцига и Т. Кумпанса, а первые работы по линейному программированию были выполнены в конце 30-х годов в Ленинградском государственном университете Л. В. Канторовичем. Употребление слова “программирование” связано с тем, что при решении задач находят такой набор переменных, который является программой (планом) при выполнении поставленной задачи. Математическая задача линейного программирования в канонической форме формулируется следующим образом: Найти такие неотрицательные значения х1 , х2 , х3 ,..., хn, которые обеспечивают оптимальное (минимальное или максимальное) значение линейной функции (целевой функции) F= +с и удовлетворяют системе ограничений (2.2) Коэффициенты , с- известные постоянные, характеризующие условия задачи (параметры условия). Система уравнения (2.2) должна быть неопределенной, так как только в этом случае возможен выбор решения из множества возможных. Задача линейного программирования может не иметь решений в следующих случаях: 1) если система ограничений несовместна, в том числе, если только не выполняется условие неотрицательности переменных xi; 2) система ограничений совместна, есть допустимые решения, но среди них нет оптимального решения. От системы ограничений, заданной в виде неравенств, при необходимости всегда можно перейти к канонической системе ограничений, добавив или отняв, дополнительные неотрицательные переменные. Эти переменные имеют вполне определенный экономический смысл. Так, если в ограничениях задачи отражается расход и наличие производственных ресурсов, то дополнительные переменные в оптимальном плане будут характеризовать объем неиспользованных ресурсов. Пример. Приведите к каноническому виду систему ограничений (2.1) из задачи о производстве столов и стульев. Введем неотрицательные переменные х4 , х5 , х6. Перепишем систему неравенств в виде: Так как левая часть первого неравенства меньше правой, то, добавив к ней положительную переменную х 4, можем вместо неравенства записать уравнение: 2 х 1 +0,5 х 2+ х 4 = 80. Переменная х 4 играет роль неизрасходованных часов рабочего времени. Аналогично, так как левая часть второго неравенства больше правой, то, отняв он нее положительную переменную х5, можем вместо неравенства записать уравнение: х 2 – 4 х 1– х 5 = 0. Переменная х5 показывает, на сколько количество проданных стульев больше учетверенного количества столов и т.д. Система (2.1) в каноническом виде имеет вид: Графический метод решения задачи линейного программирования Если математическая модель задачи линейного программирования имеет два параметра управления, и система ограничений представляет собой систему неравенств, то задача может быть решена графическим методом. Графический метод основан на геометрической интерпретации области решений системы ограничений и выборе из нее точки, в которой целевая функция принимает оптимальное значение. Как говорилось ранее, решением системы неравенств с двумя переменными является выпуклая область – пересечение полуплоскостей, представляющих собой решение каждого неравенства. Эту область называют областью допустимых решений (ОДР) или многоугольником решений. Каждое значение целевой функции F 0 = c 1 x 1+ c 2 x 2 задает на плоскости прямую, называемую опорной. Все эти прямые параллельны между собой и перпендикулярны вектору, называемому градиентом функции и имеющему координаты: grad F = (c 1; c 2). Особенностью задачи линейного программирования является то, что с перемещением любой опорной прямой параллельно в одну сторону значение целевой функции либо только растет, либо только убывает. Градиент показывает направление, в котором значение целевой функции будет возрастать. Поэтому, перемещая опорную прямую до «выхода» из ОДР в направлении градиента, будем получать все большие значения целевой функции на каждой из прямых. Наибольшее же будет достигаться в точке «выхода», соответствующей обычно одному из углов многоугольника. Это рассуждение иллюстрирует теорему линейного программирования:
|
||||
Последнее изменение этой страницы: 2016-08-01; просмотров: 278; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.97.9.171 (0.006 с.) |