Читать «Краткий курс...» онлайн - страница 42

желательно получить при минимальных затратах валовых мощностей во всём множестве отраслей. Всё это в совокупности в формально-математических описаниях приводит к задаче линейного программирования:

Это — «задача продуктообмена», в которой необходимо найти векторы X и F , удовлетворяющие системе неравенств и критерию оптимума. Набор коэффициентов r₁ , ... , r_n в критерии оптимума позволяет некоторым образом «складывать» чугун и хлеб, производимые разными отраслями.

Это — обычная задача линейного программирования, одного из разделов линейной алгебры. Для её решения изпользуется стандартный алгоритм, называемый «симплекс метод», в различных модификациях известный с начала 1940-х годов.

Система неравенств типа (4) описывает в n-мерном пространстве выпуклый многогранник, аналогом коего в трехмерном пространстве может служить неподвижная картофелина после обрезки её ножом, перемещающимся по плоскостям, определяемым уравнениями (1) и дополняющими их неравенствами (4). Аргумент Z функции Min задает пакет (стопу) параллельных плоскостей, ориентация которого в пространстве (т.е. направление перпендикуляра ко всякой плоскости из пакета) определяется набором коэффициентов r₁ , ... , r_n . Оптимальное решение находится как общая точка, в которой одна из плоскостей пакета касается многогранника. Это подобно тому, как к лежащей на столе картофелине (после её обрезки) поднесли книгу, перемещая её параллельно самой себе: книга коснется хотя бы одной из вершин многогранника.

В линейном программировании эта образная очевидность характера перемещения книги относительно картофелины доказана математически строго для пространства n измерений. Алгоритм «симплекс метода» основан на том, что оптимальное решение задачи (4) лежит в одной из вершин n-мерного выпуклого многогранника и для его поиска необходимо последовательно пересмотреть значения функции Z в вершинах, перемещаясь из одной в другую вдоль его ребер в направлении убывания функции Z.

Практически в каждой книге, в которой разсматри­вается линейное программирование и его применение для решения практических задач, излагается теория двойственности линейного программирования. Её смысл сводится к тому, что каждой задаче линейного програм­мирования математически объективно соответствует двойственная ей задача, и оптимальные решения обеих задач взаимно связаны друг с другом. По отношению к задаче (4) двойственная к ней записывается так:

По отношению к экономике это — «задача рентабельности».

С начала 1950-х гг. известна теорема: если в опти­мальном решении прямой задачи неравенство № k вы­полняется как строгое, т.е. имеет место соотношение >, а не = (либо < , а не =), то в оптимальном решении двойственной задачи значение соответствующей переменной равно нулю.

Также с начала 1950-х гг. известны экономические интерпретации теории двойственности. Обычно в них в качестве прямой задачи разсматривается некая задача продуктообмена, в которой переменные интерпретиру­ются как объёмы ресурсов, вовлекаемых в производ­ственный процесс. Тогда в качестве двойственной выступает задача рентабельности, в которой перемен­ные интерпретируются как некие цены (цены «некие», поскольку не во всех интерпретациях это реальные цены рынка) соответствующих ресурсов. Такая интерпретация: в прямой задаче пере­менные — объёмы; в двойственной задаче переменные — некие цены, — стала традиционной, общеизвестной, общеприня­той. Смотри, на­при­мер, Ю.П.Зай­ченко “Изследование операций”, Киев, “Вища школа”, 1979 г. — рядовой учебник для вузов; “Математическая экономика на персо­нальном ком­пью­тере” под ред. М.Кубонива пер. с япон­ского, М., “Финансы и статистика”, 1991 г., японское изд. 1984 г. — лик­без-справочник.