Построение межотраслевого баланса

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

" Забайкальский государственный университет"

Факультет дополнительного профессионального образования Кафедра экономики и бухгалтерского учета Контрольная работа По предмету: «Методы оптимальных решений»

Выполнил: студент гр. ЭКБ — 12−1 Лескова А.С.

Проверил: Мурзина Н.В.

Чита 2014

Задача 1

Заданы таблица межотраслевых потоков и таблица конечных продуктов. Постройте межотраслевой баланс в отчетном периоде и, увеличив конечный продукт на 10 процентов, постройте межотраслевой баланс в плановом периоде.

Таблицы межотраслевых потоков

Таблица конечных продуктов

Решение.

1. Построим межотраслевой баланс в отчетном периоде и занесем в таблицу:

2. Построим межотраслевой баланс в плановом периоде.

Найдем матрицу А прямых затрат, элементы которой рассчитаем по формуле

:

Она имеет неотрицательные значения и удовлетворяет критерию продуктивности:

Поэтому для любого вектора конечного продукта можно найти необходимый объем валового выпуска по формуле:

.

Матрица .

Обратная к ней матрица имеет вид:

.

Посчитаем величину конечного продукта в плановом периоде, увеличив его на 10%:

.

Определим величину валовой продукции в плановом периоде:

=.

Посчитаем межотраслевые потоки в плановом периоде по формуле

межотраслевой баланс в плановом периоде

Задача 2

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

Решение.

Определим сначала многоугольник решений, для чего систему ограничений-неравенств запишем в виде уравнений и пронумеруем их:

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

Прямая (1) — х₂ = 2 + 2х₁ — проходит через точки:

Прямая (2) — х₂ = - 1+ 1/3 х₁ — проходит через точки:

Прямая (3) — х₂ = 8 — 4/3 х₁ — проходит через точки:

Построим область допустимых значений — треугольник ABC.

Координаты вектор-градиента равны коэффициентам целевой функции:

.

Проведём через область ABCD произвольную линию уровня перпендикулярно направлению градиента — прямая, линия уровня.

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

Предельное положение — линия (4). Следовательно, точка В является оптимальным решением, обеспечивающим максимальное значение целевой функции.

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

Предельное положение — линия (5). Следовательно, точка, А является оптимальным решением, обеспечивающим минимальное значение целевой функции.

Определим координаты точки В как пересечение прямых (2) и (3):

Следовательно, максимальное значение целевая функция достигает в точке и равно .

Определим координаты точки, А как пересечение прямых (2) и оси Ох₁:

Следовательно, минимальное значение целевая функция достигает в точке и равно .

Задача 3

Решить симплексным методом задачи:

Решение.

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений

Введем искусственные переменные x:

Для постановки задачи на максимум целевую функцию запишем так:

Z (X) = x₁ + 4x₂ + x₃ — Mx₆ — Mx₇ > max

Из уравнений выражаем искусственные переменные и подставим в целевую функцию:

x₆ = 4 + x_{1 -} 2x_{2 -} x₃

x₇ = 6 — 2x_{1 -} 3x₂ — x₃+x₅

Z (X) = x₁ + 4x₂ + x₃ — M (4 + x₁ — 2x₂ — x₃) — M (6 — 2x₁ — 3x₂ — x₃ + x₅) > max

Z (X) = (1 + M) x₁ + (4 + 5M) x₂ + (1 + 2M) x₃ + (- M) x₅ + (- 10M) > max

Решим систему уравнений относительно базисных переменных: x₆, x₄, x₇.

Полагая, что свободные переменные равны 0, получим первый опорный план: X₁ = (0,0,0,9,0,4,6)

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее: min (4: 2, 9: 1, 6: 3) = 2

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

Получаем новую симплекс — таблицу:

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

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

min (-, 7: 3.5, 0: 3.5) = 0

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

Получаем новую симплекс — таблицу:

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i5

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

min (-, 7: 1, —) = 7

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

Получаем новую симплекс — таблицу:

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

Так как в оптимальном решении отсутствуют искусственные переменные (равны нулю), то данное решение является допустимым.

Оптимальный план можно записать так: x₂ = 3, x₁ = 2.

Тогда Z_max = 4*3 + 1*2 = 14.

Задача 4

Решить методом потенциалов транспортные задачи:

Решение.

Проверим равенство запасов и потребностей:

;

.

Равенство не выполняется (), следовательно, транспортная задача является открытой. Сведём её к закрытой модели путем введения фиктивного поставщика. Положим его запас равным дефициту ресурса (100 — 80 = 20), а тарифы на перевозки — равными 0.

Построим новую транспортную таблицу и определим начальное распределение методом северо-западного угла:

При этом стоимость перевозок составит:

Проверяем количество заполненных клеток — 8, а должно быть Следовательно, опорный план является вырожденным.

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

При этом стоимость перевозок составит:

Проверяем количество заполненных клеток — 8, а должно быть Следовательно, опорный план является вырожденным. Для получения невырожденного плана принудительно добавляем нуль (0) в клетку (1,2) и (1,3).

Определим потенциалы и оценки свободных клеток:

u₁ + v₁ = 1

u₁ + v₂ = 5

u₁ + v₃ = 7

u₂ + v₄ = 7

u₂ + v₅ = 13

u₃ + v₄ = 4

u₄ + v₃ = 2

u₄ + v₅ = 3

u₅ + v₂ = 2

u₆ + v₅ = 0

Пусть u₁ = 0, тогда v₁ = 1, v₂ = 5, v₃ = 7, u₄ = - 5, v₅ = 8, u₂ = 5, v₄ = 2, u₃ = 2, u₅ = - 3, u₆ = - 8

Найдём оценки свободных клеток :

S₁₄ = 9 — (0 + 2) = 7

S₁₅ = 3 — (0 + 8) = - 5

S₂₁ = 4 — (5 + 1) = - 2

S₂₂ = 6 — (5 + 5) = - 4

S₂₃ = 4 — (5 + 7) = - 8

S₃₁ = 1 — (2 + 1) = - 2

S₃₂ = 5 — (2 + 5) = - 2

S₃₃ = 3 — (2 + 7) = - 6

S₄₁ = 2 — (-5 + 1) = 6

S₄₂ = 4 — (-5 + 5) = 4

S₄₄ = 10 — (-5 + 2) = 13

S₅₁ = 3 — (-3 + 1) = 5

S₅₃ = 5 — (-3 + 7) = 1

S₅₄ = 6 — (-3 + 2) = 7

S₅₅ = 4 — (-3 + 8) = - 1

S₆₁ = 0 — (-8 + 1) = 7

S₆₂ = 0 — (-8 + 5) = 3

S₆₃ = 0 — (-8 + 7) = 1

S₆₄ = 0 — (-8 + 2) = 6

S₆₅ = 0 — (-8 + 8) = 0

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

Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой — клетка (2;3) — и строим цикл, первая вершина которого находится в выбранной клетке, а остальные — в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «-», начиная со свободной клетки.

Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «-»): min (25;5) = 5. Перераспределяем 5 единиц ресурса и получаем новый план поставок:

При этом стоимость перевозок составит:

Определим потенциалы и оценки свободных клеток:

u₁ + v₁ = 1

u₁ + v₂ = 5

u₁ + v₃ = 7

u₂ + v₃ = 4

u₂ + v₄ = 7

u₃ + v₄ = 4

u₄ + v₃ = 2

u₄ + v₅ = 3

u₅ + v₂ = 2

u₆ + v₅ = 0

Пусть u₁ = 0, тогда v₁ = 1, v₂ = 5, v₃ = 7, u₄ = - 5, v₅ = 8, u₂ = - 2, v₄ = 9, u₃ = 1, u₅ = - 3, u₆ = - 8. Найдём оценки свободных клеток :

S₁₄ = 9 — (0 + 9) = 0

S₁₅ = 3 — (0 + 8) = - 5

S₂₁ = 4 — (-2 + 1) = 5

S₂₂ = 6 — (-2 + 5) = 3

S₂₅ = 13 — (-2 + 8) = 7

S₃₁ = 1 — (1 + 1) = - 1

S₃₂ = 5 — (1 + 5) = - 1

S₃₃ = 3 — (1 + 7) = - 5

S₄₁ = 2 — (-5 + 1) = 6

S₄₂ = 4 — (-5 + 5) = 4

S₄₄ = 10 — (-5 + 9) = 6

S₅₁ = 3 — (-3 + 1) = 5

S₅₃ = 5 — (-3 + 7) = 1

S₅₄ = 6 — (-3 + 9) = 0

S₅₅ = 4 — (-3 + 8) = - 1

S₆₁ = 0 — (-8 + 1) = 7

S₆₂ = 0 — (-8 + 5) = 3

S₆₃ = 0 — (-8 + 7) = 1

S₆₄ = 0 — (-8 + 9) = 1

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

Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой — клетка (3;3) — и строим цикл, первая вершина которого находится в выбранной клетке, а остальные — в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «-», начиная со свободной клетки.

Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «-»):min (10;5) = 5. Перераспределяем 5 единиц ресурса и получаем новый план поставок:

При этом стоимость перевозок составит:

Определим потенциалы и оценки свободных клеток:

u₁ + v₁ = 1

u₁ + v₂ = 5

u₁ + v₃ = 7

u₂ + v₄ = 7

u₃ + v₃ = 3

u₃ + v₄ = 4

u₄ + v₃ = 2

u₄ + v₅ = 3

u₅ + v₂ = 2

u₆ + v₅ = 0

Пусть u₁ = 0, тогда

v₁ = 1, v₂ = 5, v₃ = 7, u₄ = - 5, v₅ = 8, u₂ = - 1, v₄ = 8, u₃ = - 4, u₅ = - 3, u₆ = - 8. Найдём оценки свободных клеток :

S₁₄ = 9 — (0 + 8) = 1

S₁₅ = 3 — (0 + 8) = - 5

S₂₁ = 4 — (-1 + 1) = 4

S₂₂ = 6 — (-1 + 5) = 2

S₂₃ = 4 — (-1 + 7) = - 2

S₂₅ = 13 — (-1 + 8) = 6

S₃₁ = 1 — (-4 + 1) = 4

S₃₂ = 5 — (-4 + 5) = 6

S₄₁ = 2 — (-5 + 1) = 6

S₄₂ = 4 — (-5 + 5) = 4

S₄₄ = 10 — (-5 + 8) = 7

S₅₁ = 3 — (-3 + 1) = 5

S₅₃ = 5 — (-3 + 7) = 1

S₅₄ = 6 — (-3 + 8) = 1

S₅₅ = 4 — (-3 + 8) = - 1

S₆₁ = 0 — (-8 + 1) = 7

S₆₂ = 0 — (-8 + 5) = 3

S₆₃ = 0 — (-8 + 7) = 1

S₆₄ = 0 — (-8 + 8) = 0

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

Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой — клетка (1;

5) — и строим цикл, первая вершина которого находится в выбранной клетке, а остальные — в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «-», начиная со свободной клетки.

Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «-»): min (0;10) = 0. Перераспределяем 0 единиц ресурса и получаем новый план поставок:

При этом стоимость перевозок составит:

Определим потенциалы и оценки свободных клеток:

u₁ + v₁ = 1

u₁ + v₂ = 5

u₁ + v₅ = 3

u₂ + v₄ = 7

u₃ + v₃ = 3

u₃ + v₄ = 4

u₄ + v₃ = 2

u₄ + v₅ = 3

u₅ + v₂ = 2

u₆ + v₅ = 0

Пусть u₁ = 0, тогдаv₁ = 1, v₂ = 5, v₃ = 2, u₄ = 0, v₅ = 3, u₂ = 4, v₄ = 3, u₃ = 1, u₅ = - 3, u₆ = - 3

Найдём оценки свободных клеток :

S₁₃ = 7 — (0 + 2) = 5

S₁₄ = 9 — (0 + 3) = 6

S₂₁ = 4 — (4 + 1) = - 1

S₂₂ = 6 — (4 + 5) = - 3

S₂₃ = 4 — (4 + 2) = - 2

S₂₅ = 13 — (4 + 3) = 6

S₃₁ = 1 — (1 + 1) = - 1

S₃₂ = 5 — (1 + 5) = - 1

S₄₁ = 2 — (0 + 1) = 1

S₄₂ = 4 — (0 + 5) = - 1

S₄₄ = 10 — (0 + 3) = 7

S₅₁ = 3 — (-3 + 1) = 5

S₅₃ = 5 — (-3 + 2) = 6

S₅₄ = 6 — (-3 + 3) = 6

S₅₅ = 4 — (-3 + 3) = 4

S₆₁ = 0 — (-3 + 1) = 2

S₆₂ = 0 — (-3 + 5) = - 2

S₆₃ = 0 — (-3 + 2) = 1

S₆₄ = 0 — (-3 + 3) = 0

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

Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой — клетка (2;

2) — и строим цикл, первая вершина которого находится в выбранной клетке, а остальные — в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «-», начиная со свободной клетки.

Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «-»): min (0; 5; 20;10) = 0. Перераспределяем 0 единиц ресурса и получаем новый план поставок:

Определим потенциалы и оценки свободных клеток:

u₁ + v₁ = 1

u₁ + v₅ = 3

u₂ + v₂ = 6

u₂ + v₄ = 7

u₃ + v₃ = 3

u₃ + v₄ = 4

u₄ + v₃ = 2

u₄ + v₅ = 3

u₅ + v₂ = 2

u₆ + v₅ = 0

Пусть u₁ = 0, тогда v₁ = 1, v₂ = 4, v₃ = 4, u₄ = 0, v₅ = 3, u₂ = 2, v₄ = 5, u₃ = - 1, u₅ = 2, u₆ = - 3. Найдём оценки свободных клеток :

S₁₂ = 5 — (0 + 4) = 1

S₁₃ = 7 — (0 + 4) =3

S₁₄ = 9 — (0 + 3) = 6

S₂₁ = 4 — (2 + 1) = 1

S₂₃ = 4 — (2 + 4) = - 2

S₂₅ = 13 — (2 + 3) = 8

S₃₁ = 1 — (-1 + 1) = 1

S₃₂ = 5 — (-1 + 4) = 2

S₄₁ = 2 — (0 + 1) = 1

S₄₂ = 4 — (0 + 4) = 0

S₄₄ = 10 — (0 + 3) = 7

S₅₁ = 3 — (2 + 1) = 0

S₅₃ = 5 — (2 + 4) = - 1

S₅₄ = 6 — (2 + 3) = 1

S₅₅ = 4 — (2 + 3) = - 1

S₆₁ = 0 — (-3 + 1) = 2

S₆₂ = 0 — (-3 + 4) = - 1

S₆₃ = 0 — (-3 + 4) = 1

S₆₄ = 0 — (-3 + 3) = 0

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

Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой — клетка (2;

3) — и строим цикл, первая вершина которого находится в выбранной клетке, а остальные — в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «-», начиная со свободной клетки.

Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «-»): min (5; 20) = 5. Перераспределяем 5 единиц ресурса и получаем новый план поставок:

Определим потенциалы и оценки свободных клеток:

u₁ + v₁ = 1

u₁ + v₅ = 3

u₂ + v₂ = 6

u₂ + v₃ = 4

u₂ + v₄ = 7

u₃ + v₄ = 4

u₄ + v₃ = 2

u₄ + v₅ = 3

u₅ + v₂ = 2

u₆ + v₅ = 0

Пусть u₁ = 0, тогда v₁ = 1, v₂ = 4, v₃ = 2, u₄ = 0, v₅ = 3, u₂ = 2, v₄ = 5, u₃ = - 1, u₅ = - 2, u₆ = - 3

Найдём оценки свободных клеток :

S₁₂ = 5 — (0 + 4) = 1

S₁₃ = 7 — (0 + 2) =5

S₁₄ = 9 — (0 + 5) = 4

S₂₁ = 4 — (2 + 1) = 1

S₂₅ = 13 — (2 + 3) = 8

S₃₁ = 1 — (-1 + 1) = 1

S₃₂ = 5 — (-1 + 4) = 2

S₃₃ = 3 — (-1 + 2) = 2

S₄₁ = 2 — (0 + 1) = 1

S₄₂ = 4 — (0 + 4) = 0

S₄₄ = 10 — (0 + 5) = 5

S₅₁ = 3 — (-2 + 1) = 4

S₅₃ = 5 — (-2 + 2) = 5

S₅₄ = 6 — (-2 + 5) = 3

S₅₅ = 4 — (-2 + 3) = 3

S₆₁ = 0 — (-3 + 1) = 2

S₆₂ = 0 — (-3 + 4) = - 1

S₆₃ = 0 — (-3 + 2) = 1

S₆₄ = 0 — (-3 + 5) = - 2

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

Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой — клетка (6;

4) — и строим цикл, первая вершина которого находится в выбранной клетке, а остальные — в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «-», начиная со свободной клетки.

Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «-»): min (20; 20; 15) = 15. Перераспределяем 0 единиц ресурса и получаем новый план поставок:

ў

Определим потенциалы и оценки свободных клеток:

u₁ + v₁ = 1

u₁ + v₅ = 3

u₂ + v₂ = 6

u₂ + v₃ = 4

u₃ + v₄ = 4

u₄ + v₃ = 2

u₄ + v₅ = 3

u₅ + v₂ = 2

u₆ + v₄ = 0

u₆ + v₅ = 0

Пусть u₁ = 0, тогда v₁ = 1, v₂ = 4, v₃ = 2, u₄ = 0, v₅ = 3, u₂ = 2, v₄ = 3, u₃ = 1, u₅ = - 2, u₆ = - 3

Найдём оценки свободных клеток :

S₁₂ = 5 — (0 + 4) = 1

S₁₃ = 7 — (0 + 2) =5

S₁₄ = 9 — (0 + 4) = 5

S₂₁ = 4 — (2 + 1) = 1

S₂₄ = 7 — (2 + 4) = 1

S₂₅ = 13 — (2 + 3) = 8

S₃₁ = 1 — (1 + 1) = - 1

S₃₂ = 5 — (1 + 4) = 0

S₃₃ = 3 — (1 + 2) = 0

S₄₁ = 2 — (0 + 1) = 1

S₄₂ = 4 — (0 + 4) = 0

S₄₄ = 10 — (0 + 4) = 6

S₅₁ = 3 — (-2 + 1) = 4

S₅₃ = 5 — (-2 + 2) = 5

S₅₄ = 6 — (-2 + 4) = 4

S₅₅ = 4 — (-2 + 3) = 3

S₆₁ = 0 — (-3 + 1) = 2

S₆₂ = 0 — (-3 + 4) = - 1

S₆₃ = 0 — (-3 + 2) = 1

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

Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой — клетка (6;

2) — и строим цикл, первая вершина которого находится в выбранной клетке, а остальные — в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «-», начиная со свободной клетки.

Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «-»): min (0; 5;5) = 0. Перераспределяем 0 единиц ресурса и получаем новый план поставок:

Определим потенциалы и оценки свободных клеток:

u₁ + v₁ = 1

u₁ + v₅ = 3

u₂ + v₃ = 4

u₃ + v₄ = 4

u₄ + v₃ = 2

u₄ + v₅ = 3

u₅ + v₂ = 2

u₆ + v₂ = 0

u₆ + v₄ = 0

u₆ + v₅ = 0

Пусть u₁ = 0, тогда v₁ = 1, v₂ = 3, v₃ = 2, u₄ = 0, v₅ = 3, u₂ = 2, v₄ = 3, u₃ = 1, u₅ = 1, u₆ = - 3

Найдём оценки свободных клеток :

S₁₂ = 5 — (0 + 3) = 2

S₁₃ = 7 — (0 + 2) =5

S₁₄ = 9 — (0 + 3) = 6

S₂₁ = 4 — (2 + 1) = 1

S₂₂ = 6 — (2 + 3) = 1

S₂₄ = 7 — (2 + 3) = 2

S₂₅ = 13 — (2 + 3) = 8

S₃₁ = 1 — (1 + 1) = - 1

S₃₂ = 5 — (1 + 3) = 2

S₃₃ = 3 — (1 + 2) = 0

S₄₁ = 2 — (0 + 1) = 1

S₄₂ = 4 — (0 + 3) = 1

S₄₄ = 10 — (0 + 3) = 7

S₅₁ = 3 — (1 + 1) = 1

S₅₃ = 5 — (1 + 2) = 3

S₅₄ = 6 — (1 + 3) = 4

S₅₅ = 4 — (1 + 3) = 0

S₆₁ = 0 — (-3 + 1) = 2

S₆₃ = 0 — (-3 + 2) = 1

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

Для перераспределения поставок выбираем клетку с наибольшей по модулю отрицательной оценкой — клетка (3;

1) — и строим цикл, первая вершина которого находится в выбранной клетке, а остальные — в заполненных клетках. В вершинах цикла поочередно расставляем знаки «+» и «-», начиная со свободной клетки.

Определяем размер перераспределяемой поставки (минимальное из значений в клетках со знаком «-»): min (10; 10; 5) = 5. Перераспределяем 5 единиц ресурса и получаем новый план поставок:

Определим потенциалы и оценки свободных клеток:

u₁ + v₁ = 1

u₁ + v₅ = 3

u₂ + v₃ = 4

u₃ + v₁ = 1

u₃ + v₄ = 4

u₄ + v₃ = 2

u₄ + v₅ = 3

u₅ + v₂ = 2

u₆ + v₂ = 0

u₆ + v₄ = 0

Пусть u₁ = 0, тогда v₁ = 1, v₂ = 4, v₃ = 2, u₄ = 0, v₅ = 3, u₂ = 2, v₄ = 4, u₃ = 0, u₅ = - 2, u₆ = - 4

Найдём оценки свободных клеток :

S₁₂ = 5 — (0 + 2) = 3

S₁₄ = 9 — (0 + 4) = 5

S₂₁ = 4 — (2 + 1) = 1

S₂₂ = 6 — (2 + 2) = 2

S₂₄ = 7 — (2 + 4) = 1

S₂₅ = 13 — (2 + 3) = 8

S₃₁ = 1 — (0 + 1) = 0

S₃₂ = 5 — (0 + 2) = 3

S₃₃ = 3 — (0 + 2) = 1

S₄₁ = 2 — (0 + 1) = 1

S₄₂ = 4 — (0 + 2) = 2

S₄₄ = 10 — (0 + 4) = 6

S₅₁ = 3 — (-2 + 1) = 4

S₅₃ = 5 — (-2 + 2) = 5

S₅₄ = 6 — (-2 + 4) = 4

S₅₅ = 4 — (-2 + 3) = 3

S₆₁ = 0 — (-4 + 1) = 3

S₆₃ = 0 — (-4 + 2) = 2

S₆₅ = 0 — (-4 + 3) = 1

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

Список использованных источников

1. Акулич И. Л. Математическое программирование в примерах и задачах: учеб. пособие/ И. Л Акулич. — Москва: Высшая школа, 2009. — 347 с.

2. Балдин К. В. Математическое программирование: учебник / под ред. К. В. Балдин, Н. А. Брызгалов, А. В. Рукосуев. — Москва: Дашков и К, 2009. — 218 с.

3. Красс М. С. Математические методы и модели для магистрантов экономики: учеб. пособие для студентов/ М. С. Красс, Б. П. Чупрынов. — Москва: Высшая школа, 2010. — 496 с.

4. Математика для экономистов. Задачник: учеб. практ. пособие для студентов вузов / под ред.С. И. Макарова, М. В. Мищенко. — Москва: КноРус, 2008. — 358 с.