Решение транспортной задачи средствами MathCAD.

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

Пример.

Дана транспортная задача (в виде таблицы). Найти ее исходное решение.

№	В1	В2	В3	Предложение
А1	70	38	24	14
А2	58	18	56	20
А3	19	10	100	26
Спрос	30	22	8

 

т.

Решение:

Исходный план будет состоять из 9-ти чисел (для данной задачи):

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

Математическая модель такой задачи имеет вид:

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

Системы равенств:

             

Система ограничений:

, при i=1,2,3; j=1,2,3.

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

Given

     

: =Minimize (y, , , , , , , , , )

=

(y, , , , , , , , , )=

 

Найденное решение означает следующее:

Производимые на предприятия А1 14 единиц продукции следует распределить по складам следующим образом:

склад В1 – 4 единицы;

склад В2 – 2 единицы;

склад В3 – 8 единиц.

Производимые на предприятии №2 20 единиц продукции следует распределить по складам следующим образом:

склад В1 – 0 единиц;

склад В2 – 20 единиц;

склад В3 – 0 единиц.

Производимые на предприятии №3 26 единиц продукции следует распределить по складам следующим образом:

склад В1 – 26 единиц;

склад В2 – 0 единиц;

склад В3 – 0 единиц.

Затраты на перевозку всех грузов при таком распределении продукции составят 1402 у.е. и эти затраты являются минимальными.

 

III раздел

Задача о назначениях

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

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

Возможные применения задач о назначениях представлены в таблице:

Ресурсы	Объекты	Критерии эффективности
Рабочие	Рабочие места	Время
Грузовые автомобили	Маршруты	Затраты
Станки	Участки	Объем переработанной продукции
Экипажи	Рейсы	Время простоя
Торговый агент	Города	Товарооборот

Матрица стоимостей имеет вид: где - затраты, связанные с назначением i- го ресурса на j- ый объект, i= j=1, n, где n- число объектов или ресурсов.

Обозначим:

Таким образом, решение задачи может быть записано в виде .

Допустимое решение называется назначением. Оно строится путем выбора ровно одного элемента в каждой строке матрицы и ровно одного элемента в каждом столбце этой матрицы.

Элементы матрицы С, соответствующие элементам матрицы X, будем отмечать кружками:

, .

 

Математическая постановка задачи:

 при ограничениях:

Алгоритм решения задачи

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

1)преобразования строк и столбцов матрицы;

2) определение назначения;

3) модификация преобразованной матрицы.

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

2 шаг. Если после выполнения 1-го шага в каждой строке и в каждом столбце матрицы С можно выбрать по одному нулевому элементу, то полученное решение будет оптимальным назначением.

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

Если после проведения 3-го шага оптимальное решение не достигнуто, то процедуру проведения прямых следует повторить до тех пор пока не будет получено допустимое решение.

Пример:

.

Распределить ресурсы по объектам.

Решение. 1шаг. Значения минимальных элементов строк1,2,3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая, из элементов каждого столбца соответствующее минимальное значение, получим:

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5, 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим:  

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

3 шаг: Вычеркиваем столбец 1, строку 3, строку 2 (или столбец 2). Значение минимального невычеркнутого элемента равно 2:

min=2.

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

Примечания

1. Если исходная матрица не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты, чтобы матрица стала квадратной.

2. Если какой-либо ресурс не может быть назначен на какой –то объект, то соответствующая стоимость полагается равной достаточно большому числу М.

3. Если исходная задача является задачей максимизации, то все элементы матрицы С следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем задачу следует решить как задачу минимизации.(например, задача о планировании загрузки оборудования с учетом максимальной производительности станков)

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

 

 

IVраздел

 Симплекс – метод

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

В канонической форме записи все переменные неотрицательны, ограничениями являются уравнения, и требуется найти такие значения переменных x_j, j=1, n, при которых целевая функция имеет максимум:

Переход к канонической форме записи можно осуществить с помощью следующих действий:

I. Ограничения вида «». В этом случае, для перехода к уравнению в левую часть неравенства добавляют дополнительную неотрицательную переменную.

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

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

IV. Если в задаче требуется найти минимум f, то заменяя f на – f, переходят к задаче максимизации, так как .

Алгоритм симплекс- метода

1. Приводим математическую модель задачи к каноническому виду (в случае неканонической).

2. Находим начальное решение и проверяем его на оптимальность.

Получение начального решения:

Выбираются m переменных, называемых базисными и обладающих следующим свойством: они входят с коэффициентом 1 только в одно уравнение и с коэффициентом 0 в остальные уравнения системы:

(1)

Остальные n- m переменных называются свободными.

Все свободные переменные полагаются равными нулю, а базисные переменные – равные правым частям соответствующих ограничений системы (1).

Если все , то начальное решение является допустимым.

3. Выражение функции f только через свободные переменные:

.

4. Проверка решения на оптимальность.

Для этого составляется симплекс- таблица:

Базисные переменные	Коэффициенты при переменных								Свободные члены
	X1	X2	…	Xm	…	XP	…	Xn
X1	a11	a12	…	a1m	…	a1p	…	a1n	b1
X2	a21	a22	…	a2m	…	a2p	…	a2p	b2
…	…	…	…	…	…	…	…	…	…
Xq	aq1	aq2	…	aqm	…	aqp	…	aqn	bq
…	…	…	…	…	…	…	…	…	…
Xm	am1	am2	…	amm	…	amp	…	amn	bm
f	-c1	-c2	…	-cm	…	-cp	…	-cn	0

 

Для проверки решения на оптимальность просматривается последняя f-строка:

4.1 Если коэффициенты, стоящие при свободных переменных неотрицательны, то полученное решение оптимально.

4.2 Если все эти коэффициенты положительны, то полученное решение единственно.

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

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

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

5. Получение нового решения.

5.1 Выбор переменной, вводимой в список базисных переменных.

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

5.2. Выбор переменной, выводимой из списка базисных переменных.

Находят отношение элементов столбца свободных членов к элементам разрешающего столбца. При делении на отрицательный элемент и 0 результат полагают равным +∞. Среди отношений находят минимальное. Строка соответствующая минимальному отношению, называется разрешающей. Базисная переменная, стоящая в этой строке, выводится из списка базисных переменных. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом.

 5.3.Выполнение симплекс-преобразования и переход к новой симплекс- таблице.

Переписываем разрешающую строку, разделив ее на ключевой элемент; остальные коэффициенты таблицы находим по правилу «прямоугольника»: новый элемент = (старый элемент)×(разрешающий элемент) -    ×      .

    

 

Элемент  находится в разрешающей строке в одном столбце со старым элементом. Элемент    находится в разрешающем столбце в одной строке со старым элементом.

Получаем новое опорное решение, которое снова проверяем на оптимальность и т.д. по рассмотренному алгоритму, пока не получим оптимальное решение.

Пример.