Полная версия

Главная arrow Финансы

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

РЕШЕНИЕ НА СТАТИЧЕСКОЙ ОПТИМИЗАЦИОННОЙ МОДЕЛИ С ОДНОКРИТЕРИАЛЬНОЙ ЦЕЛЕВОЙ ФУНКЦИЕЙ

Первая модель из предыдущего параграфа (2.17)-(2.25) представляет собой задачу линейного программирования, которую можно решить стандартными методами. Однако в условиях этой задачи имеется соотношение, позволяющее решить ее значительно проще. Это соотношение (2.20), отражающее факт выпуска конечной продукции как цели проекта в заданных пропорциях. По сути дела, это соотношение означает, что в качестве целевой функции рассматривается не вектор, а скаляр — общий объем производства конечной продукции как цели проекта.

Задача такого вида, но без уравнений (2.18)—(2.19) и ограничения

(2.23)-(2.24) рассматривалось ранее в работах [131, 139, 150-151, 235], где также приводится их решение. В работах [131, 139] решение задачи этого типа дается без подробного его обоснования, а в [151, 235] приводится строгое математическое доказательство. В данной работе разработан альтернативный способ получения решения и получено его доказательство. Кроме того, предлагаемый способ решения ускоряет процесс решения и позволяет устранять несовместности исходных данных на основе анализа экономического содержания элементов решения. Решение получено методом декомпозиции оптимизационной задачи на подзадачи и последующего синтеза полученных решений подзадач.

Условие (2.20) позволяет декомпозировать данную оптимизационную задачу на несколько подзадач, решение каждой из них можно получить в виде аналитических формульных зависимостей, на основе которых затем можно синтезировать общее решение. В состав декомпозированных задач входят три подзадачи, каждая включает одно из ограничений на переменные. Первая подзадача включает ограничение только на производительность линий предприятий. Вторая содержит ограничение только на объемы затрат импортных товаров и товаров внешних предприятий. Третья включает ограничение только на количество занятых работников. Целевой функцией каждой из этих задач является скалярная величина — объем производства конечной продукции как цели проекта, который требуется максимизировать.

Запишем ограничения этих подзадач в преобразованной форме. Для получения преобразованного ограничения первой подзадачи подставим в уравнение (2.17) вместо вектора у его выражение из уравнения (2.20). После этого решаем полученное уравнение относительно вектора х • Это решение имеет вид

где В — матрица обратная к матрице I -А;

/ — единичная диагональная матрица.

Затем подставляем это выражение для вектора х в неравенство (2.22), выражающее ограничение на производительность линии предприятия. Тогда это неравенство примет форму

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

Все численные значения переменных в правой части системы этих неравенств имеют фиксированные значения, поэтому вся правая часть — это числа. Обозначим эти числа через а;-. Запишем предыдущие неравенства в виде

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

Содержательный смысл числа а,- — это тот возможный уровень

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

Исходя из вышесказанного, можно сформулировать содержательный смысл последней формулы. Решение первой подзадачи — максимальный общий объем производства конечной продукции а — определяется синтезом N частных задач и представляет собой минимальный объем производства конечной продукции, получаемый из решения этих N частных задач, поскольку только этот объем обеспечивается совместно производительностями линий предприятий, т.е. заданными их ограничениями. Докажем теперь строго, что решением первой подзадачи является именно величина а* ^.

Обозначим через / индекс предприятия, для которого величина a,-, i = 1,N имеет минимальное значение. Проведем это доказательство от противного. Пусть решением первой подзадачи будет любое число, не равное ау, например число а^, большее, чем ау. Следует

заметить, что этим числом не может быть число меньшее, чем ау,

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

Вычислим теперь величину валового производства предприятия / при этом объеме производства конечной продукции (обозначим Ху), которая определяется по формуле

где bjj — элемент матрицы В .

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

Сравнивая правые части выражений Х/ и ру, видим, что они отличаются только одним слагаемым, где стоят величины ау и а^, причем ау <а^. Поэтому в силу линейности выражений х/ и ру из них следует, что Ху > ру. Это неравенство противоречит тому, что выпуск производственной линии предприятия должен быть меньше или равен его максимальной производительности. Поскольку в качестве а^ можно взять любое число, большее ау, то полученное противоречие доказывает наше утверждение.

Запишем теперь ограничение второй подзадачи в преобразованной форме. Для этого подставим выражение для вектора х из (2.30) в уравнение (2.18), которое примет вид

Затем подставим это выражение для вектора z в неравенство

(2.23), которое будет выглядеть так:

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

Обозначим числа в правой части этих неравенств в виде а,-, Тогда аналогично первой подзадаче максимальный объем производства конечной продукции во второй подзадаче, обозначаемый q(2), определяется формулой

Содержательный смысл величин ау, — это максимальный объем производства конечной продукции а в одной из М задач, на которые декомпозируется вторая подзадача. Каждая из этих задач включает только одно из ограничений на объемы потребления импортных товаров и товаров внешних предприятий /, / = 1,м ? Как и в первой подзадаче, в силу линейности уравнений можно аналогично доказать, что значение а^ действительно максимальное и не может быть увеличено.

Запишем теперь условие третьей подзадачи, включающей только ограничение на количество занятых работников. Для этого подставим в уравнение (2.19) выражение (2.30) для вектора х • В результате получим уравнение

Заменим теперь в этом уравнении вектор у на его выражение из уравнения (2.20) и подставим полученное выражение для величины h в неравенство (2.24), выражающее ограничение на количество занятых работников, которое будет выглядеть так:

Как и в предыдущих подзадачах, после выполнения преобразований с этим неравенством, получаем выражение для интервала возможных значений искомой величины а в следующем виде

В данной подзадаче имеется одно скалярное ограничение, в силу чего максимальный объем производства конечной продукции, обозначаемый , будет равен правой части предыдущего неравенства, обозначаемой aN+M+1:

Действительно, если допустить, что максимальное значение больше этой величины, то будет нарушено неравенство (2.31). Если допустить, что максимальное значение меньше этой величины, то сразу получаем противоречие, так как легко найти большее значение, удовлетворяющее условию данной подзадачи, например саму величину aN+M+1.

Содержательный смысл величины а^ — это максимальный объем производства конечной продукции а, который может быть получен, если нет ограничений на производительность линий предприятий и на потребление товаров неконкурирующего импорта, а ограничивающим является только общее количество занятых работников.

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

*

а, как решение общей задачи, обозначаемый а , определяется по формуле

или как синтез решений задач, на которые декомпозируются частные подзадачи

Учитывая доказательства решений подзадач, легко показать, что ?

величина а максимальная в решаемой задаче. Действительно, пусть *

а = а/, где / — индекс, на котором реализовалось максимальное значение. Допустим теперь, что эта величина не максимальная. При этом значение, меньшее, чем а/, не может быть, так как можно найти

большее значение, удовлетворяющее всем условиям задачи, например значение ау.

Пусть искомое значение больше ау. Индекс / соответствует определенной подзадаче. Выше было показано, что решением любой подзадачи является минимальное значение из величин ау. Поэтому получаем противоречие, что решением может быть значение, большее минимальной из величин ау. Доказательство получено.

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

Основой для устранения несовместности является требование, чтобы величины ay, i = 1 ,N + М + 1 были неотрицательными. Если какая-либо из этих величин имеет отрицательное значение, то это означает, что соответствующее ограничение является несовместным.

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>