КАТЕГОРИИ: Архитектура-(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) |
Вершины многогранника называются угловыми точками
Как мы уже отмечали, графический метод, описанный в предыдущих примерах, приемлем в отношении задач с не более, чем двумя переменными. В большинстве же практических ситуаций число неизвестных может быть гораздо больше. Симплекс- метод- один из наиболее известных алгебраических подходов к решению задач линейного программирования с более, чем с двумя переменными. Отметим прежде всего Аналитическое решение транспортной задачи будет рассмотрено далее. Покажем решение этой задачи в EXCEL Требуется составить оптимальный план перевозок топлива от поставщиков к потребителям, чтобы а) вывезти все топливо б) удовлетворить весь спрос в) минимизировать суммарные затраты Построение математической модели: Положим хi j – количество груза, перевозимого от i-го исходного пункта к j-му пункту назначения. х11 + х12 + х13 =300 х21 + х22 + х23 =500 х11 + х21 =500→ ограничения х12 + х22 =200 х13 + х23 =100 хij ≥ 0 F = 7х11 + 9х12 + 8х13 + 3х21 + 4х22 + 6х23 → min § 3. Общая постановка задачи линейного программирования. Симплекс- метод
Задача линейного программирования в стандартной форме а11х1 + а12х2+……а1nхn ≤ в1 а21х1 + а22х2+……а2nхn ≤ в2 (1) …………………………… аm1х1 + аm2х2+…аmnхn ≤ вm xi ≥ 0, i = 1,n F = c1х1 + c2х2+……cnхn → max Матричная запись: Ах = в, F = c x → max Здесь А – матрица коэффициентов, х – столбец переменных, в- столбец правых частей, с - строка коэффициентов целевой функции. Основной принцип линейного программирования 1. Множество решений системы (1) из § 2 является выпуклым многогранником (напомним, что выпуклое множество вместе с любыми двумя точками содержит все точки соединяющего их отрезка). 3. Оптимальное решение (глобальный максимум) достигается хотя бы в одной угловой точке выпуклого многогранника, число которых конечно. Отсюда, принципиальный путь поиска оптимального решения: перебрать все угловые точки (их конечное число!) и среди них выбрать ту в которой целевая функция достигает максимума. Однако, как отмечается в [13], технические сложности подобной процедуры настолько существенны, что за исключением простейших случаев, этот метод практически бесполезен.
Поэтому, необходимо научиться отбрасывать заведомо “плохие” угловые точки и работать только с перспективными, не прибегая к грaфикам. Именно это и реализовал Данциг в разработанном им симплекс-методе. Суть метода – “направленный перебор”, когда вначале находят, какую нибудь угловую точку, а затем переходят к таким соседним угловым точкам, в которых значения целевой функции увеличиваются. Такой направленный перебор позволяет резко сократить число шагов (итераций). Ясно, что для реализации симплекс- метода необходимо математически: - выбрать начальное опорное решение (угловую точку) - проверить его на оптимальность - при необходимости перейти к лучшему - уметь распознавать ситуации отсутствия оптимального решения. Рассмотрим этапы “ручного” cимплекс - метода, когда необходимые преобразования осуществляются в таблицах стандартного вида. Пример: Фирма намеревается приступить к изготовлению трех видов изделий, используя три вида ресурсов. Исходные данные приведены в таблице стандартного вида. Табл.1
Дата добавления: 2015-06-04; Просмотров: 423; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |