симплекс- метод решения задачи

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

Таблица №4: Симплекс- таблица нулевой итерации.

Базис

План

х1

х2

х3

х4

х5

х6

Контроль

х4

x5

x6

-5

-5

-6

-16

Вычислим отношение элементов столбцов плана и х3 в каждой строке:

Получим разрешающие: строка №3 (отношение b3 / a33 наименьшее), столбец №3 (наименьшее a 3 = -6), ключевой элемент l=4.

Произведём пересчёт всех элементов таблицы к их значениям следующей (первой) итерации по формулам (9), (10) согласно вышеописанному алгоритму с учётом определённых здесь ключевых столбца и строки. При этом все элементы третьей (ключевой) строки нужно просто разделить на выделенный ключевой элемент 4, а процедура пересчёта элементов неключевых строк производится с участием элементов старой симплекс- таблицы, стоящих в вершинах прямоугольника, по одной из диагоналей которого расположены пересчитываемый и ключевой элементы. Эту процедуру иллюстрирует рис. 8.

Результат – симплекс- таблица первой и остальных итераций – приведён в табл.5. Второй столбец контрольных сумм получен простым суммированием по строке, первый – по формулам преобразования элементов.

Таблица №5: Симплекс- таблицы остальных итераций.

Базис	План	х1	х2	х3	х4	х5	х6	Контроль	Итерация №1
х4							-2
x5		1,25	-1,25				-0,75	125,25	125,25
x3		0,25	0,75				0,25	227,25	227,25
		-3,5	-0,5				1,5	1347,5	1347,5
		Получим разрешающие: строка №2 (отношение b2 / a21 наименьшее), столбец №1 (наименьшее a 1 = -3,5), ключевой элемент l=1,25.
Базис	План	х1	х2	х3	х4	х5	х6	Контроль	Итерация №2
х4						-1,6	-0,8	400,6	400,6
x1			-1			0,8	-0,6	100,2	100,2
x3						-0,2	0,4	202,2	202,2
			-4			2,8	-0,6	1698,2	1698,2
		Получим разрешающие: строка №3 (отношение b3 / a32 наименьшее), столбец №2 (наименьшее a 1 = -4), ключевой элемент l=1.
-100
Базис	План	х1	х2	х3	х4	х5	х6	Контроль	Итерация №3
х4				-2		-1,2	-1,6	-3,8	-3,8
x1						0,6	-0,2	302,4	302,4
x2						-0,2	0,4	202,2	202,2

На третьей итерации достигается оптимальный план, т.к. все элементы индексной строки в нём положительны. Значения ненулевых в нём переменных (базисных) находятся в столбце плана, т.е. x₁=300, x₂=200, а переменная x₃ в состав базисных в оптимальном плане не входит, т.е. она является свободной: x₃=0. Этот результат был получен здесь в пункте 3). Однако, в отличие от графического метода, симплекс- таблица, как уже было отмечено, содержит много дополнительных полезных сведений, в частности, из того, что в базисе оптимального плана присутствует переменная x₄ - остаток ресурса первого типа, следует, что этот ресурс имеется в избытке, а остальные ресурсы в этом плане дефицитны. Однако значение этого остатка из столбца плана равно 0, а значит и первый ресурс на самом деле расходуется полностью, однако увеличение его запаса не приведёт к изменению оптимального плана, о чём свидетельствует равенство нулю его двойственной оценки из индексной строки. Выполнены также и проверочные свойства симплекс- таблицы – одинаковы сосчитанные двумя способами все элементы столбцов контрольных сумм; не равен нулю третий элемент индексной строки, соответствующий невыгодному третьему виду услуги, и не равны нулю пятый и шестой элементы индексной строки, соответствующие дефицитным ресурсам второго и третьего видов. Т.о. весь процесс итераций произведен без ошибок.

Двойственная задача

Для ответа на третий вопрос задания сформулируем задачу линейного программирования, двойственную к исходной. Для этого получим расширенную матрицу (4.1) исходной задачи (11):

Теперь транспонируем её:

Составим двойственную к (11) задачу, как предложено выше в пункте “Элементы теории двойственности”, как задачу на минимизацию с ограничениями в форме неравенств со знаком “больше или равно” и вышеприведённой транспонированной расширенной матрицей:

(15)

Получим её решение из пункта оптимальной симплекс- таблицы пункта 5), пользуясь тем, что z_i= a _i+n, т.е. z₁= a ₄=0, z₂= a ₅=2, z₃= a ₆=1. Дадим теперь экономическую интерпретацию переменных и ограничений двойственной задачи (15). В полученном оптимальном плане значения двойственных (теневых) цен показывают, что для продолжения неубыточного процесса оказания услуг можно закупать дефицитные в полученном плане ресурсы второго и третьего типа по ценам, не превышающим 2 и 1 руб. за штуку, соответственно, а нелимитирующий ресурс первого типа, вообще говоря, при такой системе оценок закупаться не должен. Однако он в оптимальном плане израсходован полностью. Это означает, что при дополнительной закупке дефицитных ресурсов в новом плане первый ресурс станет дефицитным, однако прибыль в новом плане всё же будет положительной. На вопрос, до каких пределов имеет смысл увеличивать объёмы дефицитных ресурсов, как раз и отвечает решение параметрической задачи. Из пункта 4) решения следует, что объём ресурса второго типа имеет смысл увеличивать до 1200 шт., т.е. на 400 шт. (но только этого ресурса, без изменения объёмов других ресурсов!). С другой стороны, если сравнить приростной коэффициент эффективности вовлечения второго ресурса из пункта 4) со значением двойственной оценки этого ресурса, то, как и отмечалось выше, они равны в точке оптимального плана задачи (11). Экономический смысл ограничений (15) заключён в том, что при убыточном процессе оказания услуг, условия которого как раз и определяются в двойственной задаче, дополнительные издержки при оказании этих услуг по закупке дефицитных ресурсов (левые части неравенств второй – четвёртой строк (15)) должны быть не меньше прибыли, при этом извлекаемой.

Оформление отчёта

Отчет о выполнении задания должен содержать титульный лист, формулировку задачи с конкретными числовыми данными и пункты выполнения задания, аналогичные вышеизложенным в §II.2. При выполнении пунктов 3) - 6), должны быть приведены вычисления, если, конечно, работа не была выполнена с использованием компьютерных средств. Если были использованы компьютерные программы, то необходимо указать, какие. При этом отчёт должен быть представлен в электронном виде в формате того приложения, в котором были произведены вычисления.

3. рекомендации по использованию компьютерного обеспечения

При выполнении задания рекомендуется пользоваться компьютерными приложениями типа математических пакетов общего назначения или крупноформатных электронных таблиц. Отчет о выполнении задания может быть оформлен в них целиком в электронном виде.

Перед изложением конкретных рекомендаций в данном разделе необходимо изложить некоторые исторические сведения. Наиболее широко компьютерные средства использовались при решении задач класса линейного программирования на том этапе развития ЭВМ в нашей стране, когда основным вычислительным инструментом являлись большие машины коллективного пользования (70-ые – 80-ые года ХХ века). Среди распространённых тогда ЭВМ наиболее выделяются в этом отношении машины единой серии (ЕС: ЕС-1033, … ЕС-1066). Связано это с тем, что на всех них была легально установлена единая русифицированная система виртуальных машин (СВМ) разработки фирмы IBM, в состав обязательно поставляемых системных библиотек которой входила математическая библиотека с широким набором операций группы математического программирования, хотя многие организации имели и собственные программные разработки в этой области. Лёгкость применения машин этого типа в экономических расчётах была обусловлена структурой штата обслуживающего персонала этих ЭВМ, в который входил программист, владеющий вышеупомянутым программным обеспечением. По- этому даже в случае полного отсутствия каких- либо навыков работы на ЭВМ у конкретного экономиста- практика была возможность с помощью программиста провести необходимые вычисления, поскольку именно программист производил процедуру математической формализации задачи, адаптации общего приложения к конкретному случаю и проводил вычисления. С заменой ЭВМ этого класса на персональные компьютеры, работавшие под управлением операционных систем семейства DOS фирмы Microsoft (конец 80-х - начало 90-ых годов ХХ века), ситуация с возможностью их применения конкретным экономистом для случая решения задач оптимизационного класса, и в том числе задач ЛП, существенно ухудшилась. Причин тому две. Во- первых, экономист- практик теперь чаще всего не имел возможности получить квалифицированную консультацию по вопросам формализации задачи и применения программных продуктов для ПК без существенных дополнительных расходов по оплате этих консультаций. Во- вторых, программные продукты, способные производить вычисления такого рода, уже не входили в состав операционной системы и распространялись отдельно, причём были весьма примитивными. Так что возникала задача поиска программы, способной проводить необходимые вычисления, причём с доступным неспециалисту в области программирования интерфейсом. Среди программ этой группы стоит упомянуть пакет EURECA, в котором алгоритм решения задач оптимизации с ограничениями в форме неравенств (частным случаем которого является задача ЛП) присутствовал и имел достаточно простой интерфейс. Следующий шаг – переход к ПК под управлением операционных систем группы Windows – привёл к новому осложнению ситуации. Теперь знание компьютерных средств является необходимым требованием к любому специалисту, а специалисту экономического профиля – в первую очередь. В настоящее время основные офисные программные средства типа пакета MSOffice в ряде случаев содержат готовые алгоритмы решения задач оптимизации. Однако интерфейс этих алгоритмов всё же нельзя назвать достаточно “прозрачным”. Так, в приложении Excel из пакета MSOffice присутствует общая процедура решения задач линейного, выпуклого, нелинейного и частично- целочисленного программирования. Вид её диалоговых окон при решении задачи ЛП приведён на рис.9,10. При этом она содержит ряд обязательных параметров, смысл которых в конкретных задачах не всегда ясен. кроме того, использование общих алгоритмов в конкретных задачах не всегда рационально, например в целочисленном программировании, где применение реализованного в приложении Solver общего метода ветвей и границ (алгоритма Гомори) может привести к полному перебору или даже превышению над полным перебором в случае задачи с булевыми переменными. Применение этой автоматизированной процедуры к решению задачи ЛП можно найти на последнем рабочем листе в книге примера выполнения задания [1] в файле LinProgr.xls. С другой стороны, такие приложения, как крупноформатные электронные таблицы (КЭТ), имеют интерфейс, в котором многие алгоритмы оптимизации могут быть весьма просто реализованы самим пользователем, если, конечно, они ему знакомы. Прекрасный тому пример – табличный алгоритм симплекс- метода. Для случая КЭТ он будет здесь рассмотрен ниже. В случае математических пакетов общего назначения типа MathCad-а существуют определённые трудности. Во- первых, использование подобных программ в этом случае возможно при наличии в них соответствующих процедур, которые обычно не входят в базовый комплект поставки и распространяются отдельно. Во- вторых, интерфейс этих процедур требует от пользователя минимального знакомства с языками программирования, в частности с понятием подпрограммы.

разберём теперь случай применения КЭТ, в частности КЭТ Excel из пакета MSOffice для реализации алгоритма симплекс- метода. Возможны, конечно, и другие варианты, однако здесь мы ограничимся только наиболее распространённым в настоящее время офисным вычислительным средством. При этом для понимания нижеизложенного необходимо знание основных понятий КЭТ: рабочий лист, ячейка листа, её адрес, слой значения и слой формул ячейки, а также понятие об основных встроенных функциях и групповых операциях КЭТ. Пример решения всей вышеприведённой задачи в этой программе находится в вышеупомянутом файле LinProgr.xls. Там, на листе симплекс- метода и реализована вышеописанная процедура. Удобство применения КЭТ в этой ситуации заключается в наличии двух типов адресов ячеек листа КЭТ, используемых при проведении вычислений, т.е. написании формул. Это абсолютный, не изменяемый при копировании адрес строки (число) или столбца (буква), признаком которого является наличие перед адресом символа $. Второй тип адреса – относительный -, применяемый программой по умолчанию, при копировании формулы изменяется на столько строк и столбцов, на сколько эта формула была перемещена в листе от своего исходного положения. Для симплекс- метода это позволяет в каждой симплекс- таблице писать формулы только для двух ячеек – первой ячейки разрешающей строки и первой ячейки любой другой строки. После этого путём фиксации в этих формулах адреса ключевых строки и столбца с последующим копированием формул во всю таблицу сразу получается полная таблица новой итерации. Процедура построения самих формул выглядит с использованием “мыши” довольно просто: в рассчитываемую ячейку вводится знак “=”, после чего формула строится простым указанием мышью (со щелчком на выбранной ячейке) на участвующие в вычислениях ячейки предыдущей итерации (см. рис.8) с введением между

адресами ячеек знаков необходимых арифметических операций “-“, “*”, “/” и, как было выше отмечено, символа $ перед адресами ключевых столбца и строки (см. рис.11), с последующим копированием формул в строку. При вычислении столбца контрольных сумм можно воспользоваться групповой операцией суммирования по интервалу СУММ(интервал). область интервала – суммируемые числовые ячейки строки симплекс- таблицы – выделяется в построителе формул с помощью “мыши”. Для более тесного ознакомления с вышеизложенным необходимо войти в вышеупомянутый лист и проанализировать все формулы, по которым произведены вычисления элементов таблиц. На этом позвольте здесь откланяться, а подробнее ознакомиться с процедурами симплекс- метода в КЭТ можно на практических и семинарских занятиях или консультациях по дисциплине “Математическое моделирование в экономике”.