Студопедия

КАТЕГОРИИ:


Архитектура-(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

Ресурсы Запасы (ресурсов) Расходные коэффициенты
1 2 3
труд   6 5 4
сырье   3 2 4
оборудование   5 3 3
Прибыль, у.е.   9 10 16



Поделиться с друзьями:


Дата добавления: 2015-06-04; Просмотров: 423; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.