Методические указания по изучению дисциплины и выполнению контрольной работы (стр. 6 из 14)

C x₁

Рис.2.3

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

Теперь нужно среди точек построенного многоугольника найти такую, в которой целевая функция Z=12x₁+15x₂ достигает максимального значения. Для этого построим прямую, заданную уравнением 12х₁+15х₂=0, которая является линией нулевого уровня функции Z.

Направление возрастания линейной функции Z=12x₁+15x₂ указывает вектор

с началом в точке (0;0) и концом в точке М₁(12,15), координаты которой равны коэффициентам при соответствующих переменных функции Z.

Для нахождения оптимального плана нужно «передвигать» линию нулевого уровня Z параллельно самой себе в направлении вектора

до точки ее «последней встречи» с многоугольником, которая и является оптимальным планом задачи. В нашем случае это вершина В многоугольника OABCD - точка пересечения прямых (а) и (в). Координаты (

) точки найдем, решив систему уравнений.

откуда х₁^*=2, х₂^*=4.

Найдем соответствующее значение целевой функции:

усл. ед.

Ответ. Для обеспечения максимального дохода от реализации готовой продукции предприятию необходимо выпустить 2 ед. продукции вида А и 4 ед. продукции вида В. При таком плане доход от реализации составит 84 усл. ед.

Геометрический метод решения ЗЛП обладает рядом достоинств: он прост, нагляден, позволяет быстро и легко получить ответ. Однако только геометрический метод решения никак не может удовлетворить ни математиков, ни экономистов. Возможны «технические» погрешности, которые неизбежно возникают при приближенном построении графиков. Второй недостаток геометрического метода заключается в том, что многие величины, имеющие четкий экономический смысл (такие, как остатки ресурсов производства, избыток питательных веществ и т.п.), не выявляются при геометрическом решении задач. Но самое главное - геометрический метод неприемлем для решения практических задач. Поэтому необходимы аналитические методы, позволяющие решать ЗЛП с любым числом переменных и выявить экономический смысл входящих в них величин.

3. Транспортная задача

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

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

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

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

Пусть имеется m поставщиков А₁, А₂, ...,А_m однородного груза в количествах соответственно а_1,а₂,...,а_m единиц и n потребителей В_1,В₂,...,В_n этого груза, потребность которых составляет соответственно b₁, b_2,...,b_n единиц. Известна стоимость (тариф) c_ij перевозки единицы груза от i-го (i=

поставщика к j-му (

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

Обычно исходные данные транспортной задачи представляют в виде табл. 1:

табл.1

B_j A_i	b₁	b₂	...	b_n
a₁	c₁₁	c₁₂	...	c_1n
a₂	c₂₁	c₂₂	...	c_2n
...	...	...	...	...
a_m	c_m1	c_m2	...	c_mn

При постановке конкретных задач перевозки грузов может возникнуть одна из трех ситуаций:

(3.1)

(3.2)

(3.3)

Каждой ситуации соответствует определенная модель ТЗ: ситуации (3.1) (суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей) отвечает закрытая модель ТЗ (сбалансированная транспортная модель), а ситуациям (3.2) и (3.3) - отвечает открытая модель ТЗ (несбалансированная транспортная модель).

3.2. Экономико-математическая модель ТЗ

Рассмотрим ситуацию (3.1). Обозначим через

количество единиц груза, которое необходимо доставить от i-го поставщика к j-му потребителю.

Экономико-математическая модель ТЗ должна отражать все условия и цель задачи в математической форме. Переменные

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

(3.4)

(3.5)

(3.6)