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

Сформулировать линейную производственную задачу и составить ее математическую модель, взяв исходные данные из приложения 1, где технологическая матрица А затрат различных ресурсов на единицу каждой продукции, вектор объемов ресурсов В и вектор удельной прибыли С при возможном выпуске четырех видов продукции с использованием трех видов ресурсов

Компактно записаны в виде

C1 c2 c3 c4

А11 а12 а13 а14 b1

A21 a22 a23 a24 b2

A31 a32 a33 a34 b3

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

В последней симплексной таблице указать обращенный базис Q-1, соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения H = Q-1B

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

    1.16 27 10 9 8 3 5 0 6 144 2 0 1 0 130 1 4 2 3 140

Задача имеет вид:

F(X) = 27x1 + 10x2 + 9x3 + 8x4 > max при ограничениях:

    3x1 + 5x2 + 6x4?144 2x1 + x3?130

X1 + 4x2 + 2x3 + 3x4?140

Для приведения к канонической форме необходимо:

В 1-м неравенстве смысла (?) вводим базисную переменную x5. В 2-м неравенстве смысла (?) вводим базисную переменную x6. В 3-м неравенстве смысла (?) вводим базисную переменную x7.

    3x1 + 5x2 + 0x3 + 6x4 + 1x5 + 0x6 + 0x7 = 144 2x1 + 0x2 + 1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 130 1x1 + 4x2 + 2x3 + 3x4 + 0x5 + 0x6 + 1x7 = 140

F(X) = 27x1 + 10x2 + 9x3 + 8x4

Расширенная матрица системы ограничений-равенств данной задачи:

3

5

0

6

1

0

0

144

2

0

1

0

0

1

0

130

1

4

2

3

0

0

1

140

Поскольку в системе имеется единичная матрица, то соответствующие уравнения имеют вид:

    3x1 + 5x2 + 6x4 + x5 = 144 2x1 + x3 + x6 = 130

X1 + 4x2 + 2x3 + 3x4 + x7 = 140

Выразим базисные переменные через остальные:

X = - 3x1 - 5x2 - 6x4 - x5+144

X = - 2x1 - x3 - x6+130

X = - x1 - 4x2 - 2x3 - 3x4 - x7+140

Подставим их в целевую функцию:

F(X) = 27x1 + 10x2 + 9x3 + 8x4

F(X) = 27x1 + 10x2 + 9x3 + 8x4 > max

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

    - 3x1 - 5x2 - 6x4 - x5+144 ? 0 - 2x1 - x3 - x6+130 ? 0 - x1 - 4x2 - 2x3 - 3x4 - x7+140 ? 0

Приводим систему неравенств к следующему виду:

    3x1 + 5x2 + 6x4 + x5 ? 144 2x1 + x3 + x6 ? 130

X1 + 4x2 + 2x3 + 3x4 + x7 ? 140

F(X) = 27x1 + 10x2 + 9x3 + 8x4 > max

Упростим систему.

    3x1 + 5x2 + 6x4 + x5 ? 144 2x1 + x3 + x6 ? 130

X1 + 4x2 + 2x3 + 3x4 + x7 ? 140

F(X) = 27x1 + 10x2 + 9x3 + 8x4 > max

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

Определим максимальное значение целевой функции F(X) = 27x1 + 10x2 + 9x3 + 8x4 при следующих условиях-ограничений.

    3x1 + 5x2 + 6x4 + x5?144 2x1 + x3 + x6?130

X1 + 4x2 + 2x3 + 3x4 + x7?140

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (?) вводим базисную переменную x8. В 2-м неравенстве смысла (?) вводим базисную переменную x9. В 3-м неравенстве смысла (?) вводим базисную переменную x10.

    3x1 + 5x2 + 0x3 + 6x4 + 1x5 + 0x6 + 0x7 + 1x8 + 0x9 + 0x10 = 144 2x1 + 0x2 + 1x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 + 1x9 + 0x10 = 130 1x1 + 4x2 + 2x3 + 3x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 + 1x10 = 140

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

3

5

0

6

1

0

0

1

0

0

2

0

1

0

0

1

0

0

1

0

1

4

2

3

0

0

1

0

0

1

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

Решим систему уравнений относительно базисных переменных:

X8, x9, x10,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,0,0,0,0,144,130,140)

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

Базис

B

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X8

144

3

5

0

6

1

0

0

1

0

0

X9

130

2

0

1

0

0

1

0

0

1

0

X10

140

1

4

2

3

0

0

1

0

0

1

F(X0)

0

-27

-10

-9

-8

0

0

0

0

0

0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

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

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

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления:bi / ai1

И из них выберем наименьшее:

Min (144:3 , 130:2 , 140:1) = 48

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Базис

B

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

Min

X8

144

3

5

0

6

1

0

0

1

0

0

48

X9

130

2

0

1

0

0

1

0

0

1

0

65

X10

140

1

4

2

3

0

0

1

0

0

1

140

F(X1)

0

-27

-10

-9

-8

0

0

0

0

0

0

0

Похожие статьи




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

Предыдущая | Следующая