Лабораторная работа № 3 Транспортная задача линейного программирования

Цель работы:

Научиться составлять экономико-математические модели транспортных задач и решать задачи методом потенциалов.

1.Общие сведения

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

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

Математически транспортная задача по критерию стоимости формируется следующим образом. Имеется п потребителей и т поставщиков однородного груза. Мощность i-гo поставщика (i = 1,m) обозначим а_i, спрос j-го потребителя (j = 1,п) b_j. Затраты на перевозку одной тонны груза от i-гo поставщика до j-го потребителя обозначим с_ij. Размер поставки продукции поставщиком i потребителю j обозначим х_ij ; общую сумму затрат на перевозку груза обозначим через F.

Запишем математическую модель задачи:

1) объем поставок i-гo поставщика должен равняться количеству имеющегося у него груза:

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

3) запас груза у поставщиков должен равняться суммарному спросу потребителей:

4) размер поставок должен выражаться неотрицательным числом:

5) общая сумма затрат на перевозку груза должна быть минимальной:

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

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

Пример: Найти решение транспортной задачи, исходные данные которой приведены в таблице.

Пункты отправления	Пункты назначения						Запасы
	В1	В2	В3	В4	В5
А1 А2 А3	5 7 8	3 6 9	2 5 4	4 3 5		8 1 2	160 80 140
Потребности	90	70	80	70		90

При дополнительных условиях: из А1 а В1 должно быть перевезено не менее 50 ед. груза, из А3 в В5 – не менее 60 ед., а из А2 в В4 – не более 50 ед. груза.

Решение:

1) Определим тип задачи:

Пункты имеют (общий запас): 160+80+140=380; общие потребности составляют: 90+70+80+70+90=400. Значит задача открытого типа: так как общий запас груза не равен общему объему потребностей.

Составим модель задачи:

x_ij- количество груза, перевозимое из i – го пункта в j – ый пункт, i =1,2,3; j=1,2,3,4,5.

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

Целевая функция:

F=5x₁₁+3x₁₂+2x₁₃+4x₁₄+8x₁₅+7x₂₁+6x₂₂+5x₂₃+3x₂₄+x₂₅+8x₃₁+9x₃₂+4x₃₃ +5x₃₄+2x₃₅min

2)Оформление задачи в Excel имеет вид:

Заполняем окно Поиска решения следующим образом:

После нажатия кнопки Выполнить, получился следующий результат:

Таким образом, план перевозки продукции с минимальными суммарными затратами по ее доставке следующий: из пункта А1 в В1 перевозится 70 ед. груза, в В2 – 70, в В3 – 20; из А2 в В4 – 50 ед. груза, в В5 – 30; из А3 в В3 – 60, в В4 – 20 ед, в В5 – 60. Общие затраты по транспортировки составят 1240 ден. ед.

2. Порядок выполнения работы

2.1.Ознакомится с методическими указаниями, изложенными в п.1;

2.2.Составить экономико-математические модели задач (по указанию преподавателя)

2.3.Решить задачи, используя метод потенциалов.

3. Содержание отчета:

3.1.Тема и цель работы

3.2.Условия задач

3.3.Экономико-математические модели задач.

3.4. Результаты решения.

3.5.Выводы по работе.