Решите задачи линейного программирования (8.31 — 8.60) графи­ческим методом, проведите анализ на чувствительность.

Во всех задачах .

8.31. 8.32.

8.33. 8.34.

8.35. 8.36.

8.37. 8.38.

8.39. 8.40.

8.41. 8.42.

8.43. 8.44.

8.45. 8.46.

8.47. 8.48.

8.49. 8.50.

8.51. 8.52.

8.53. 8.54.

8.55. 8.56.

8.57. 8.58.

8.59. 8.60.

Задачи линейного программирования (8.61 – 8.90) решите симплекс-методом и проведите анализ моделей на чувствительность, сформулируйте двойственную задачу к исходной и решите её.

8.61.

8.62.

8.63.

8.64.

8.65.

8.66.

8.67.

8.68.

8.69.

8.70.

8.71.

8.72.

8.73.

8.74.

8.75.

8.76.

8.77.

8.78.

8.79.

8.80.

8.81.

8.82.

8.83

8.84

8.85.

8.86

8.87

8.88

8.89

8.90

9. Транспортные задачи линейного программирования

9.1. Постановка задачи

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них яв­ляется, как правило, распределение ресурсов, находящихся у т производителей (поставщиков), по п потребителям этих ресурсов.

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

• прикрепление потребителей ресурса к производителям;

• привязка пунктов отправления к пунктам назначения;

• взаимная привязка грузопотоков прямого и обратного направле­ний;

• отдельные задачи оптимальной загрузки промышленного обору­дования;

• оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются т пунктов отправления груза и объемы отправления по каждому пункту а_1, а₂, ..., а_т. Известна потребность в грузах по каждому из п пунктов назначения. Задана матрица стоимостей доставки по каж­дому варианту . Необходимо рассчитать оптимальный план перевозок, т. е. определить, сколько груза должно быть отправлено из каждого i-го пункта отправления (от поставщи­ка) в каждый j-й пункт назначения (до потребителя) x_ij с мини­мальными транспортными издержками.

В общем виде исходные данные представлены в табл. 9.1.

Таблица 9.1

Исходные данные

Потребители Поставщики	В1	В2	…	Вn	Запасы (объёмы потребления)
А1			…
А2			…
…	…	…	…	…	…
Аm			…
Потребность			…

Транспортная задача называется закрытой, если суммарный объём отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения :

(9.1)

Если такого равенства нет (потребности выше запасов или на­оборот), задачу называют открытой, т. е.:

(9.2)

Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнений.

Все грузы из i-х пунктов должны быть отправлены, т. е.:

(9.3)

Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

(9.4)

Суммарные объемы отправления должны равняться суммар­ным объемам назначения:

Должно выполняться условие неотрицательности переменных: . Перевозки необходимо осуществить с ми­нимальными транспортными издержками (функция цели):

(9.6)

В модели (9.3) — (9.6) вместо матрицы стоимостей перевозок () могут задаваться матрицы расстояний. В таком случае в каче­стве целевой функции рассматривается минимум суммарной транс­портной работы. Как видно из выражения (9.5), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае если

• потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщике недостающим объемом отправления;

• запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом по­требления.

Варианты, связывающие фиктивные пункты с реальными, име­ют нулевые оценки. После введения фиктивных пунктов задача ре­шается как закрытая.

Транспортным задачам присущи следующие особенности:

• распределению подлежат однородные ресурсы;

• условия задачи описываются только уравнениями;

• все переменные выражаются в одинаковых единицах измерения;

• во всех уравнениях коэффициенты при неизвестных равны еди­нице;

• каждая неизвестная встречается только в двух уравнениях систе­мы ограничений.

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