Алгебра симплекс-метода

из "Моделирование производственно-инвестиционной деятельности фирмы "

Последующий материал, посвященный анализу оптимального решения в задаче Канторовича, существенно использует симплекс-процедуру перехода от начального допустимого базисного решения к оптимальному решению. В связи с этим необходимо напомнить табличный метод нахождения оптимального решения в задаче линейного программирования. Среди множества реализаций симплекс-процедуры выберем ту, которая, во-первых, в явном виде разделяет базисные и свободные переменные и позволяет в последней симплекс-таблице выделить так называемую матрицу эффективности, а во-вторых, хорошо приспособлена для решения на ЭВМ. [c.65]
Задача линейного программирования (2.7), (2.10), (2.9) с дополнительными ограничениями на неотрицательность переменных tt имеет размерность я + т. При этом число базисных переменных в случае линейной независимости системы ограничений (2.8) равно числу ограничений, т. е. т, а число свободных переменных совпадает с числом неизвестных в линейной форме (2.7), т. е. равно п. Обозначим через с значение целевой функции в форме (2.7). [c.67]
В матрице (2.13) коэффициенты первой строки совпадают с коэффициентами линейной формы (2.11) =0, ат=—р .а0=—рп, а коэффициенты первого столбца — с коэффициентами правых час тей ограничений (2.8) д,0= Ь ,. .., ai0 = bfl. .., а = Ьт. [c.68]
Пусть объем фактора L равен 8 единицам, а фактора К — 4 единицам. В этом случае в ходе решения соответствующей оптимизационной задачи осуществляется выбор интенсивностей использования технологических способов Р , Р2 и Рг, при которых достигается наибольший выпуск товарной продукции при условии использования факторов труд и капитал в объеме, не превосходящем их наличного количества (8 4). [c.72]
Приведем краткое решение задачи (2.14)— (2.17). [c.72]
Так как решаемая задача — задача на максимум, то соотношения (2.20) показывают, что начальное базисное решение является допустимым, но не оптимальным (коэффициенты при хр х2 и х3 в выражении для с не являются неотрицательными числами). [c.72]
В ходе последовательного преобразования таблиц коэффициентов, используя симплекс-процедуру, получим оптимальное решение задачи (2.14), (2.18), (2.19), (2.17), исходя из начального допустимого решения (2.20). [c.72]
Приведем последнюю симплекс-таблицу коэффициентов, да--, ющую оптимальное решение задачи в этом случае. [c.74]
Оптимальному состоянию системы соответствует выпуск товарной продукции с° = 6 (уменьшился на 3,6 ед.). Наряду с первым производственным способом неэффективным оказывается и второй (х2=0) — капиталоемкий. Интенсивность третьего производственного способа соответствует наличному объему капитала. При этом не-, использованный остаток фактора труд равен 2 (t=2). Таким обра-л зом, фактор является дефицитным, а фактор L — недефицитным. [c.74]
Если предприятие ограничивается одним производственным способом, требующим больших затрат некоторого ресурса, запасы которого ограниченны, то теневая цена этого ресурса будет велика. Однако установленные в соответствии с этим способом производства теневые цены не будут наилучшими, так как введение других производственных способов позволяет более рационально использовать все запасы ресурсов. Например, если в модели из предыдущего пункта ограничиться способом Р2, то теневая цена капитала будет очень высокой, а теневая цена труда крайне низкой (при двух единицах капитала его останется 7 единиц). Если же наряду с Р2 ввести способ производства Рр то теневая цена капитала останется прежней, а теневая цена труда повысится (при двух единицах капитала его останется 2 единицы). [c.75]
что оптимальному состоянию производственной системы в модели (2.7)— (2.9) соответствует вектор оптимальных теневых цен наличного запаса ресурсов. Оптимальные теневые цены называют объективно обусловленными оценками (о.о.о.), или оптимальными оценками, или двойственными оценками ресурсов. [c.75]
Для определения о.о.о. ресурсов составим самостоятельную задачу линейного программирования. [c.75]
Отметим, что любое преобразование матрицы (2.24) по правилам симплекс-процедуры приводит к новой матрице, которая описывает новое допустимое (или оптимальное) решение как прямой, так и двойственной задачи. [c.78]
Дадим краткую экономическую интерпретацию соотношений (2.27) — первая теорема двойственности и (2.28) — вторая теорема двойственности. Более подробно экономическое содержание двойственных оценок излагается в главе 3. [c.78]
Вернемся к модели (1.1)— (1.6) из 1-й главы и методом, изложенным в главе 2, получим ее оптимальное решение. Пусть х, и х2 — искомые объемы добычи соответственно торфа и угля х,, х4, х5 — неиспользованные остатки оборотных средств предприятия, электроэнергии и трудовых ресурсов. Для удобства записи и последующих вычислений все коэффициенты матрицы ограничений увеличим в тысячу раз. Таким образом, ресурсы теперь измеряются в тыс.(руб., кВт-ч, чел.-ч, т). [c.81]
На первом шаге (табл. 3.1(а)) наиболее выгоден план добычи угля, что обусловливает его введение в базис (план производства) следующего шага (см. табл. 3.1(6)). Какое же из первоначальных базисных переменных он заменит Для ответа на этот вопрос почленно разделим первый столбец на столбец xv т. е. неиспользованные остатки ресурсов делим на коэффициенты замены. Так как в плане первого шага ресурсы не используются в их полном объеме, то каждый из элементов частных покажет, какое количество угля можно добыть за счет полного использования соответствующего ресурса. Но добыча угля требует одновременной затраты всех трех ресурсов, и исчерпание какого-либо одного ресурса сделает дальнейшую добычу невозможной. Таким образом, максимальная добыча угля возможна лишь в размере 40 тыс. т, а не 180 или 128. При добыче 40 тыс. т угля будет полностью истрачен фонд оборотных средств в размере 20 тыс. руб., а его неиспользованный остаток х3 станет нулевым. [c.83]

Вернуться к основной статье