КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Метод линейного программирования
Лекция 10. Методы математического программирования составляют раздел Линейным программированием называется раздел математики, в Q(x) = р 1 х 1+ р 2 х 2+... + рnхn (10.1)(5.5)
(10.2) (5.6)
где коэффициенты аij, bj, рj, (i =1, j =1,n) — действительные числа. Можно предполагать, что b 1≥0, b 2≥0 ,..., bn ≥0.
АХ= b; х ≥0; Qmin(х) ≥ рrх, где х =(х 1, х 2,..., x n)T Rn, А — матрица размера тn; р =(p 1, p 2, …, p n)T; b =(b1, b2, …, bm)T ≥ 0 где Rn — область возможных решений. Если имеется максимум целевой функции G(x) = р 1 х 1+ р2 х 2+... + рnрn, то это равнозначно отысканию минимума функции Q(x) = -G(x) = (-pi) x i + (-р2) x2 +... + (-рn) xn. Если в дополнительных условиях имеется неравенство, например, а i1 х 1+ а 2 х 2+... + аin х n ≤ b i то введением вспомогательного переменного множителя у можно перейти к уравнению а i1 х 1+ а 2 х 2+... + аin х n= b. Для нового переменного также справедливо неравенство (10.3)(5.7) Любая ЗЛП может быть приведена квиду (5.7). Двойственной Точка х = (х1, х2, …, хn)T, удовлетворяющая всем условиям, Множество всех оптимальных решений ЗЛП выпукло. Если допустимая область образована n неравенствами х j≥ 0, и т Если допустимая область ограничена и непустая, то она является Если допустимая область пуста, то ЗЛП неразрешима. Если допустимая область не ограничена, то ЗЛП либо может быть Канонический вид ЗЛП. Основным алгоритмом решения ЗЛП Например, каноническая форма 2х1 – Зх2 + х4 = 5, к которой 2х1 – Зх2 ≤ 5, при x4 ≥ 0. 2х1 – Зх2 + х4 = 5 Формулировка задачи представлена в виде если каждое из уравнений содержит одну переменную х jтакую, что Например, 3 х 1+ х 2+ 2 х 3 = 5; - х 1 + 3 х 3+ х 5 = 9;
х 1, х 3 — свободные переменные. В целевую функцию должны входить только свободные переменные. Если целевая функция имеет вид Q(x) = х1 + 13х2 +2x3 +17х4 + 3х5, то вычитанием из этого выражения первого уравнения, умножен- Q(x) = -52х1 + 35х3 + 109. Тогда окончательно ЗЛП в каноническом виде запишется: (10.4)(5.8) При всех хi = 0 Qmin= 109. Задача (10.4) (5.8) решается симплекс-методом. Для этого находим Так как ограничения в виде уравнений представляют собой плоскости в n-мерном пространстве, а также условия хi ≥ 0, то решение Рассмотрим пример, когда ЗЛП решается при двух переменных х1 и х2, поэтому может быть интерпретирована геометрическими построениями на плоскости. Пример. Имеется два вида ресурсов в количестве 8 и 24, из которых изготавливается два вида изделий. На единицу изделия первого Ставится задача, в каких количествах следует изготавливать Р е ш е н и е. Построим математическую модель задачи. Обозначим Учитывая ограничения на используемые материалы, сформулируем ЗЛП: максимизировать доход Fmax = 4 x 1 + 5 х 2
при условиях 2х, +х ≤ 8; 4 x 1 + 6 х 2 ≤ 24; x1 ≥ 0, х2 ≥ 0.
Каждое из неравенств системы определяет полуплоскость, их пересечение (заштрихованная часть) — это ресурсно-обеспеченная Для определения точки максимума ОДР возьмем какую-либо
F= 4 х 1 + 5 х 2, или 20 = 4 х 1 + 5 х 2.
2х1+х2 = 8 и
Вершинами ОДР в этой задаче являются точки О, А, К и В. Допустимой симплекс-таблице соответствует точка минимума, Пример. Задана целевая функция
F= -3 х 1 + х 2 +3 х 3 => min,
при ограничениях
2 х 1 + х 2 + х 3 + х 4 < 5;
-х 1 + 3 х 2 - х 3 < 4;
х, + 2х,+ х,+х < 8; x 1=0, x 2=0, x 3> 0
F= -3 х 1 + х 2 +3 х 3 => min. Ограничения: 2 х 1 + х 2 + х 3 + х 4 = 5;
-х 1 + 3 х 2 - х 3+ x 5 = 4;
х 1+ 2х2+ х3+х6 =8; x i=0, где х 1, х 2, х 3 — свободные переменные, а х 4, х 5, х 6 — базисные. Таблица (10.1)5.1 j*
i*
Так как в последней строке имеется отрицательный член, от Для выбора разрешающей строки берутся коэффициенты при хi
и . Для разрешающей строки выбираем наименьшее из получен- Таблица (10.2) 5.2 j*
i*
Для перехода к новой симплекс-таблице необходимо поменять места- Таблица 5.3 j*
i*
Остальные элементы таблицы вычисляем по формуле, значение Тогда для элемента а 52 Аналогично для рj и для b i Так же для F и т.д. Заполняем табл. 5.3. F min = — 7. Базисное решение: х 1 = 2,5; х 2 = 0; х 3 = 0; x 4=0; х 5 = 6,5; х 6 = 5,5. Проверка: F min = -3х1 + х 2+ 3х3 = -3 х 5/2 = -7,5.
назад
Дата добавления: 2015-04-24; Просмотров: 1510; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |