Рис. 12.28.

5. Показать, что в матрице, имеющей несколько нулевых и несколько ненулевых элементов, минимальное число линий (т. е. строк и столбцов), содержащих все нули, равно максимальному числу нулей, расположенных в разных строках и разных столбцах. (Этот результат известен как теорема Кёнига.)

6. Найти решение ЗН с минимальной стоимостью, где матрица С равна

7. Определим минимаксную ЗН как задачу нахождения такого назначения с матрицей С, чтобы максимальная стоимость элемента этого назначения была минимальной. Решить минимаксную ЗН для матрицы С из задачи 6.

8. Решить нижеприведенную транспортную задачу, где (4 X X 5)-матрица является матрицей стоимостей С, вектор-столбец является вектором снабжения (предложений), а вектор-строка - вектором спроса (потребностей).

{Замечание. Свести задачу к эквивалентной задаче, в которой сумма потребностей равна сумме предложений.)

9. Рассмотрим транспортную задачу с матрицей стоимостей С, приведенной ниже, и векторами снабжения и потребностей

[ ,] = [10.15.20] J =[5,12,13,15]

Оптимальное решение этой задачи дается перевозками, показанными в верхних левых углах следующей матрицы: 12 3 4

KJ=2 3

8. Список литературы

1. Balinski М. L. (1965), Integer programming; Methods, uses, computations, Man. ScL, 12, p. 253.

2. Balinski M. L. (1969), Labelling to obtain a maximum matching. Combinatorial Math, and its Appl., Bose and Bowling, Eds., Univ. of North Carolina Press, p. 585.

3. Balinski M. L. (1970), On maximum matching, minimum covering and their connections, Proc. Princeton Symp. on Math. Programming, Kahn, Ed., Princeton Univ. Press, p. 303.

4. Balinski M. L., Gomory R. E. (1964), A primal method for the assignment and transportation problems, Man. Sci., 10, p. 578.

5. Берж К. (1962), Теория графов и ее применения, ИЛ, М.

6. Bourgeois F., Lassalle J. С. (1971), Algorithm 415 - Algorithm for the assignment problem. Comm. of ACM, 14, p. 805.

7. Bourgeois F., Lassalle J. C. (1971), An extension of the Munkres algorithm for the assignment problem to rectangular matrices. Comm. of ACM, 14, p. 802.

8. Dantzig G. B. (1963), Linear programming and extensions, Princeton Univ. Press, Princeton, New Jersey.

9. Desler J. F. Hakimi S. L. (1969), A graph-theoretic approach to a class of integer programming problems. Ops. Res., 17, p. 1017.

10. Edmonds J. (1965), Paths, trees and flowers, Canadian Math. J., 17, p. 449.

11. Edmonds J. (1965), Maximum matching and a polyhedron with 0-1 vertices, /. of Res., Nat. Bur. of Stand., 69B, p. 125.

12. Edmonds J. (1967), An introduction to matching. Summer seminar on mathematics of the decision sciences, Stanford University.

13. Edmonds J., Johnson E. L. (1970), Matching: A well solved class of integer linear programs, Proc. Calgary Intl. Conf. on Combinatorial Structures and their Appl., Gordon and Breach, New York, p. 89.

14. Edmonds J. (1962), Covers and packings in a family of sets. Bull. Amer. Math. Soc, 68, p. 494.

15. Egervary E. (1953), On combinatorial properties of matrices, translated by H. W. Kuhn, Office of Naval Research Logistics Project Report, Dept. Math., Princeton University.

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

1агр = [10, 15, 21],

[р,]2 = [6, 12, 13, 15].

Оптимальное решение дается перевозками, показанными в нижних правых углах вышеприведенной матрицы Иг]. Стоимость этого решения равна 239, а величина транспортируемых грузов - 46 единицам.

Объяснить, почему для данной матрицы стоимостей можно транспортировать большую величину грузов при меньшей полной стоимости, и особенно обратить внимание на то, что дуги, вдоль которых производится перевозка, остаются прежними (см. [28]).