Файл: Методические материалы по курсу экономикоматематическое моделирование.doc

Варианты заданий по теме 3

Вариант 1
Составить двойственную задачу к исходной ЗЛП.

Z = -2x₁ + x₂ → min

x₁ - x₂ ≤ 3

x₁ + x₂ ≤ 9

-x₁ + x₂ ≥ 3

x₁ + x₂ ≥ 3/2

x₁ ≥0, x₂ ≥0
Вариант 2
Составить двойственную задачу к исходной ЗЛП.

Z = 4x₁ + 3x₂ → max

-x₁ + 3x₂ ≤ 9

2x₁ + 3x₂ ≤ 18

2x₁ - x₂ ≤ 10

x₁ ≥0, x₂ ≥0
Вариант 3
Составить двойственную задачу к исходной ЗЛП.

Z = x₁ + x₂ → max

-x₁ + x₂ ≤ 1

x₁ + 2x₂ ≤ 10

x₁ + 2x₂ ≥ 2

2x₁ + x₂ ≤ 10

x₁ ≥0, x₂ ≥0
Вариант 4
Составить двойственную задачу к исходной ЗЛП.

Z = 2x₁ + x₂ → max

x₁ + x₂ ≤ 8

3x₁ - 2x₂ ≤ 12

-x₁ + 2x₂ ≤ 8

2x₁ + 3x₂ ≥ 6

x₁ ≥0, x₂ ≥0
Вариант 5
Составить двойственную задачу к исходной ЗЛП.

Z = x₁ - 3x₂ → max

x₁ - x₂ ≤ 3

2x₁ + x₂ ≥ 3

x₁ - 3x₂ ≤ 1

x₁ ≥0, x₂ ≥0
Вариант 6
Составить двойственную задачу к исходной ЗЛП.

Z = 3x₁ + 5x₂ → min

x₁ + x₂ ≤ 5

3x₁ - x₂ ≤ 3

x₁ ≥0, x₂ ≥0
Вариант 7
Составить двойственную задачу к исходной ЗЛП.

Z = -2x₁ + x₂ → min

x₁ - x₂ ≤ 3

x₁ + x₂ ≤ 9

-x₁ + x₂ ≥ 3

x₁ + x₂ ≥ 3/2

x₁ ≥0, x₂ ≥0

Вариант 8
Составить двойственную задачу к исходной ЗЛП.

Z = 2x₁ + 2x₂ → min

x₁ + 3x₂ ≥ 3

-2x₁ + x₂ ≤ 2

x₁ + x₂ ≤ 5

x₁ ≥0, x₂ ≥0
Вариант 9
Составить двойственную задачу к исходной ЗЛП.

Z = 2x₁ + 2x₂ → max

x₁ + 3x₂ ≥ 3

-2x₁ + x₂ ≤ 2

x₁ + x₂ ≤ 5

x₁ ≥0, x₂ ≥0
Вариант 10
Составить двойственную задачу к исходной ЗЛП.

Z = 2x₁ + 3x₂ → min

x₁ + x₂ ≤ 4

6x₁ + 2x₂ ≥ 6

x₁ + 5x₂ ≥ 5

x₁ ≥0, x₂ ≥0

Тема 4. Транспортная задача

Пример задачи.
Мощности поставщиков: А₁ = 120 т; А₂ = 220 т; А₃ = 300 т; А₄ = 170 т. Спрос потребителей: В₁ = 120 т; В₂ = 250 т; В₃ = 200 т; В₄ = 180 т. Удельные затраты на перевозку единицы груза представлены матрицей С:

---

Определить объемы перевозок из пункта i в пункт j такие, чтобы суммарные издержки на перевозку были бы минимальными, т.е. построить матрицу объемов перевозок х.

.
Решение задачи:
1. Определить тип задачи – закрытый или открытый.

Задача открытая, т.к.



Вводится фиктивный потребитель с объемом потребления В_ф



2. Строится расчетная матрица с фиктивным потреблением В_ф и удельными затратами на перевозку фиктивного груза C_iф = 0. Исходное опорное решение поставленной транспортной задачи см. табл. 12.

Таблица 12

	120	250	200	180	Вф
120	2 120	4	5	2 0	0
220	5	6	2 200	3 20	0
300	4	3 80	5	7 160	0 60
170	6	2 170	6	6	0

3. Формируется опорный план перевозок по критерию наименьших удельных затрат на перевозку единицы груза, т.е. minC_ij. Затраты C_ij = 0 на перевозку фиктивных грузов не принимаются во внимание. Оставшиеся мощности сносятся фиктивному потребителю



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

K = m + n – 1 - план невырожденный,

K < m + n – 1 - план вырожденный,

где K - количество занятых клеток в таблице 12, т.е. количество

---

> 0;

m - количество строк матрицы;

n - количество столбцов.

В нашем примере задача вырожденная (7 < 4 + 5 – 1). Число занятых клеток К меньше значения (m + n – 1) на 1. Поэтому одну клетку нужно дополнительно заполнить нулевой поставкой. Такие клетки называют условно-занятыми. Нуль помещают в такую клетку, чтобы в каждой строке и столбце было не менее одной занятой клетки. Поместим нулевую поставку в клетку (1,4), т.е. х₁₄ = 0. Теперь задача стала невырожденной.
5. Оптимизируем опорный план, используя метод потенциалов.

Определяем потенциалы строк U_i и столбцов V_j по формуле:

С_ij = U_i + V_j . (1)

Для этого зададим одно любое значение потенциала U_i либоV_j, например, U₃ = 0.

Пересчитаем все остальные U_i , V_j по (1) и зафиксируем их в таблице 12:



6. Определяются оценки свободных клеток:

E_ij = C_ij – (U_i + V_j)  0 (2)

Е₁₂ = 4 – (- 5 + 3) = 6 Е₃₁ = 4 – (0 + 7) = - 3

Е₁₃ = 5 – (- 5 + 6) = 4 Е₃₃ = 6 – (0 + 6) = 0

Е_1ф = 0 – (- 5 + 0) = 5 Е₄₁ = 6 – (- 1 + 7) = 0

Е₂₁ = 5 – (- 4 + 7) = 2 Е₄₃ = 6 – (- 1 + 6) = 1

Е₂₂ = 6 – (- 4 + 3) = 7 Е₄₄ = 6 – (- 1 + 7) = 0

Е_2ф = 0 – (- 4 + 0) = 4 Е_4ф = 0 – (- 1 + 0) = 1.

7. Условие оптимальности задачи: Е _ij 0.

В нашем примере имеется отрицательная оценка (Е₃₁ = – 6). Для клетки (3,1) строим цикл (цепь, многоугольник) для перераспределения поставок. Все его вершины, кроме одной, должны находиться в занятых клетках, углы прямые, число вершин четное. Для указанной клетки (3,1) построим цикл отдельно (рис. 2а). Около свободной клетки цикла ставится знак (+), далее поочередно проставляются знаки (-) и (+). У вершин со знаком (-) выбирается минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+) и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новые значения грузов в вершинах цикла (рис. 2б).

---

– +






120

+ –
Рис. 2а Рис 2б
8. Перенесем цикл с новыми значениями (рис. 2б) в новую матрицу (табл. 13) и заполним таблицу поставками, не использованными в цикле.
Таблица 13

	120	250	200	180	Вф	Ui
	120 2	4	5	2 120	0	-5 -5
	220 5	6	2 200	3 20	0	-4
	300 4 120	3 80	6	7 40	0 60	0
	170 6	2 170	6	6	0	-1
Vj	4	3	6	7	0

Оценки свободных клеток матрицы (табл. 13) не отрицательны, т.е. Е_ij . Следовательно, полученное опорное решение оптимально:

Е₁₁ > 0; E₁₂ > 0; E_1ф > 0; E₂₁ > 0; E₂₂ > 0;

E_2ф > 0; E₃₃ = 0; E₄₁ > 0; E₄₃ > 0; E₄₄ = 0.

Задача решена.
9. Определяется значение целевой функции:

F = 2*120 + 2*200 + 3*20 + 4*120 + 3*80 + 7*40 + 2*170 = 2040 руб.

---

Варианты заданий по теме 4

Решить транспортную ЗЛП методом потенциалов, построив исходный опорный план способом минимального элемента.
Вариант 1

ai bj	80	60	170	80
110	8	1	9	7
190	4	6	2	12
90	6	5	8	9

Вариант 2

ai bj	30	70	90	110
50	3	8	10	5
150	1	4	6	2
100	3	1	9	7

Вариант 3

ai bj	15	7	14	62
51	24	19	23	15
19	14	21	15	16
28	10	9	6	11

Вариант 4

ai bj	25	135	40	100
100	5	2	1	1
110	3	7	5	5
90	6	5	4	4

---