Файл: Золотарь, И. А. Экономико-математические методы в дорожном строительстве.pdf

с запасами: 8000 м3; 9000 м3 и 10 000 м3. Для погрузки мате­

риалов используются экскаваторы, имеющие производительность 250 м3/смену в карьерах 1 и 2 и 500 м3/смену в карьере 3.

Эти карьеры обеспечивают каменными материалами также ряд других строящихся объектов. На погрузку материалов для рас­ сматриваемого участка выделен для экскаваторов общий лимит 60 машино-смен с правом использовать его по усмотрению строи­ телей.

Транспортные затраты на перевозку материалов характеризу­

135; из карьера 3— 170 автомобиле-смен.

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

Необходимо минимизировать линейную форму:

71

Так как ограничения (V.22) — (V.25) содержат лишь две пере­ менные у\ и у2, то они могут быть изображены на плоскости. На

рис. 17 показана геометрическая интерпретация линейных нера­ венств. Если, к примеру, равенство 2 х + у = Ъ изображается на гра­ фике прямой LL', то неравенство 2х + у < 5 — областью, располо­ женной ниже и левее прямой LL'. Если переменные должны удов-

летворять еще одному неравенству, например х + г /< 3, то точки, удовлетворяющие обоим указанным неравенствам, располагаются ниже и левее ломаной МК L'. Дополнительные ограничения в виде неравенств могут ограничить область допустимых решений со всех сторон. Так, принимая дополнительно условия х ^ О и у ^ 0, полу­ чим область допустимых решений, которая на рис. 17 показана штриховкой.

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

Нанесем на график условия (V.22) и (V.25), а также ограниче­ ния (V.23) и (V.24), каждое из которых занимает область между двумя параллельными прямыми (рис. 18). Такие две прямые для (V.23) будут иметь уравнения:

О = — 2т/], — 2,86г/2-j-9,72 или у2= — 0,702^ + 3,40;

—2 ^ - 2 , 8 6 0 2 + 9,72= 0,9 или у2= - 0 , 7 0 2 у г ^3,08.

72

Аналогично для ограничения (V.24) получим:

у2= —0,35#!+ 2,70;

У 2 = —0,35^ + 3,05.

Нанеся на график все наши ограничения, выраженные зависи­ мостями (V.22) — (V.25), получим область допустимых решений на­ шей задачи в виде линии ab. Решение с минимумом у2 соответству­

Таким образом, оптимальный план перевозок будет характери­ зоваться вывозкой из карьеров 1,2 и 3 следующих количеств мате­

чи, а линейная форма получает следующую минимальную вели­

мальному решению оказался бы очень длительным, не будь в симплекс-методе критерия, позволяющего исключить из рассмот­ рения некоторые вершины многогранника, заведомо не могущие дать оптимального решения. Этим достигается значительное сокра­

73

щение числа перебираемых вариантов решения задачи. В доказа­ тельство этого можно привести следующие положения.

Втеории линейного программирования доказывается, что если

взадаче имеется п неизвестных при т уравнениях, то число систем линейно независимых уравнений

т\ (т — л )!

т. е. по существу упорядоченную схему перебора вариантов, мы рез­ ко сокращаем число их, которое должно быть рассмотрено для отыскания оптимального решения. Так, число шагов (итераций), необходимых в симплекс-методе для получения оптимального ре­ шения, заключено между т и 2т, т. е. в приведенном примере 7-М4. Легко поэтому представить себе эффективность симплексметода решения задач линейного программирования. Очевидно, что при охарактеризованном переборе вариантов и последователь­ ном отыскании оптимального решения нужно иметь вначале какойто начальный (опорный) вариант. Вот почему решение задач ли­ нейного программирования распадается на два этапа: нахождение исходного (опорного) плана (решения); улучшение путем ряда последовательных попыток (итераций) опорного плана до опти­ мального, дающего экстремум целевой функции.

§11. Применение линейного программирования при отыскании оптимальных решений в области дорожного строительства

Вернемся к примеру, условия которого были даны табл. 17 и

уравнениями (V.4) — (V.6 ), (V.8 ), (V.9), (V.10). Получим для не­

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

ных планов является метод «северо-западного угла».

В верхнем левом (северо-западном) углу табл. 17 стоит одна из искомых переменных Х ц . На 1-м шаге примем произвольно ее

значение равным меньшей из величин а\ и Ъи т. е. *n = min(ai; by). Подобное назначение величины хп имеет совершенно опреде­ ленный смысл. Объем вывозки из карьера 1 на участок 1 не дол­ жен быть больше общей потребности в материале для этого участ­

ствует наибольшему, который только возможен по условиям зада­

Данные, полученные после 1-го цикла построения опорного пла­ на, приведены ниже:

.74

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

На 2-м шаге в северо-западном углу оказывается уже неизвест­ ная величина *2ь которая также назначается из условия х2\ —

= m in(a2;& i— 04).

Примем * 2 1 — 6 1 — aj = 1. Тогда после 2-го шага получаем следую­

щую таблицу-матрицу:

75