Полная версия

Главная arrow Логистика arrow Логистика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Графический метод решения задач линейного программирования

Если число переменных в задаче линейного программирования равно двум, а ограничениями является система неравенств, то задачу можно решить графическим методом.

Пример 5.7. Задача на отыскание оптимального числа ездок

С регионального склада А продукция доставляется двум потребителям и (рис. 5.14).

Схема маршрута

Рис. 5.14. Схема маршрута

Время на одну ездку (оборот) автомобиля на маршруте равно 1,5 ч на маршруте ч. Время на маршруте – ч.

Требуется организовать работу автомобилей так, чтобы потери времени в пределах их работы на маршруте были бы минимальными или равнялись бы нулю.

Ограничения.

  • 1. Превышение времени в наряде (7 ч) не допускается.
  • 2. Число ездок может быть только целым.

Критерий оптимальности. Сведение потерь времени к нулю или минимуму.

Решение.

Вариант 1. Принимаем раздельный вариант обслуживания потребителей и .

Тогда автомобиль, работающий на маршруте , за время работы сделает 4 ездки:

Принимаем число ездок равным 4, так как согласно условию задачи число ездок может быть только целым.

Потери времени при таком варианте организации работ

При работе только на маршруте АБ2 число ездок автомобиля будет равно

Потери времени составят

Очевидно, раздельная работа автомобилей на маршрутах не даст оптимального решения, так как имеет значительные потери времени.

Поэтому надо искать другой вариант.

Вариант 2. Автотранспорт обслуживает потребителей Б1 и Б2 таким образом, чтобы автомобиль часть ездок выполнял на маршруте АБ1, а другую часть – на маршруте АБ2.

Варианты такой организации работы автомобилей приведены в табл. 5.22.

Таблица 5.22

Определение оптимальной работы автомобилей при обслуживании потребителей Б1 и Б2

Номер варианта

Число ездок

Затраты времени при работе

Потери времени, ч

Процент потерь времени

на первом маршруте

на втором маршрут

на первом маршруте

на втором маршруте

Всего

1

4

0

6,0

0

6,0

1,0

14,3

2

3

2

4,5

2,4

6,9

0,1

1,43

3

2

3

3,0

3,6

6,6

0,4

5,71

4

1

4

1,5

4,8

6,3

0,7

10,0

5

0

5

0

6,0

6,0

1,0

14,3

Из данных табл. 5.22 следует, что оптимальным вариантом работы автомобилей будет второй, при котором автомобиль выполнит две ездки на маршруте АБ1 и три – на маршруте АБ2. Потери времени при такой организации работ минимальные.

Получение оптимального варианта определения числа ездок описанным выше методом является громоздким и требует значительных затрат времени. Удобнее для этого пользоваться графическим методом, который более прост и менее трудоемкий.

Математически условие задачи может быть сформулировано следующим образом:

1,5x+ 1,2y = 7,0,

где x – число ездок на первом маршруте; у – число ездок на втором маршруте.

Это выражение представляет собой уравнение прямой, пересекающей оси координат. Для нахождения этой прямой необходимо найти максимальное значение х и у. Максимальное значение х будет в том случае, когда у = 0, т.е. Xmax = 7 : 1,5 = 4,6, а Ymax – когда х = 0, т.е. Ymax =7:1,2 = 5,8.

Откладываем максимальные значения Хmax и Ymax на графике на соответствующих осях координат и соединяем полученные точки прямой линией A1A2 (рис. 5.15).

График определения оптимального числа ездок

Рис. 5.15. График определения оптимального числа ездок

Искомый оптимальный вариант может находиться только в зоне, ограниченной прямой линией и осями координат. Необходимо найти такую точку, в которой линия графика наиболее подходит к ординатам целых величин или пересекает их на графике. Точки пересечения ординат целых величии в пространстве, ограниченном линией и осями координат, обозначены буквами С1; С2; С3; С4; С5. На графике линия проходит через точку С2, координаты которой: х = 3; у = 2. Таким образом, оптимальный вариант организации работы автомобилей будет следующий: автомобиль должен выполнить две ездки на маршруте АБ1 и три ездки на маршруте АБ2. Полученные на графике данные полностью совпадают с табличными.

Отсюда следует, что для решения подобных типов задач нужно построить график по максимальным значениям Х и Y и на нем отыскать оптимальное число ездок. В таком случае таблицей пользоваться нет необходимости.

Пример 5.8. Задача на лучшее использование имеющегося подвижного состава

Из двух терминалов вывозится однотипный груз на тягачах с прицепами. Установлено, что для вывозки груза из первого терминала один тягач должен иметь два прицепа, а второй – четыре прицепа. Количество груза, перевозимого одним тягачом из первого терминала, составляет 12 т, а со второго – 20 т. Автохозяйство имеет 8 тягачей и 24 прицепа. Требуется расставить тягачи и прицены таким образом, чтобы обеспечить их максимальную производительность.

Сведения о транспортных средствах приведены в табл. 5.23.

Таблица 5.23

Сведения о транспортных средствах

Наименование транспортных средств

Соотношение транспортных средств

Наличие транспортных средств

Терминал 1

Терминал 2

Тягачи

1

1

8

Прицепы

2

4

24

Условие задачи можно записать следующими уравнениями: х + у = 8 – уравнение для тягачей;

2x + 4у = 24 – уравнение для прицепов,

где х – число тягачей на терминале 1; у – число тягачей на терминале 2.

Из условия задачи записываем уравнение по производительности. Исследуем первые два уравнения на максимум и определяем значения х и у.

Из первого уравнения эти значения будут равны: х = 8, у = 8 (тягачи), а из второго х = 12; у = 6,0 (прицепы).

Построим график в соответствии с результатами X и Y (рис. 5.16).

График определения оптимальной загрузки автомобилей и тягачей

Рис. 5.16. График определения оптимальной загрузки автомобилей и тягачей

На рис. 5.16 показана точка пересечения двух прямых, построенных в соответствии со значениями X и Y. Если из этой точки опустить перпендикуляры на оси X и Y, то значение ординат этой точки составит x = 4, у = 4.

Полученные величины показывают, что на первый терминал следует направлять четыре тягача, а на второй – четыре.

Так как один тягач на первом терминале требует два прицепа, а на втором четыре, то прицепы следует расставить следующим образом:

  • • на первом терминале 2x =2•4 = 8;
  • • на втором терминале 4у = 4 • 4 = 16.

Максимальная производительность будет равна:

Проверим полученный результат методом последовательного отбора возможных вариантов расстановки тягачей и прицелов по терминалам. На графике (см. рис. 5.16) обозначим координаты точкам K1, К2 и т. д. до К9.

Для точки К1 координаты будут равны: х = 8; у = 0.

Или:

Из приведенных расчетов следует, что максимальная производительность соответствует точке К5 с координатами: x= 4 и у = 4 и равна 128 т. Это и будет оптимальный вариант расстановки тягачей и прицепов по терминалам согласно условиям нашей задачи.

 
<<   СОДЕРЖАНИЕ   >>