ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Поскольку слева всегда строки, а справа столбец, результат вектор-столбец, число элементов которого равно числу строк матрицы-сомножителя (см. приложение 3). В нашем примере выделены ячейки 13:15.
Шаг 2. На панели инструментов (под полосой меню Файл, Правка, Вид и т. д.) щелкнуть левой кнопкой мыши по кнопке Вставка функции. Откроется диалог Мастер функций шаг 1 из 2, как показано на рис.
П4.2.
Шаг 3. В левом окне диалога Категория выбрать Математические и щелкнуть по этой строке левой кнопкой мыши. В левом окне найти и выделить МУМНОЖ. После этого нажать ОК. Появится диалог МУМНОЖ, как это показано на рис.
П4.3.
Шаг 4. В окне Массив I надо указать адрес матрицы, левого сомножителя. Это можно сделать, набрав адрес с клавиатуры, но лучше сделать это с помощью мыши.
Для этого надо установить курсор в окне Массив 1 и мышью выделить ячейки, занимаемые массивом, т. е. установить курсор в левом верхнем углу матрицы и, нажимая левую кнопку мыши, протащить его до правого нижнего угла массива. Если диалог заслоняет матрицу, его можно сдвинуть, используя мышь: поставить на него курсор (но не на кнопку и не на окно), нажать левую кнопку мыши и, не отпуская ее, перетащить диалог в нужное место. Затем таким же способом надо в окно Массив 2 ввести адрес второго сомножителя.
После этого, нажимая Shift и Ctrl, нажать Enter. В ячейках 13:15 появится результат умножения матрицы на вектор, как это
Рис. П4.2. Диалог Мастер функций шаг 1 из 2
Рис. П4.3. Диалог мумнож
Рис. П4.4. Умножение матрицы на вектор
Аналогичным образом выполняется умножение матрицы на матрицу.
Сложение векторов
Можно, разумеется, складывать векторы поэлементно, введя в каждую ячейку массива, в котором хранится сумма, соответствующую формулу, например складывая векторы А и У на рис. П4.5, ввести в ячейку Н2 формулу =B2+D2, в ячейку НЗ : =B3+D3 и т. д. Однако и в этом случае удобнее работат ь с массивом как с цельным объектом. Для этого надо:
Шаг 1. Мышью выделить ячейки под сумму векторов (ячейки F2 : F5 на рис. П4.5).
Шаг 2. Набрать (с клавиатуры) знак равенства.
Шаг 3. Выделить мышью ячейки В2 : В5.
Шаг 4. Набрать (с клавиатуры) знак плюс.
Рис. П4.5. Сложение векторов
Шаг 6. Нажимая Shift и Ctrl, нажать Enter.
Транспонирование массивов
Транспонирование массива производится так:
Шаг і. Мышью выделить ячейки под результат транспонирования.
Шаг 2. Вызвать функцию ТРАНСП. Ее можно найти в категории
МАТЕМАТИЧЕСКИЕ или ПОЛНЫЙ АЛФАВИТНЫЙ ПЕРЕЧЕНЬ
либо ввести с клавиатуры.
Шаг 3. Ввести в окно диалога функции ТРАНСП адрес транспонируемого массива.
Шаг 4. Нажимая Shift и Ctrl, нажать Enter.
Пример приведен на рис. П2.6.
Рис. П4.6. Транспонирование массивов
- При умножении: слева всегда строка, справа всегда столбец.
- При сложении: строка складывается со строкой, столбец со столбцом.
- Для превращения столбца в строку или строки в столбец используется операция транспонирования (функция ТРАНСП () в Ехеі).
- Для правильного выполнения операции над массивами Enter или ОК нажимаются только при отжатых клавишах Shift и Ctrl.
Приложение 5ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Линейное программирование частный случай общей задачи оптимизации при наличии ограничений. Многие задачи планирования производственно-коммерческой деятельности предприятия сводятся к задачам линейного программирования.
Задача линейного программирования на максимум в стандартной форме формулируется следующим образом.
Найти числа .с,,такие, что
і = 1, ...,m, j = I.....n.
Например:
2.v, -x2 = max, -4x, + x2 2,
X, -x2 1,
2x, + x2 5, Xy*x7 --
В матричных обозначениях эта задача выглядит следующим образом:
сх = шах.
(5)
АхЬ, х 0.
Здесь с n-мерный вектор-строка, х ш-мерный вектор-столбец, А матрица порядка ш*п.
Например:
(2
| -4 Г | V | '2' | ||
| 1 -1 | * | - *1 | 1 | |
| . 2 1, | ,5, | |||
| К | * | Г | ||
| U, | Іо, |
Xсіхі =* min-}-1
j~ 1
ху 0
Или в матричном виде
сх = min, АхЬ, х 0.
Функция сх от переменных х,,...,х„ называется целевой функцией.
Числа х{,...,хп векторы х, удовлетворяющие неравенствам
Ах Ь, дг О
в задаче на максимум или
Ах Ь, х0
в задаче на минимум, называются множеством допустимых решений.
Иногда удобнее записывать задачу линейного программирования в канонической форме. Каноническая форма отличается от стандартной только записью ограничений. В канонической форме они записываются в следующем виде:
Х?? =bn
л (?)
Xj 0.
Задачу в канонической форме всегда можно привести к задаче в стандартной форме, записав равенства (7) в виде эквивалентной системы неравенств:
АхЬ,
-Ах -Ь.
С другой стороны, задачу в стандартной форме тоже можно привести к задаче в канонической форме, введя дополнительные переменные г. Системы неравенств:
АхЬ и Ax + lz = b,z 0,
(где I единичная матрица размерности ш*ш) эквивалентны. Например, задача (6) в канонической форме записывается как
|
=ф шах, |
| ' -4 | 1 | у \ | 1 | 0 | 0' | V | '2' | |||
| 1 | -1 | * | ¦ и | 0 | 1 | 0 | * | г2 | 1 | |
| , 2 | ь | 1-Г2 ) | ,0 | 0 | и | V "3 4 | ,5, |
| fz' | 'o' | |||
| ( х, ^ | Гол | 1 | ||
| I, | Z2 | 0 | ||
| Uy | loj |
2х, -х2 + 0z, + 0г2 + 0г3 = max, -4 x,+x2+z, =2, х, ~x2+z2 =1,
2.r, + x2 + z3 =5, x„x2,z„z2,z30.
Можно записать эту задачу проще, добавив нулевые элементы в вектор-строку коэффициентов целевой функции и столбцы в матрицу ограничений:
¦ max,
(2 -10 0 0)*
| V | ||||
| о о 7 |
*2 | f2l | ||
| 1-1010 | * | *3 | = | 1 |
| о о |
*4 | ,5, | ||
| Л 4 |
| '0' | ||
| *2 | 0 | |
| *3 | 0 | |
| *4 | 0 | |
| . Х5 J | 10, |
Найти вектор у такой, что
yb = min, у А с, уо,
или найти числа yt,...,ym такие, что
ХМ = min,
Іш\
HI
Хм2^
i= I
у, 0.
Стандартной задаче на минимум соответствует двойственная задача: Найти вектор у такой, что
yb = max, уАс, у 0.
или найти числа У\,,Ут такие, что
ХМ =тах-
м
т
Связь между прямой и двойственной задачами описывается следующими теоремами:
1. Если прямая и двойственная задачи имеют допустимые решения (т. е. множества их допустимых решений не пусты), то обе они имеют и оптимальные решенияу',х‘, причем
ех = уЬ
(оптимальные значения целевых функций прямой и двойственной задач равны),
. дсх'
у,~ж
(при увеличении правой части ограничения /? на единицу оптимальное значение целевой функции увечится примерно на ^единиц).
2. Для того чтобы допустимое решение прямой задачи линейного программирования ,х‘„ было оптимальным, необходимо и достаточно, чтобы нашлось такое допустимое решение двойственной задачи уу’ , что
I п
і=і j=і
3. Если оптимальное решение задачи линейного программирования существует, то
из у* =0 следует Хяг?у ~ь,, из у’ 0 следует Шаохі Ь ,
т
из х’ 0 следует XУій? = сі - 1 = 1
из х‘ =0 следует X -1’. ао сі-
В общем случае это не обязательно, но обычно количество ненулевых элементов в векторе оптимального решения равно наименьшему из чисел: количество ограничений, количество переменных в прямой задаче.
Оптимального решения задачи линейного программирования не существует в любом из следующих случаев:
1. Если целевая функция не ограничена на множестве допустимых решений. Например:
Зх, + х, =* max,
-х, + х2 4, х„хг 0.
2. Если множество допустимых решений пусто, т. е. описывается системой несовместных неравенств. Например:
х, + 2х, = max,
+хг 4, дг, 2,
-¦?'і -4,
0.
Обычно эти случаи являются следствием плохой постановки задачи.
Приложение 6 РЕШЕНИЕ ЗАДАЧЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В EXCEL
Для решения задач линейного программирования в Excel используется надстройка ПОИСК РЕШЕНИЯ. Работу этой надстройки рассмотрим на примере. Пусть требуется решить следующую задачу:
2х, -х2 = шах -4х, +х22 х,-х2\
2х, + х2 ? 5 x„x20.
или в матричных обозначениях:
Шаг 1. Ввести исходные данные в таблицу. В нашем примере коэффициенты целевой функции введены в ячейки А1: В1; элементы матрицы ограничений в ячейки АЗ:В5; правые части ограничений в ячейки D3: D5.
Шаг 2. Ввести нули в ячейки, отведенные под план. В нашем примере это ячейки А7 : А8, они выделены серым цветом.
Шаг 3. Ввести формулу для вычисления значения целевой функции. В примере под значение целевой функции отведена ячейка D1 (выделена серым цветом) и в нее введена формула:
=МУМНОЖ(А1:В1;А7:А8)
Шаг 4. Вычислить значение произведения матрицы ограничений на искомый вектор Ах . Для этого в примере отведены ячейки СЗ : С5. Они выделены серым цветом, и в них введена формула:
=МУМНОЖ(АЗ:В5;А7:А8)
Шаг 5. В меню СЕРВИС вызвать ПОИСК РЕШЕНИЯ, как показано на рис. П6.1.
Рис. П6.1. Вызов надстройки ПОИСК РЕШЕНИЯ
Рис. П6.2. Диалог ПОИСК РЕШЕНИЯ
Шаг 6. Установить флажок в окне равной диалога ПОИСК РЕШЕНИЯ, как показано на рис. П6.2.
Шаг 7. В окно Установить целевую ячейку ввести адрес ячейки, в которой хранится значение целевой функции, а в окно Изменяя ячейки адрес искомого вектора, как показано на рис. П6.3.
Шаг 8. В диалоге ПОИСК РЕШЕНИЯ нажать клавишу ДОБАВИТЬ, предварительно установив курсор в окне Ограничения. Появится новый диалог, как это показано па рис.
ГІ6.4.
Рис. П6.4. Диалог Добавление ограничения
Снова появится диалог ПОИСК РЕШЕНИЯ, как это показано на рис. П6.6.
Рис. П6.5. Добавление ограничений
Рис. П6.6. Диалог ПОИСК РЕШЕНИЯ после добавления ограничений
II6.7. после чего нажать ОК. На экране появится диалог ПОИСК РЕШЕНИЯ.
Рис. П6.7. Диалог Параметры
П6.8, нажать в диалоге-сообщении о результате поиска ОК, в противном случае искать ошибку.
Рис. П6.8. Решение найдено
Литература
1. Белов А. А/., Ботвин Г. А., Добрин Г. II., Карлик А. Е. Формирование и анализ основных показателей плана производства и реализации продукции с помощью Microsoft Excel. СПб.: изд.
СПб Университета экономики и финансов, 2000.
2. Гарнаев А. Использование MS Excel и VBA в экономике и финансах. СПб.: Bhv, 1999.
3. Григорьева Т. А. Налоги и другие обязательные платежи, действующие в Санкт-Петербурге в 2003 году. СПб.: Анатолия, 2003.
4. Додж М., Кината К., Стинсон К. Эффективная работа с Excel. СПб.: Питер, 1997.
5. Канторович Л. В., Горстко г\. Б. Оптимальные решения в экономике.
М.: Наука, 1972.
6. Карлберг К. Бизнес-анализ с помощью Excel. М.: Вилямс, 2000.
7. Кузин Б. И., Горбоконь А. А., Тютюкин В. К., Чернова Г. В. Экономико-математические модели в организации и планировании промышленного предприятия. Л.: изд.
ЛГУ, 1982.
8. Кузин Б., Юрьев В., Шахдинаров Г. Методы и модели управления фирмой. СПб.: Питер, 2001.
9. Лебедев В. Г., Дроздова Т. Г, Кушарев В. II., Асаул А. Н„ Осорьева И. Б. Управление затратами на предприятии. СПб.: Бизнес-пресса, 2003.
10. Смирницкий Е. К. Экономические показатели промышленности.
М.: Экономика, 1974.
11. Шепеленко Г. И. Экономика, организация и планирование производства на предприятии.
Ростов-на-Дону: Март, 2000.
