Экономико-математические методы и модели. Линейное программирование — Алесинская Т.В., Сербин В.Д., Катаев А.В
ББК 65.В 641 я73 Алесинская Т.В., Сербин В.Д., Катаев А.В. Учебно-методическое пособие по курсу «Экономико-математические методы и модели. Линейное программирование». Таганрог: Изд-во ТРТУ , 2001. 79 с. В учебно-методическом пособии рассмотрены вопросы построения математических моделей основных типов задач линейного программирования и способы их решения средствами табличного редактора Microsoft Excel, приведены примеры решения или рекомендации к решению конкретных задач. Предлагаемое учебно-методическое пособие рекомендуется для использования в курсе «Экономико-математические методы и модели» для студентов экономических специальностей. Электронная версия книги размещена в библиотеке AUP.Ru . Постоянный адрес книги в Интернет — http://www.aup.ru/books/m85/ Табл. 25. Ил. 30. Библиогр.: 7 назв. Печатается по решению ред.-изд. совета Таганрогского государственного радиотехнического университета. Рецензенты: Новиков М.В., канд. экон. наук, доцент каф. ГиМУ ТРТУ Карелин В.П., д-р техн. наук, профессор ТИУиЭ Таганрогский государственный радиотехнический университет, 2001. Алесинская Т.В., Сербин В.Д., Катаев А.В., 2001
| ВВЕДЕНИЕ | 5 |
| 1. ЛАБОРАТОРНАЯ РАБОТА №1 “РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО | |
| ПРОГРАММИРОВАНИЯ (ЛП) С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL” | 6 |
| 1.1. ЦЕЛЬ РАБОТЫ | 6 |
| 1.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ | 6 |
| 1.3. ИНСТРУКЦИЯ ПО ИСПОЛЬЗОВАНИЮ E XCEL ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛП [5] | 6 |
| 1.3.1. ОДНОИНДЕКСНЫЕ ЗАДАЧИ ЛП | 7 |
| 1.3.1.1. ВВОД ИСХОДНЫХ ДАННЫХ | 7 |
| 1.3.1.2. Решение задачи | 13 |
| 1.3.2. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ | 16 |
| 1.3.3. ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛП | 17 |
| 1.3.4. ЗАДАЧИ С БУЛЕВЫМИ ПЕРЕМЕННЫМИ | 20 |
| 1.3.5. ВОЗМОЖНЫЕ ОШИБКИ ПРИ ВВОДЕ УСЛОВИЙ ЗАДАЧ ЛП | 22 |
| 1.4. ПРИМЕРНЫЕ ВОПРОСЫ ДЛЯ ЗАЩИТЫ РАБОТЫ | 22 |
| 1.5. ВАРИАНТЫ | 24 |
| 2. ЛАБОРАТОРНАЯ РАБОТА №2 (ЧАСТЬ I) “ОДНОИНДЕКСНЫЕ ЗАДАЧИ | |
| ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ” | 27 |
| 2.1. ЦЕЛЬ РАБОТЫ | 27 |
| 2.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ | 27 |
| 2.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [1,2,3,4,6,7] | 28 |
| 2.4. ПРИМЕРНЫЕ ВОПРОСЫ ДЛЯ ЗАЩИТЫ РАБОТЫ | 40 |
| 2.5. ВАРИАНТЫ | 38 |
| 3. ЛАБОРАТОРНАЯ РАБОТА №2 (ЧАСТЬ II) “АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ | |
| ОДНОИНДЕКСНЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ” | 39 |
| 3.1. ЦЕЛЬ РАБОТЫ | 40 |
| 3.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ | 40 |
| 3.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [5,6,7] | 41 |
| 3.3.1. ЗАДАЧИ АНАЛИЗА ОПТИМАЛЬНОГО РЕШЕНИЯ НА ЧУВСТВИТЕЛЬНОСТЬ 41 | |
| 3.3.2. ГРАФИЧЕСКИЙ АНАЛИЗ ОПТИМАЛЬНОГО РЕШЕНИЯ НА | |
| ЧУВСТВИТЕЛЬНОСТЬ | 41 |
| 3.3.3. АНАЛИЗ ОПТИМАЛЬНОГО РЕШЕНИЯ НА ЧУВСТВИТЕЛЬНОСТЬ В EXCEL | 44 |
| 3.3.3.1. Отчет по результатам | 45 |
| 3.3.3.2. Отчет по устойчивости | 47 |
| 3.4. ПРИМЕРНЫЕ ВОПРОСЫ ДЛЯ ЗАЩИТЫ РАБОТЫ | 48 |
| 4. ЛАБОРАТОРНАЯ РАБОТА №3 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО | |
| ПРОГРАММИРОВАНИЯ. СТАНДАРТНАЯ ТРАНСПОРТНАЯ ЗАДАЧА” | 49 |
| 4.1. ЦЕЛЬ РАБОТЫ | 49 |
| 4.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ | 49 |
| 4.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [1,2,3,4,6,7] | 50 |
| 4.3.1. СТАНДАРТНАЯ МОДЕЛЬ ТРАНСПОРТНОЙ ЗАДАЧИ (ТЗ) | 50 |
| 4.3.2. ПРИМЕР ПОСТРОЕНИЯ МОДЕЛИ ТЗ | 52 |
| 4.4. ВАРИАНТЫ | 55 |
| 4.6. ПРИМЕРНЫЕ ВОПРОСЫ ДЛЯ ЗАЩИТЫ РАБОТЫ | 56 |
| 5. ЛАБОРАТОРНАЯ РАБОТА №4 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО | |
| ПРОГРАММИРОВАНИЯ. ЗАДАЧА О НАЗНАЧЕНИЯХ” | 57 |
| 5.1. ЦЕЛЬ РАБОТЫ | 57 |
| 5.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ | 57 |
| 5.3. ЗАДАЧА О НАЗНАЧЕНИЯХ. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [1,3,6,7] | 57 |
| 5.4. ПОСТАНОВКА ЗАДАЧИ О НАЗНАЧЕНИЯХ | 59 |
5.5. РЕКОМЕНДАЦИИ К РЕШЕНИЮ ЗАДАЧИ О НАЗНАЧЕНИЯХ В ЛАБОРАТОРНОЙ
| РАБОТЕ №4 | 59 |
| 5.4. ВАРИАНТЫ | 60 |
| 5.5. ПРИМЕРНЫЕ ВОПРОСЫ ДЛЯ ЗАЩИТЫ РАБОТЫ | 61 |
| 6. ЛАБОРАТОРНАЯ РАБОТА №5 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО | |
| ПРОГРАММИРОВАНИЯ. “ОРГАНИЗАЦИЯ ОПТИМАЛЬНОЙ СИСТЕМЫ | |
| СНАБЖЕНИЯ” | 61 |
| 6.1. ЦЕЛЬ РАБОТЫ | 61 |
| 6.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ | 61 |
| 6.3. ПОСТАНОВКА ЗАДАЧИ | 61 |
| 6.4. РЕКОМЕНДАЦИИ К РЕШЕНИЮ | 62 |
| 6.5. ВАРИАНТЫ | 62 |
| 6.6. ЗАЩИТА РАБОТЫ | 62 |
| 7. ЛАБОРАТОРНАЯ РАБОТА №6 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛП. | |
| ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПРОИЗВОДСТВЕННЫХ МОЩНОСТЕЙ” | 65 |
| 7.1. ЦЕЛЬ РАБОТЫ | 65 |
| 7.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ | 65 |
| 7.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ | 66 |
| 7.4. ПОСТАНОВКА ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ПРОИЗВОДСТВЕННЫХ | |
| МОЩНОСТЕЙ | 69 |
| 7.5. ПОСТРОЕНИЕ И РЕШЕНИЕ РЗ ЛП | 70 |
| 7.4. ВАРИАНТЫ | 76 |
| 7.6. ПРИМЕРНЫЕ ВОПРОСЫ НА ЗАЩИТЕ РАБОТЫ | 79 |
| ЛИТЕРАТУРА | 79 |
ВВЕДЕНИЕ В данном учебно-методическом пособии рассмотрены основные типы задач линейного программирования, даны рекомендации по построению их математических моделей и поиску оптимальных решений средствами табличного редактора Microsoft Excel. В целях более эффективного усвоения учебного материала пособие построено по принципу лабораторных работ, разбитых по типам задач линейного программирования. В рамках лабораторной работы № 1 представлены: • подробные методики и конкретные примеры решения одноиндексных и двухиндексных задач линейного программирования с различными видами ограничений; • возможные ошибки при вводе условий задач линейного программирования в MS Excel. Лабораторные работы № 2–7 содержат: • теоретическое описание математических моделей задач линейного программирования определенного типа и методики их построения; • примеры решения конкретных задач описанного типа или рекомендации к их решению. Каждая лабораторная работа включает в себя 12 вариантов учебных задач определенного типа, а также список примерных вопросов для защиты работы, охватывающих как теоретические положения, так и конкретные варианты заданий. Выбранный способ изложения учебного материала позволяет использовать данное пособие как в учебных целях, так и для решения практических задач с использованием Microsoft Excel. СПИСОК ИСПОЛЬЗУЕМЫХ ОБОЗНАЧЕНИЙ 1) ЛП – линейное программирование. 2) ЦФ – целевая функция. 3) РЗ – распределительная задача. 4) ТЗ – транспортная задача. 5) * – вопрос повышенной сложности.
1. ЛАБОРАТОРНАЯ РАБОТА №1 “РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ Microsoft Excel ” 1.1. ЦЕЛЬ РАБОТЫ Приобретение навыков решения задач линейного программирования (ЛП) в табличном редакторе Microsoft Excel. 1.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ Для модели ЛП, соответствующей номеру Вашего варианта, найдите оптимальное решение в табличном редакторе Microsoft Excel и продемонстрируйте его преподавателю. 1.3. ИНСТРУКЦИЯ ПО ИСПОЛЬЗОВАНИЮ Microsoft Excel ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛП [5] Для того чтобы решить задачу ЛП в табличном редакторе Microsoft Excel, необходимо выполнить следующие действия. 1. Ввести условие задачи: a) создать экранную форму для ввода условия задачи : • переменных, • целевой функции (ЦФ), • ограничений, • граничных условий; b) ввести исходные данные в экранную форму : • коэффициенты ЦФ, • коэффициенты при переменных в ограничениях, • правые части ограничений; c) ввести зависимости из математической модели в экранную форму : • формулу для расчета ЦФ, • формулы для расчета значений левых частей ограничений; d) задать ЦФ (в окне «Поиск решения» ): • целевую ячейку, • направление оптимизации ЦФ; e) ввести ограничения и граничные условия (в окне «Поиск решения» ): • ячейки со значениями переменных, • граничные условия для допустимых значений переменных, • соотношения между правыми и левыми частями ограничений. 2. Решить задачу: a) установить параметры решения задачи (в окне «Поиск решения» ); b) запустить задачу на решение (в окне «Поиск решения» ) ;
c) выбрать формат вывода решения (в окне «Результаты поиска решения» ). 1.3.1. Одноиндексные задачи ЛП Рассмотрим пример нахождения решения для следующей одноиндексной
| задачи ЛП: | ||||
| L ( X ) = 130,5x 1 + 20x 2 + 56x 3 + 87,8x 4 → max; | ||||
| − 1,8x 1 + 2x | 2 + x 3 | − 4x 4 = 756, | ||
| + 4x 3 | − x 4 ≥ 450, | (1.1) | ||
| − 6x 1 + 2x 2 | ||||
| + 10,4x 3 + 13x 4 ≤ 89, | ||||
| 4x 1 − 1,5x 2 | ||||
| x j ≥ 0; j = 1,4. | ||||
1.3.1.1. Ввод исходных данных Создание экранной формы и ввод в нее условия задачи Экранная форма для ввода условий задачи (1.1) вместе с введенными в нее исходными данными представлена на рис.1.1. Рис. 1.1. Экранная форма задачи (1.1) (курсор в ячейке F6) В экранной форме на рис. 1.1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным задачи (1.1) соответствуют ячейки B3 ( x 1 ), C3 ( x 2 ), D3 ( x 3 ), E3 ( x 4 ), коэффициентам ЦФ соответствуют ячейки B6 (c 1 = 130,5), C6 (c 2 = 20), D6 (c 3 =56), E6 (c 4 = 87,8), правым частям ограничений соответствуют ячейки H10 ( b 1 = 756), H11 ( b 2 = 450), H12 ( b 3 = 89) и т.д.
Ввод зависимостей из математической модели в экранную форму Зависимость для ЦФ В ячейку F6 , в которой будет отображаться значение ЦФ, необходимо ввести формулу, по которой это значение будет рассчитано. Согласно (1.1) значение ЦФ определяется выражением
| 130,5x 1 + 20x 2 + 56x 3 + 87,8x 4 . | (1.2) |
Используя обозначения соответствующих ячеек в Excel (см. рис. 1.1), формулу для расчета ЦФ (1.2) можно записать как сумму произведений каждой из ячеек, отведенных для значений переменных задачи ( B3, C3, D3, E3 ), на соответствующую ячейку, отведенную для коэффициентов ЦФ ( B6, C6, D6, E6 ), то есть
| B6 B3 + C6 C3 + D6 D3 + E6 E3 . | (1.3) |
| Чтобы задать формулу (1.3) необходимо в ячейку F6 ввести следующее | |
| выражение и нажать клавишу «Enter» | |
| =СУММПРОИЗВ(B$3:E$3;B6:E6 ), | (1.4) |
где символ $ перед номером строки 3 означает, что при копировании этой формулы в другие места листа Excel номер строки 3 не изменится; символ : означает, что в формуле будут использованы все ячейки, расположенные между ячейками, указанными слева и справа от двоеточия (например, запись B6:E6 указывает на ячейки B6, C6, D6 и E6 ). После этого в целевой ячейке появится 0 (нулевое значение) (рис. 1.2). Рис.1.2. Экранная форма задачи (1.1) после ввода всех необходимых формул (курсор в ячейке F6)
Примечание 1.1. Существует другой способ задания функций в Excel с помощью режима «Вставка функций» , который можно вызвать из меню «Вставка» или при нажатии кнопки » f x » на стандартной панели инструментов. Так, например, формулу (1.4) можно задать следующим образом: • курсор в поле F6; • нажав кнопку » f x «, вызовите окно «Мастер функций – шаг 1 из 2»; • выберите в окне «Категория» категорию «Математические»; • в окне «Функция» выберите функцию СУММПРОИЗВ ; • в появившемся окне «СУММПРОИЗВ» в строку «Массив 1» введите выражение B$3:E$3 , а в строку «Массив 2» – выражение B6:E6 (рис. 1.3); • после ввода ячеек в строки «Массив 1» и «Массив 2» в окне «СУММПРОИЗВ» появятся числовые значения введенных массивов (см. рис. 1.3), а в экранной форме в ячейке F6 появится текущее значение, вычисленное по введенной формуле, то есть 0 (так как в момент ввода формулы значения переменных задачи нулевые). Рис. 1.3. Ввод формулы для расчета ЦФ в окно «Мастер функций» Зависимости для левых частей ограничений Левые части ограничений задачи (1.1) представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи ( B3, C3, D3, E3 ), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения ( B10, C10, D10, E10 – 1-е ограничение ; B11, C11, D11, E11 – 2-е ограничение и B12, C12, D12, E12 – 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл. 1.1.
| Таблица 1.1 | ||||
| Формулы, описывающие ограничения модели (1.1) | ||||
| Левая часть ограничения | Формула Excel | |||
| − 1,8x 1 + 2x 2 + x 3 − 4x 4 или | =СУММПРОИЗВ(B$3:E$3;B10:E10 ) | |||
| B10 B3 + | C10 | C3 + D10 D3 + | E10 E3 | |
| − 6x 1 | + 2x 2 + 4x 3 − x 4 или | =СУММПРОИЗВ(B$3:E$3;B11:E11 ) | ||
| B11 B3 + | C11 | C3 + D11 D3 + | E11 E3 | |
| 4x 1 − 1,5x 2 + | 10,4x 3 + 13x 4 | или | =СУММПРОИЗВ(B$3:E$3;B12:E12 ) | |
| B12 B3 + | C12 | C3 + D12 D3 + | E12 E3 | |
Как видно из табл. 1.1, формулы, задающие левые части ограничений задачи (1.1), отличаются друг от друга и от формулы (1.4) в целевой ячейке F6 только номером строки во втором массиве. Этот номер определяется той строкой, в которой ограничение записано в экранной форме. Поэтому для задания зависимостей для левых частей ограничений достаточно скопировать формулу из целевой ячейки в ячейки левых частей ограничений. Для этого необходимо: • поместить курсор в поле целевой ячейки F6 и скопировать в буфер содержимое ячейки F6 (клавишами «Ctrl-Insert» ); • помещать курсор поочередно в поля левой части каждого из ограничений, то есть в F10, F11 и F12, и вставлять в эти поля содержимое буфера (клавишами «Shift-Insert» ) (при этом номер ячеек во втором массиве формулы будет меняться на номер той строки, в которую была произведена вставка из буфера); • на экране в полях F10 , F11 и F12 появится 0 (нулевое значение) (см. рис. 1.2). Проверка правильности введения формул Для проверки правильности введенных формул производите поочередно двойное нажатие левой клавиши мыши на ячейки с формулами. При этом на экране рамкой будут выделяться ячейки, используемые в формуле (рис. 1.4 и 1.5).