8.2. Графоаналитический метод
Чтобы понять основные свойства линейных моделей и из чего складывается процесс получения решения задач линейного программирования, рассмотрим геометрическую интерпретацию линейного программирования, получившего название графоаналитического метода. Необходимо учитывать, что графоаналитический метод может быть использован только в том случае, если задача содержит два, максимум три неизвестных. В последнем случае приходится пользоваться пространственной моделью. Несмотря на простоту решения задач этим методом, его применение при разработке технологических процессов весьма ограничено.
Сущность графоаналитического метода рассмотрим на решении следующей задачи:
максимизировать функцию 10Х1+13Х2 (8.11)
при наличии ограничений
Решение задачи может быть найдено графически, как показано на рис. 8.2. Ограничения (8.12) и (8.13) на рис. 8.2 изображены прямыми линиями как уравнения, полученные заменой неравенств на равенства. Площадь под каждой из двух прямых эквивалентна математической формулировке, имеющей направленный смысл «меньше, чем» (<). Так как X1 и X2 не могут принимать отрицательных значений, область допустимых значений переменных ограничивается осями координат. Таким образом, многоугольник ОABC содержит в себе область значений Хх и Х2, удовлетворяющих всем имеющимся ограничениям. Множество точек, принадлежащих области, ограниченной линиями ОАВС (вместе с граничными точками), называется множеством решений. Это множество является выпуклым, т. е. любой отрезок, соединяющий две произвольным образом выбранные точки данного множества, лежит внутри или проходит вдоль границы ОABC.
Вершины О, А, В, С носят название экстремальных точек. Они не могут принадлежать внутренней части ни одного из отрезков, соединяющих две различные точки рассматриваемого множества. Параллельные прямые на рис. 8.2 являются графическим изображением различных значений целевой функции, которую можно записать как |
Изменяя степень достижения цели Z0, получаем на рис. 8.2 семейство параллельных изолированных прямых, уравнение которых
Из уравнения (8.16) следует, что чем выше степень достижения цели, тем выше располагается соответствующая изоцелевая прямая. Оптимальное решение определяется экстремальной точкой В, для которой
Если в формуле для целевой функции (8.11) изменить коэффициенты при переменных (при этом угол наклона параллельных линий по отношению к оси абсцисс также будет другим), то в результате точка, задающая оптимальное решение, может перемещаться. Если при наличии ограничений (8.12), (8.13), (8.14) целевая функция будет иметь вид
то в этом случае все точки, лежащие на отрезке АВ, будут являться оптимальными (рис. 8.3). Решение X1 = 0,95, Х2=1,8 будет оптимальным. Однако оптимальным будет и решение X1 = 0, Х2 = 2 . Оптимальное значение целевой функции будет равно 28,0.
Проведенный анализ показывает, что решение задачи дается координатами вершин выпуклой области допустимых решений. Если решение задается координатами двух вершин, то оно дается координатами всего отрезка, соединяющего эти вершины.
Изменение целевой оптимизирующей функции в определенных пределах не приводит к изменению решения задачи. В случае, когда в задаче имеются три переменные величины и три уравнения ограничений, например, максимизировать |
при наличии ограничений:
то приходится пользоваться пространственной моделью.
Когда ограничения являются уравнениями, то каждое из них можно считать уравнением плоскости, лежащей в трехмерном пространстве, и точка, общая этим трем плоскостям, есть единственная точка, представляющая собой допустимое решение (рис. 8.4, а). Если ограничения являются неравенствами, то область оптимальных решений образуют точки некоторого выпуклого многогранника, расположенного в первом октанте. Придавая переменной Z0, формула (8.18), различные значения, получим семейство параллельных изоцелевых плоскостей (см. рис. 8.4, а), причем большим значениям Z0 будут соответствовать плоскости, расположенные дальше от начала координат. Решение задачи дается координатами одной из вершин выпуклого многогранника допустимых решений.
Если вместо трех уравнений ограничений имеется лишь два, допустим, уравнения (8.19) и (8.20), то в этом случае областью допустимых решений окажется линия пересечения плоскостей, являющихся изображениями уравнений ограничений (рис. 8.4, б). При одном уравнении ограничений областью допустимых решений будет являться треугольник, образованный линиями пересечения плоскости, изображающей это уравнение, с плоскостями координат (рис. 8.4, в).
В случае, когда необходимо получить не максимум, а минимум функции, то многоугольник будет вогнутым.
Особенности решения задач графоаналитическим методом рассмотрим на следующих примерах
Задача 8.3. От поставщика А груз перевозится автомобилями КаMA3-5320 двум потребителям B1 и В2 на расстояние 15 и 25 км соответственно. При перевозке груза потребителю B1 на одну ездку затрачивается 1,23 ч, а потребителю В2 - 1,8 ч. Продолжительность работы автомобилей на линии -8 ч. Работая на маршруте В1, водитель делает 6 ездок, затрачивая на это 7,38 ч рабочего времени. На маршруте В2 водитель делает 4 ездки и затрачивает 7,2 ч рабочего времени. Требуется организовать работу так, чтобы максимально использовать рабочее время водителей.
Математическая модель запишется в следующем виде:
максимизировать
при наличии ограничения
где: X1 - число ездок на маршруте В1;
Х2 - число ездок на маршруте В2.
Решение может быть найдено графически, как показано на рис. 8.5. При X1 = 0, Х2 = 4,4. При Х2 = 0 , X1 = 6,5 . Соединив полученные точки А и В, получим область допустимых решений X, и Х2. Левые части уравнений целевой функции (8.22) и ограничения (8.23) совпадают. Это значит, что все точки, лежащие на линии 1,23Х1+1,8Х2=8. |
будут оптимальными. Точки Q, С2 и так далее, заключенные между прямой АВ и осями координат, имеющие координатами целые числа, изображают все возможные варианты работы автомобиля. Точки, которые ближе расположены к прямой или лежат на ней, дают наилучшие - оптимальные решения.
В рассматриваемом примере точки C1 с координатами X1=5 и Х2 = 1 и С4 с координатами X1 = 2, Х2 =3 ближе всех расположены к линии АВ. В первом случае продолжительность работы водителя на линии составит
1,23-5 + 1,8*1 = 7,95 ч,
а во втором
1,23-2 + 1,8*3 = 7,86 ч.
Задача 8.4. Определить потребное число поддонов для перевозки грузов пакетами, упакованными в потребительскую тару двух размеров - А и В. Количество грузов в таре типа А составляет 600 единиц и типа В - 300 единиц. Количество тары, загружаемой на поддон различными способами, приведено в табл. 8.1.
Таблица 8.1
Тип тары | Способы размещения тары на поддоне | |||
1 | 2 | 3 | 4 | |
А | 3 | 2 | 1 | 0 |
В | 1 | 3 | 6 | 8 |
Математическая модель задачи будет сформулирована следующим образом:
минимизировать Х{ + Х2 + Х3 + Х4 = Z0, (8.24)
при наличии ограничений
где: Xi - число поддонов, загруженных по i-способу размещения тары.
Для решения задачи начертим прямоугольную систему координат АОВ (рис. 8.6) и каждому возможному способу размещения тары на поддоне поставим точку, координаты которой соответствуют числу соответствующей тары, размещаемой на поддоне. Буквой С с индексом обозначим номер способа размещения тары на поддоне. Множество всевозможных планов размещения тары на поддоне изображается совокупностью точек выпуклого многоугольника С1 С2 С4 С3. Например, точки на отрезке С1 С2будут указывать
своими координатами количество тары типа А и типа В, приходящейся на один поддон в различных способах размещения их, сочетающих собой размещения по способу С1 и С2 (рис. 8.6). Из всех решений нас интересует выполнение условия комплектности, т. е. отношение числа тары А к числу тары В.В соответствии с заданием это соотношение равно 2 (600:300). Если из начала системы координат провести луч, координаты которого А= 2, В = 1, то оптимальным будет план размещения тары на поддоне, которому соответствует точка, одновременно принадлежащая многоугольнику и лучу, и имеющая наибольшие координаты, т. е. соответствующая плану наибольшего использования площади поддонов.Такой точкой будет Р, лежащая на отрезке С1 С3. Это указывает на то, что оптимальный план размещения тары на поддонах представляет собой комбинацию размещения тары по способу C1 и С3. |
Обозначим через δ долю поддонов, загружаемых по способу C1, а остальную часть (l-δ) - по способу С3, долю одного и другого способа размещения поддонов найдем из условия комплектности
Минимальное число поддонов Z0 определится из уравнения
откуда Z0 =212. Таким образом, по способу C1 будет загружено 194 поддона и по способу С3 - 18.
- Глава 1
- Транспорт в экономической системе россии
- Место и роль автомобильного
- Транспорта в транспортной системе страны
- Основные периоды развития автомобильного транспорта
- 1.3. Некоторые результаты экономических реформ на автомобильном транспорте россии
- 1.4. Особенности транспортной сферы материального производства
- 1.5. Транспорт и рынок
- Глава 2 производственно-транспортные системы
- 2.1. Системный подход к организации грузовых перевозок
- 2.2. Цель транспортной сферы материального производства
- 2.3. Классификация систем
- 2.4. Границы системы
- 2.5. Уровень организованности перевозочной системы
- Глава 2 28
- Глава 3 грузы, измерители перевозочного процесса и тарифы
- 3.1. Грузы Классификация грузов
- Транспортная маркировка грузов
- Объемно-массовые характеристики грузов и использование грузоподъемности транспортных средств
- Общие принципы обеспечения транспортабельности грузов
- 3.2. Измерители процесса перевозки
- Объем перевозок
- Грузопоток
- Партионность перевозок
- Транспортная продукция
- Транспортный путь
- 3.3. Тарифы
- Глава 4 автомобильные транспортные средства и показатели их использования
- 4.1. Классификация автомобилей
- 4.2. Показатели использования автомобильного транспорта Парк подвижного состава
- Время работы подвижного состава
- Пробег подвижного состава и его использование
- Использование грузоподъемности подвижного состава
- Средняя длина ездки с грузом и среднее расстояние перевозки
- Производительность грузового автомобиля
- Провозные возможности подвижного состава
- Анализ производительности грузового автомобиля
- Себестоимость перевозки груза
- Анализ себестоимости транспортирования
- Выбор типа грузового подвижного состава
- Глава 5 технология грузовых автомобильных перевозок
- 5.1. Виды грузовых автомобильных
- Перевозок и их классификация
- 5.2. Основные принципы технологии перевозочного процесса
- 5.3. Прямые и смешанные автомобильные сообщения
- 5.4. Цикл транспортного процесса
- Этап подготовки груза к перевозке
- Этап подачи подвижного состава под погрузку
- Этап погрузки (разгрузки)
- Этап транспортирования груза
- Продолжительность цикла транспортного процесса
- 5.5. Прогрессивные технологические процессы перевозки грузов Контейнерные перевозки
- Перевозки грузов укрупненными местами – пакетами
- Комбинированные перевозки грузов
- Перевозки грузов автомобилями-самосвалами и самопогрузчиками
- 5.6. Логистика - технология будущего
- Глава 6 организация автомобильных перевозок
- 6.1. Основы организации перевозочного процесса
- Что такое организация?
- Принципиальная схема организации перевозки груза
- Основные функции перевозочного процесса
- Перевозочный комплекс
- Организационная структура автотранспортного предприятия
- 6.2. Синергетика: сущность, основные идеи и понятия
- 6.3. Подготовка процесса перевозки грузов
- Экономическая подготовка
- Техническая подготовка
- Организационная подготовка
- 6.4. Служба организации перевозок Функции службы организации перевозок
- Организация выпуска автомобилей на линию
- Контроль за выполнением суточного плана перевозок
- 6.5. Передовые методы организации перевозок Централизованные перевозки грузов
- Бригадная форма организации труда
- Интермодальные перевозки
- Некоммерческие перевозки
- Транспортно-экспедиционное обслуживание
- 6.6. Особенности организации перевозок грузов Особенности организации перевозок грузов добывающих отраслей
- Особенности организации перевозок строительных грузов
- Особенности организации перевозок сельскохозяйственных грузов
- Особенности организации перевозок промышленных грузов
- Особенности перевозки скоропортящихся грузов
- Особенности перевозки хлебобулочных изделий
- Особенности организации перевозок опасных грузов
- 6.7. Организация междугородных и международных перевозок Междугородные перевозки
- Глава 2 28
- Международные перевозки
- Глава 7 управление автомобильными перевозками
- 7.1. Определение управления
- 7.2. Современное состояние управления автомобильными перевозками
- 7.3. Функции управления
- 7.4. Стадии процесса управления
- 7.5. Диспетчерское управление перевозками Основные правила построения структуры управления
- Системы контроля и регулирования движения подвижного состава
- 7.6. Руководитель коллектива
- 7.7. Стимулы и наказания
- Глава 8
- 8.2. Графоаналитический метод
- 8.3. Метод потенциалов
- 8.4. Маршрутизация перевозок
- 8.5. Применение теории массового обслуживания в организации перевозок
- 8.6. Решение задач в сетевой форме
- 8.7. Симплексный метод общие положения
- Вычислительная процедура симплексного метода
- Определение исходного базиса
- Анализ модели на чувствительность
- Двойственность задач линейного программирования
- 8.8. Сетевое планирование в управлении
- Глава 2 28
- 8.9. Ситуационные игры
- Глава 9 измерение эффективности перевозочного процесса
- 9.1. Показатели эффективности
- 9.2. Факторы, учитываемые при оценке эффективности перевозок
- 9.3. Оценка эффективности перевозок
- 9.4. Анализ эффективности перевозок
- Библиографический список