- •1. Построение экономико-математической модели задачи линейного программирования (на конкретном примере).
- •Этапы моделирования
- •Основные типы моделей:
- •§2. Основы линейного программирования.
- •Примеры задач линейного программирования
- •3. Виды заданий системы ограничений экономико-математической модели. Переход от стандартного к каноническому заданию
- •4. Геометрический смысл решения неравенств и системы неравенств
- •5. План решения задачи линейного программирования геометрическим методом
- •Строим вектор - нормальный вектор, он указывает направление возрастания функции.
- •Мысленно перемещаем прямую в направлении вектора , тогда:
- •§9. Критерии оптимальности симплекс - метода.
- •12. Метод искусственного базиса
- •7) Далее задачу решают на max или min.
- •13. Транспортная задача. Общая подстановка. Открытая и закрытая модели
- •14. Построение первоначального плана транспортной задачи методом северо-западного угла
- •15. Построение первоначального плана транспортной задачи методом минимального эллипса
- •16. Улучшение первоначального плана транспортной задачи методом потенциалов. Основные этапы. Цикл, потенциалы
- •Предварительный шаг решения:
- •17. Составление системы потенциалов для заполненных клеток при решении транспортной задачи
- •Общий шаг решения:
- •18. Проверка на потенциальность незаполненных клеток при решении транспортной задачи.
12. Метод искусственного базиса
Если при решении задачи симплекс - методом нельзя сразу получить допустимое базисное решение (т.е. если знак неравенства или ), то применяют метод искусственного базиса. Он заключается в следующем:
1) вводят искусственные переменные прибавляя их к левым частям уравнений.
2) эти искусственные переменные следует ввести в целевую функцию Z в виде: , где М - произвольно большое число.
3) вводят новую целевую функцию . Эту функцию принято записывать в виде 2 строк:
4) искусственные переменные выводят из базиса и делают их свободными, обратно в базис их не возвращают, поэтому соответствующие столбцы симплекс - таблицы вычеркивают и дальше не рассматривают.
5) чтобы определить разрешающий столбец, находят в строке наибольший положительный элемент. Разрешающую строку определяют по минимальным отношениям. Все элементы таблицы заполняются обычным образом.
6) после перевода всех искусственных переменных в свободные, получаем первое базисное решение. Все элементы в строке М обращаются в ноль и ее отбрасывают.
7) Далее задачу решают на max или min.
Пример:
Перейдем к каноническому виду, вводя вспомогательные переменные:
Введем искусственные переменные:
13. Транспортная задача. Общая подстановка. Открытая и закрытая модели
Под термином транспортная задача понимается широкий круг задач, необязательно транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся y производителей по n потребителям.
При планировании наиболее рациональных перевозок грузов выделяют следующие виды транспортных задач:
Транспортная задача по критерию стоимости перевозок.
Транспортная задача по критерию времени.
Транспортная задача на определение кратчайших расстояний по заданной сети дорог.
Транспортная задача ставится следующим образом:
Найти объемы перевозок для каждой пары поставщик - потребитель так, чтобы:
Мощности всех поставщиков были реализованы.
Удовлетворить все потребности потребителей.
Суммарные затраты на перевозку были минимальными.
Задача:
В 3-х пунктах отправления , сосредоточен груз . Этот груз следует доставить в каждый из четырех пунктов в количестве . Стоимость перевозок единицы груза из i-го пункта отправления в j-й пункт назначения задана для всех комбинаций. Определить такой план перевозок, чтобы их стоимость была минимальной.
|
|
|
|
|
Запасы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потребности |
|
|
|
|
|
- стоимость перевозок единицы продукции из i-го пункта отправления в j-й пункт назначения.
- количество единиц груза, отправленного из i-го пункта в j-й.
Если , т.e. если объем суммарных запасов груза равен суммарному объему потребностей в этих грузах, то транспортная задача является закрытой. Если же эти суммы не равны, то задача называется открытой и в этом случае следует вводить ложный пункт отправления или назначения с нулевыми тарифами.
Система ограничений в транспортной задаче имеет вид:
Данную задачу можно решить симплекс методом, но особенности модели таковы:
Система ограничений - есть система уравнений.
Коэффициенты при переменных в системе ограничений равны 1 или 0.
Каждая переменная входит в систему ограничений дважды.
Это позволяет разработать специальные методы решения транспортной задачи:
если m - число пунктов отправления, a n- число пунктов назначения, то в общем случае уравнений будет . Одно уравнение системы ограничений транспортной задачи является следствием остальных и его можно исключить. В общем случае система ограничений содержит уравнений с числом переменных. Эта система всегда разрешима.
Определение 1. План перевозок, обращающий в минимум суммарные транспортные издержки, называется оптимальным планом или оптимальным решением.
Решение транспортной задачи разбивается на 2 этапа:
Определение опорного решения.
Построение последовательных итераций, т.е. приближение к оптимальному решению.