Задание параметров задачи

Структура пособия

В главе 1 разобран пример решения задачи линейного программирования. В главе 2 на том же примере показано, как получить целочисленное решение этой задачи. Глава 3 посвящена решению транспортной задачи, а глава 4 — ре­шению задачи о назначениях. В приложение А вынесены общие правила рабо­ты с пакетом WinQSB, рассмотрены возникающие при этом трудности и пути их преодоления. В приложении Б говорится о том, как в Excel установить сред­ство Поиск решения, используемое в настоящем пособии. И наконец, в при­ложении В вы найдете перечень программ, используемых в настоящее время при выработке управленческих решений, с указанием источников их получе­ния.

Глава 1

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Пример

Требуется определить план выпуска четырех видов продукции, обеспечи­вающий максимальную прибыль от ее реализации. На изготовление этой про­дукции расходуются трудовые ресурсы, сырье и финансы. С учетом рыночного спроса и производственно-технологических возможностей заданы предельные границы выпуска каждого вида продукции. Эти границы, наличие и нормы рас­хода ресурсов, а также маржинальная прибыль (разность между выручкой и пе­ременными издержками) на единицу продукции приведены в таблице:

Ресурсы	Продукт 1	Продукт 2	Продукт 3	Продукт 4	Наличие
Труд
Сырье
Финансы
Прибыль
Нижн. гр.
Верхн. гр.		-

Обозначив количество выпускаемых изделий через.т_ь -ГгЛ, -<Ч, а целевую функцию (валовую маржинальную прибыль) — через F, построим математиче­скую модель задачи:

F— 70.V| + 6 O.Y 2 + 110x ₃ + 14 dr., —> max,

-v 1 + 2 .Y 2 + Д'з + 2.v,₍ <19, 3 < -t| < 5,

7.v 1 + 4 .V 2 + 5,v ₃ + 4 .V 4 <80, I < л,

5xi + 7.y₂ + 9xj + 8.v₄ < 100, 1 < л‘з < 3,

2 < X) < 4,

X|, x₂, -тз, X| > 0.

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

Решение с помощью пакета WinQSB

Запуск программы

Чтобы запустить программу для решения задач линейного и целочислен­ного программирования, щелкните кнопку Пуск, найдите программную группу WinQSB и выберите в ней программу Linear and Integer Programming.

Задание параметров задачи

Для ввода новой задачи нужно выбрать команду File ► New Problem. В открывшемся окне задаётся (рис. 1.1):

• Название задачи — в поле Problem Title.

• Количество переменных — в поле Number of Variables.

• Количество ограничений — в поле Number of Constraints (в нашей за­даче — 3, без учета граничных условий).

• Вариант оптимизации — максимизация (Maximization) или минимиза­ция (Minimization).

• Форма задачи — матричная (Spreadsheet Matrix Form) или стандарт­ная (Normal Model Form). Стандартная форма хотя и нагляднее, но более

• LP-ILP Problem Specification

• Problem Title: |npoi

• изводственныи план

• Number of Constraints:

• Number of Variables:

• Objective Criterion

• ii Maximization Г Minimization

• Data Entry Format

• '■ Spreadsheet Matrix Form Г Normal Model Form

• Default Variable Type

• ii Nonnegative continuous Г Nonnegative integer Г Binary (0.1)

• Г Unsigned/unrestricted

•:el Help

• Рис. 1.1. Ввод параметров решения задачи линейного программирования

• трудоемка для использования: в ней, кроме чисел (коэффициентов целевой функции и ограничений), требуется набирать на клавиатуре еще и буквы, обо­значающие переменные, а также знаки ограничений. Поэтому в дальнейшем мы будем использовать матричную форму. Однако после ввода данных эту форму легко изменить с помощью команды меню Format.

• ® Тип переменных — непрерывные неотрицательные (Nonnegative con­tinuous), целые неотрицательные (Nonnegative integer), двоичные (Binary (0,1)) или свободные, то есть произвольного знака (Unsigned/unrestricted).

• Ввод числовых данных

• Если выбрана матричная форма задачи, откроется окно с таблицей для ввода данных: коэффициентов целевой функции и ограничений, правых частей ограничений, а также для выбора их знаков. Вид этого окна после ввода данных показан на рис. 1.2.

• В строке Variable — установленные по умолчанию имена переменных. В строке Maximize (или Minimize) вводятся коэффициенты целевой функции. Обозначения С1, С2, СЗ и т. д. — это установленные по умолчанию названия ограничений. В соответствующих строках вводятся коэффициенты этих огра­ничений, за которыми следуют их знаки (в столбце Direction) и правые части (в

(к Производственный план

Variable —>	Х1	Х2	ХЗ	Х4	Direction R.	H. S.
Maximize
С1					<=
С2					<=
СЗ					<=
LowerBound
UpperBound		М
VariableType	Continuous	Continuous	Continuous	Continuous

Рис. 1.2. Задание коэффициентов целевой функции и ограничений

столбце R. Н. S.). Ниже— две строки для задания граничных ycMioBiiiiiLowerBound и UpperBound. В первой из них вводятся нижние грани­цы переменных, а во второй — верхние. По умолчанию все нижние границы равны 0, а все верхние равны бесконечности, которая обозначается большой ла­тинской буквой М. В строке Variable Туре указан заданный вами тип перемен­ных: Continuous (непрерывная), Integer (целая), Binary (двоичная) или Unre­stricted (свободная).

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

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

1.3. Перемещаться по таблице — с помощью клавиши Tab или клавиш со стрелками.

1.4. Выбрать ячейку таблицы — щелчком этой ячейки.

1.5. Редактировать содержимое ячейки таблицы — после щелчка голубого поля над таблицей. При этом выбранная ячейка выделится цветом и можно ре­дактировать ее содержимое.

1.6. Изменить знак ограничения — двойным щелчком знака. Если двойной щелчок выполнить несколько раз, знаки будут меняться циклически(<=,>=,=).

1.7. Изменить тип переменной — двойным щелчком слова, обозначающего тип этой переменной в строке Variable Туре. При нескольких двойных щелч­ках названия типов будут меняться Lununi4ecKii(Continuous, Integer, Binary, Unrestricted).

С помощью указанных далее команд меню Edit можно изменить следую­щие параметры задачи:

1.8. Название задачи — Problem Name.

1.9. Имена переменных — Variable Names.

1.10. Названия ограничений — Constraint Names.

1.11. Вариант оптимизации целевой функции — Objective Function Criterion (максимизация меняется на минимизацию или наоборот).

1.12. Количество ограничений — Insert a Constraint или Delete a Constraint (ограничения добавляются или удаляются).

1.13. Количество переменных —• Insert a Variable или Delete a Variable (пе­ременные добавляются или удаляются).

Воспользуемся этими командами, чтобы в нашей задаче ввести русские названия переменных и ограничений (рис. 1.3).

С помощью перечисленных далее команд меню Format могут быть изме­нены:

1.14. Форма задачи — Switch to Normal Model Form или Switch to Matrix Form (перейти в стандартную или матричную форму). Выбрав любую форму

к Производственный план

[Maximize Прод!

J70

Variable —>	Прод1	Прод2 j	ПродЗ	Прод4	Direction |R. H. S.
Maximize
Труд					<= 19
Сырье					<= 80
Финансы					<= 100
LowerBound
UpperBound		М
VariableType	Continuous	Continuous	Continuous	Continuous

Рис. 1.3. Измененные названия переменных и ограничений

задачи, вы можете построить задачу, двойственную к ней, с помощью команды Switch to Dual Form.

1.15. Формат чисел — Number.

1.16. Шрифт и ifeem — Font.

» Выравнивание — Alignment.

1.17. Высота строк — Row Height.

1.18. Ширина столбцов — Column Width.

Например, стандартная форма нашей задачи показана на рис. 1.4.

Вниманне! После ввода данных задачи не забудьте сохранить ее с помо­щью команды File ► Save Problem As.