Булево линейное программирование. Решение транспортной задачи с замкнутым маршрутом и возвращением в исходный пункт

Размещено на http://www.allbest.ru/

ЛАБОРАТОРНАЯ РАБОТА

БУЛЕВО ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

С ЗАМКНУТЫМ МАРШРУТОМ И ВОЗВРАЩЕНИЕМ В ИСХОДНЫЙ ПУНКТ



Это задача оптимизации, в которой переменные принимают только два значения: “единица - ноль”. Пример - задача “коммивояжера”.

Цель работы: минимизировать продолжительность замкнутого маршрута при выезде из начального пункта, проезде через все заданные пункты с возвратом в него.

Программное обеспечение: программа линейного математического программирования “LINDO (LINGO”.

Условия задачи. Всего 5 пунктов, включая начальный пункт N1. Дана таблица (матрица) времени, затрачиваемого на переезд из каждого пункта (i) в каждый из остальных пунктов (j) - t_ij и наоборот (табл.1).

Таблица 1 Таблица времени, затрачиваемого на переезд из одного пункта в другой

Из пункта i	В пункт j
	1	2	3	4	5
1 2 3 4 5	0 1 8 14 10	10 0 9 10 8	25 10 0 24 25	25 15 20 0 27	10 2 10 15 0

Для составления математической модели необходимо ввести булевы переменные следующим образом: Принимаем, что

1, если из пункта i едем в пункт j; 0 - в противном случае (обратно).

Из пункта 1 можно выехать в любой из пунктов 2-5 или остаться в пункте 1. Но при этом можно выехать только в одном направлении. Это условие можно записать так:



₁₁ + ₁₂ + ₁₃ +₁₄ + ₁₅ = 1 или _1j =1.

Если из пункта i выехать в произвольный j- ый пункт, то запишем:

_ij =1, j = 1,…,5.

В результате задачу математически можно записать следующим образом:

x_ijij min. - целевая функция.

Ограничения: _ij =1, j = 1,…,5; - выезд из пункта i;

_ij =1, i = 1,…,5; - въезд в пункт j.

Конкретно для представленной таблицы времени целевая функция выглядит так:

F = t₁₁₁₁ + t₁₂₁₂ + t₁₃₁₃ + t₁₄₁₄ + t_{15 15} + t₂₁₂₁ + t₂₂₂₂ + … + t₅₅₅₅ min.

Значения t берутся из таблицы, а _ij являются искомыми переменными. Это булевы переменные. Они могут иметь 2 значения: 1 или 0.

Для простоты демонстрации решения задачи воспользуемся только тремя пунктами: 1, 2 и 3 из табл.1, т.е. рассмотрим матрицу 3 В таком случае целевую функцию можно представить следующим образом:

F = 10₁₂ + 25₁₃ + 1₂₁ + 10₂₃ + 8₃₁ + 9 ₃₂ min

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

из пункта 1: ₁₂ + ₁₃ = 1; в пункт 1: ₂₁ + ₃₁ = 1;

из пункта 2: ₂₁ + ₂₃ = 1; в пункт 2: ₁₂ + ₃₂ = 1;

из пункта 3: ₃₁ + ₃₂ = 1; в пункт 3: ₁₃ + ₂₃ = 1.

Граничные условия: _ij >0, _ij <0.

Для программы LINDO (LINGO) дополнительно после END можно обозначить эти величины как целые: GIN ₁₂, ₁₃, GIN _32.

Результаты: ₁₂ =1, ₁₃ =0, ₂₁ =0,₂₃ =1, ₃₁ =1, ₃₂ =0.

Значит, наиболее быстрый маршрут: пункты 1 > 2 > 3 > 1.

Минимальное время: 10 +10 +8 = 28 единиц времени.

Далее представлен листинг программы LINDO (LINGO) для решения представленного примера решения задачи.

Листинг программы.

MIN 10₁₂ + 25₁₃ + 1₂₁ + 10₂₃ + 8₃₁ + 9 ₃₂ -целевая функция

SUBJECT TO

₁₂ + ₁₃ = 1; - ограничения

₂₁ + ₃₁ = 1;

₂₁ + ₂₃ = 1;

₁₂ + ₃₂ = 1;

₃₁ + ₃₂ = 1;

₁₃ + ₂₃ = 1.

₁₂ >0 - граничные условия

₁₂ <1

₁₃ >0

₁₃ <1

₂₁ >0

₂₁ <1

₂₃ >0

₂₃ <1

₃₁ >0

₃₁ <1

₃₂ >0

₃₂ <1

END

GIN ₁₂ - обозначения целых величин

GIN ₁₃

GIN ₂₁

GIN ₂₃

GIN ₃₁

GIN ₃₂

Задание: в соответствии с представленным примером минимизировать замкнутый маршрут по 5 пунктам, т.е. по данным всей матрицы, представленной в табл.1.

Оптимизация функционирования системы при заданных ресурсных ограничениях

Цель работы: оптимизировать систему с ресурсными ограничениями.

Все, что необходимо для производственного процесса (финансы, рабочая сила, сырье и т.п.) можно объединить понятием “ресурсы”, среди которых можно выделить три основные группы: трудовые, материальные и финансовые. Большинство задач, возникающих в производстве можно рассматривать как преобразование ресурсов в результат (получение продукта и его реализацию). Поэтому значительная часть задач, возникающих при управлении производством, относится к классу задач распределения ресурсов.

Программное обеспечение: программа линейного математического программирования “LINDO (LINGO”.

В настоящей лабораторной рассматриваются два основных варианта задач.

Первый вариант: максимизировать полученный результат - R (количество продуктов или прибыль) при заданных ресурсах (Q).

Модель оптимизируемой системы:

Модель целевой функции (F):

F=R= _j max (прибыль),

где: c_J - прибыль, получаемая от единицы j-ой продукции;

x_J - количество продукции j - го вида;

n - количество видов продукции.

Модель ограничений (ресурсов):

где: а_ij - количество i - го ресурса, необходимого для изготовления еди ницы j- го вида продукции;

b_i - запас i - го ресурса;

m- количество видов ресурсов.

Граничные условия: x_Jmin ? x_J? x_Jmax .

Решение первого варианта задачи:

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

Таблица 1 Исходные данные

Ресурсы	Вид продукции	Располагаемый ресурс
	П1	П2	П3	П4
Трудовые	1	2	3	4	40
Материальные	6	5	4	3	110
Финансовые (на единицу продукции)	4	6	8	12	100 Сумма 250
Граница выпуска: нижняя верхняя	1 12	0 -	2 -	3 3
План выпуска	x1	x2	x3	x4
Прибыль от единицы продукции	60	70	120	130

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

Листинг программы “LINDO”

MAX 60x₁ + 70x₂ +120x₃ +130x₄

SUBJECT TO

X1+2X2+3X3+4X4 <=40

6X1+5X2+4X3+3X4 <= 110

4X1+6X2+8X3+12X4 <= 100

X1>=1

X1<=12

X2>=0

X3>=2

X4=3

END

Результаты:^*

1350 - максимальная прибыль

X1 = 12

X2 = 0 > оптимальное количество выпускаемой продукции

X3 = 2

X4 = 4

*На остальные цифры не обращать внимания

Далее необходимо подсчитать затраченные ресурсы (Q) как сумму произведений затраты ресурсов на единицу соответствующей продукции на вычисленное количество выпуска этой продукции: 30 + 89 +100 = 219

Коэффициент эффективности системы: 1350/219=6,16.

Второй вариант:

При заданной прибыли, например, R=1350 минимизировать используемые ресурсы Q.

C этой целью в модель вводятся дополнительные переменные: Y1, Y2, Y3.

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

F = Y1+Y2+Y3 > max

В результате модель ограничений приобретает следующий вид:

Сюда же добавляется еще одно ограничение по прибыли (R):

R=

Граничные условия сохраняются.

Листинг программы:

MAX Y1+Y2+Y3

SUBJECT TO

X1 + 2X2 + 3X3 + 4X4 + Y1 = 40

6X1 + 5X2 + 4X3 + 3X4 + Y2 =110

4X1 + 6X2 + 8X3 + 12X4 +Y3 =100

60X1 + 70X2 + 120X3 +130X4 >=1350

X1>=1

X1<=12

X2>=0

X3>=2

X4 = 3

END

Результаты:

69,5 (сумма неиспользованного ресурса, т.е. Y1+Y2+Y3)

Y1 = 4,5

Y2 = 65

Y3 = 0

X1 = 1

X2 = 0

X3 = 7,5

X4 = 3

В итоге:

1) прибыль (R) равна 1350 ед.

2) количество используемых ресурсов: Q = 250 - 69,5 = 180,5

3) план выпуска продукции: X1 = 1, X2 = 0, X3 = 7,5, X4 =3

4) коэффициент эффективности k = 1350/180,5 = 7,48.

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

Задание: в соответствии с представленным примером оптимизировать план выпуска продукции, прибыль от единицы которой составляет 60, 70, 130, 150 для каждого продукта. Остальные параметры системы сохранены без изменений.

Многокритериальная оптимизация. Реализация метода последовательных приближений в задаче с ресурсными ограничениями

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

Программное обеспечение: программа линейного математического программирования “LINDO (LINGO”. Приведен листинг программы.

Исходные условия задачи. Для изготовления двух видов продукции (x₁, x₂) используются два вида ресурсов (y₁, y₂). Дано количество ресурсов в условных единицах, затрачиваемых на изготовление единицы продукции:

Таблица 1. Исходные данные для решения задачи оптимизации

Вид ресурса	Запас ресурса	Число единиц ресурсов, затраченное на изготовление единицы продукции
		X1	X2
S1 S2	18 16	1 2	3 1

.

Даны также запасы ресурсов в условных единицах: S₁ ? 18, S₂ ? 16.

Прибыль получается от единицы продукции (x₁,x₂) соответственно 2 и 3 денежные единицы.

Необходимо рассчитать такой план выпуска продукции (x₁, x₂), который обеспечит максимум прибыли (первая целевая функция) и минимум затраченных ресурсов (вторая целевая функция).

Алгоритм решения поставленной задачи:

1. Построить модель системы.

2. Последовательное нахождение таких значений величин x₁ и x₂, которые обеспечат минимизацию затрат ресурсов при различных заданных величинах прибыли, например: 900, 950, 1000, 1050, 1100 денежных. ед., пока будет хватать ресурсов. С этой целью целесообразно использовать программу линейного программирования LINDO (LINGO), листинг которой приведен ниже. На каждом этапе расчетов определяется коэффициент эффективности.

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

Пример решения поставленной задачи.

Первый этап. Моделирование системы.

На рис.1 приведена блок-схема объекта исследования:

Размещено на http://www.allbest.ru/

Рис.1. Блок-схема объекта исследования.

Функция прибыли: y₁= 2x₁ + 3x₂ .

Функции потребления ресурсов: y₂ = x₁ +3x₂ 18,

(модели ограничений ресурсов) y₃ = 2x₁ + x₂ 16.

Второй этап. Последовательное проведение минимизации затраченных ресурсов для следующей последовательности зафиксированных значений прибыли: 10, 15, 17 и т.д. денежных единиц до конца имеющихся ресурсов. C этой целью в модель вводятся дополнительные переменные: z₂, z₃. Каждая из этих переменных является оценкой соответствующего неиспользуемого ресурса, т.е. разностью между располагаемым и потребленным ресурсом. Эта величина должна быть минимизирована. Следовательно, модель целевой (минимизируемой) функции имеет следующий вид:

F = z₂+ z₃ > max.

В результате модели ограничений ресурсов приобретают следующий вид:

y₂ = x₁ +3x₂ + z₂ = 18,

y₃ = 2x₁ + x₂ + z₃ =16.

Сюда добавляется функция ограничения по прибыли (y_огр) :

y₁= 2x₁ + 3x₂ ? y_огр

Ниже представлен листингпрограммы LINDO, с помощью которой последовательно проводится минимизация затрат при различных заданных значениях прибыли: 10, 15, 17, 22 и 24 ден. ед. Каждый раз вычисляются затраты ресурсов и коэффициент эффективности (Кэф.), равный отношению прибыли к затратам. Результаты сведены в табл.2.

Листинг программы LINDO (LINGO):

MAX Z2+ Z3

SUBJECT TO

X1 + 3X2 + Z2 = 181

2X1 + X2 + Z3 = 16

2X1 + 3X2 >=10 (начальная величина зафиксированной прибыли)

X1>=1 граничные условия

X2>=1

END1

GIN X1 обозначения целых величин

GIN X2

Таблица 2 Результаты экспериментов

Прибыль	10	15	17	22	24
Затраты	14	21	23	33	34
Кэф	0,71	0,71	0,74	0,67	0,70
Выпуск продукции (x1,x2)	2 2	3 3	1 5	5 4	6 4

На основании сравнительного анализа результатов необходимо принять решение о выборе одного из двух вариантов плана выпуска продукции (x₁, x₂) : при максимальной эффективности производства (третья колонка) или при максимальной прибыли, но не самой высокой эффективности (последняя колонка).

Задание: осуществить оптимизацию представленной системы в соответствии с приведенным примером, но с измененными данными об ограничениях по ресурсам: 20 вместо 18 по одному (y₂) и 18 вместо 16 по другому (y₃) ресурсу.

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

Цель работы: минимизировать суммарные транспортные расходы в соответствии с представленной на рис.1 схемой.

Программное обеспечение: программа линейного программирования LINDO. маршрут ограничение транспортный задача

Необходимо перевезти продукцию от поставщика (склады A₁ A₂) к потребителю в три точки: B₁ B₂ B₃, как показано на схеме:

Размещено на http://www.allbest.ru/

Рис.1. Схема доставки груза. Цифрами отмечены транспортные затраты на перевозку единицы груза

Таблица условий

Поставщик	Потребитель (заказчик)	Запасы
	В1	В2	В3
А1	7 x11	9 x12	21 x13	100
А2	20 x21	15 x22	16 x23	200
Заявки	80	130	90	300

Примечания: 1) x_ij - число единиц груза, которые i - ый поставщик должен отправить j - му потребителю; 2) в углах ячеек представлены транспортные затраты на перевозку единицы груза в соответствующем направлении.

Задача: минимизировать суммарные транспортные расходы.

Модель системы:

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

F = 7x₁₁ +9 x ₁₂ +21 x ₁₃ +20 x ₂₁ +15 x ₂₂ +16 x ₂₃ > min.

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

x₁₁ + x_{12 +} x₁₃ = 100,

x_{21 +} x_{22 +} x₂₃ = 200,

x₁₁ + x₂₁ = 80,

x₁₂ + x₂₂ = 130,

x₁₃ + x₂₃ = 90.

Граничные условия: x_ij ? 0, где i = 1, 2 ; j = 1, …, 3.

Решение задачи: листинг программы Lindo (Lingo)

MIN 7x₁₁ +9 x ₁₂ +21 x ₁₃ +20 x ₂₁ +15 x ₂₂ +16 x ₂₃ -целевая функция

SUBJECT TO

x₁₁ + x₂₁ = 80 -ограничения

x₁₂ + x₂₂ = 130

x₁₃ + x₂₃ = 90

x₁₁ + x_{12 +} x₁₃ = 100

x_{21 +} x_{22 +} x₂₃ = 200

x₁₁ >=0 x₂₁ >=0 -граничные условия

x₁₂ >=0 x₂₂ >=0

x₁₃ >=0 x₂₃>=0

END

Результаты: минимальные суммарные транспортные расходы (F_min) составляют 3830 денежных единиц. Такой результат может быть достигнут при перевозке груза в следующих пропорциях:

x₁₁ = 80; x₂₁ = 0;

x₁₂ = 20; x₂₂ = 110;

x₁₃ = 0; x₂₃ = 90;

Задание: рассчитать минимальные транспортные расходы и оптимизировать перевозку груза в соответствии со схемой, представленной на рис.2.

Размещено на http://www.allbest.ru/

Рис.2. Схема доставки груза для выполнения лабораторной работы

Размещено на Allbest.ru