4252

Учебно-методическое пособие по курсу экономико-математические методы и модели. Линейное программирование

Книга

Информатика, кибернетика и программирование

В учебно-методическом пособии рассмотрены вопросы построения математических моделей основных типов задач линейного программирования и способы их решения средствами табличного редактора Microsoft Excel, приведены примеры решения или рекомендации к ре...

Русский

2012-11-15

1.17 MB

193 чел.

В учебно-методическом пособии рассмотрены вопросы построения математических моделей основных типов задач линейного программирования и способы их решения средствами табличного редактора Microsoft Excel, приведены примеры решения или рекомендации к решению конкретных задач.

Предлагаемое учебно-методическое пособие рекомендуется для использования в курсе "Экономико-математические методы и модели" для студентов экономических специальностей.


СОДЕРЖАНИЕ

ВВЕДЕНИЕ 2

1. ЛАБОРАТОРНАЯ РАБОТА №1 “РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЛП) С ИСПОЛЬЗОВАНИЕМ Microsoft Excel” 2

1.1. ЦЕЛЬ РАБОТЫ 2

1.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ 2

1.3. ИНСТРУКЦИЯ ПО ИСПОЛЬЗОВАНИЮ Excel ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛП [5] 2

1.3.1. ОДНОИНДЕКСНЫЕ ЗАДАЧИ ЛП 2

1.3.1.1. ВВОД ИСХОДНЫХ ДАННЫХ 2

1.3.1.2. Решение задачи 2

1.3.2. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ 2

1.3.3. ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛП 2

1.3.4. ЗАДАЧИ С БУЛЕВЫМИ ПЕРЕМЕННЫМИ 2

1.3.5. ВОЗМОЖНЫЕ ОШИБКИ ПРИ ВВОДЕ УСЛОВИЙ ЗАДАЧ ЛП 2

1.4. ПРИМЕРНЫЕ ВОПРОСЫ ДЛЯ ЗАЩИТЫ РАБОТЫ 2

1.5. ВАРИАНТЫ 2

2. ЛАБОРАТОРНАЯ РАБОТА №2 (часть I) “ОДНОИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ” 2

2.1. ЦЕЛЬ РАБОТЫ 2

2.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ 2

2.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [1,2,3,4,6,7] 2

2.4. ПРИМЕРНЫЕ ВОПРОСЫ ДЛЯ ЗАЩИТЫ РАБОТЫ 2

2.5. ВАРИАНТЫ 2

3. ЛАБОРАТОРНАЯ РАБОТА №2 (часть II) “АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ ОДНОИНДЕКСНЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ” 2

3.1. ЦЕЛЬ РАБОТЫ 2

3.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ 2

3.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [5,6,7] 2

3.3.1. ЗАДАЧИ АНАЛИЗА ОПТИМАЛЬНОГО РЕШЕНИЯ НА ЧУВСТВИТЕЛЬНОСТЬ 2

3.3.2. ГРАФИЧЕСКИЙ АНАЛИЗ ОПТИМАЛЬНОГО РЕШЕНИЯ НА ЧУВСТВИТЕЛЬНОСТЬ 2

3.3.3. АНАЛИЗ ОПТИМАЛЬНОГО РЕШЕНИЯ НА ЧУВСТВИТЕЛЬНОСТЬ В EXCEL 2

3.3.3.1. Отчет по результатам 2

3.3.3.2. Отчет по устойчивости 2

3.4. ПРИМЕРНЫЕ ВОПРОСЫ ДЛЯ ЗАЩИТЫ РАБОТЫ 2

4. ЛАБОРАТОРНАЯ РАБОТА №3 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СТАНДАРТНАЯ ТРАНСПОРТНАЯ ЗАДАЧА” 2

4.1. ЦЕЛЬ РАБОТЫ 2

4.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ 2

4.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [1,2,3,4,6,7] 2

4.3.1. СТАНДАРТНАЯ МОДЕЛЬ ТРАНСПОРТНОЙ ЗАДАЧИ (ТЗ) 2

4.3.2. ПРИМЕР ПОСТРОЕНИЯ МОДЕЛИ ТЗ 2

4.4. ВАРИАНТЫ 2

4.6. ПРИМЕРНЫЕ ВОПРОСЫ ДЛЯ ЗАЩИТЫ РАБОТЫ 2

5. ЛАБОРАТОРНАЯ РАБОТА №4 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ЗАДАЧА О НАЗНАЧЕНИЯХ” 2

5.1. ЦЕЛЬ РАБОТЫ 2

5.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ 2

5.3. ЗАДАЧА О НАЗНАЧЕНИЯХ. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [1,3,6,7] 2

5.4. ПОСТАНОВКА ЗАДАЧИ О НАЗНАЧЕНИЯХ 2

5.5. РЕКОМЕНДАЦИИ К РЕШЕНИЮ ЗАДАЧИ О НАЗНАЧЕНИЯХ В ЛАБОРАТОРНОЙ РАБОТЕ №4 2

5.4. ВАРИАНТЫ 2

5.5. ПРИМЕРНЫЕ ВОПРОСЫ ДЛЯ ЗАЩИТЫ РАБОТЫ 2

6. ЛАБОРАТОРНАЯ РАБОТА №5 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. “ОРГАНИЗАЦИЯ ОПТИМАЛЬНОЙ СИСТЕМЫ СНАБЖЕНИЯ” 2

6.1. ЦЕЛЬ РАБОТЫ 2

6.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ 2

6.3. ПОСТАНОВКА ЗАДАЧИ 2

6.4. РЕКОМЕНДАЦИИ К РЕШЕНИЮ 2

6.5. ВАРИАНТЫ 2

6.6. ЗАЩИТА РАБОТЫ 2

7. ЛАБОРАТОРНАЯ РАБОТА №6 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛП. ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПРОИЗВОДСТВЕННЫХ МОЩНОСТЕЙ” 2

7.1. ЦЕЛЬ РАБОТЫ 2

7.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ 2

7.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 2

7.4. ПОСТАНОВКА ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ПРОИЗВОДСТВЕННЫХ МОЩНОСТЕЙ 2

7.5. ПОСТРОЕНИЕ И РЕШЕНИЕ РЗ ЛП 2

7.4. ВАРИАНТЫ 2

7.6. ПРИМЕРНЫЕ ВОПРОСЫ НА ЗАЩИТЕ РАБОТЫ 2

ЛИТЕРАТУРА 2


ВВЕДЕНИЕ

В данном учебно-методическом пособии рассмотрены основные типы задач линейного программирования, даны рекомендации по построению их математических моделей и поиску оптимальных решений средствами табличного редактора 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.  Ввести условие задачи:
    1.   создать экранную форму для ввода условия задачи:
      •  переменных,
      •  целевой функции (ЦФ),
      •  ограничений,
      •  граничных условий;
    2.   ввести исходные данные в экранную форму:
      •  коэффициенты ЦФ,
      •  коэффициенты при переменных в ограничениях,
      •  правые части ограничений;
    3.   ввести зависимости из математической модели в экранную форму:
      •  формулу для расчета ЦФ,
      •  формулы для расчета значений левых частей ограничений;
    4.   задать ЦФ (в окне "Поиск решения"):
      •  целевую ячейку,
      •  направление оптимизации ЦФ;
    5.   ввести ограничения и граничные условия (в окне "Поиск решения"):
      •  ячейки со значениями переменных,
      •  граничные условия для допустимых значений переменных,
      •  соотношения между правыми и левыми частями ограничений.
  2.  Решить задачу:
    1.   установить параметры решения задачи (в окне "Поиск решения");
    2.   запустить задачу на решение (в окне "Поиск решения");
    3.   выбрать формат вывода решения (в окне "Результаты поиска решения").

1.3.1. Одноиндексные задачи ЛП

Рассмотрим пример нахождения решения для следующей одноиндексной задачи ЛП:

(1.1)

1.3.1.1. Ввод исходных данных

Создание экранной формы и ввод в нее условия задачи

Экранная форма для ввода условий задачи (1.1) вместе с введенными в нее исходными данными представлена на рис.1.1.

Рис.1.1. Экранная форма задачи (1.1) (курсор в ячейке F6)

В экранной форме на рис.1.1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным задачи (1.1) соответствуют ячейки B3 (), C3 (), D3 (), E3 (), коэффициентам ЦФ соответствуют ячейки B6 (130,5), C6 (20), D6 (56), E6 (87,8), правым частям ограничений соответствуют ячейки H10 (756), H11 (450), H12 (89) и т.д.

Ввод зависимостей из математической модели в экранную форму

Зависимость для ЦФ

В ячейку F6, в которой будет отображаться значение ЦФ, необходимо ввести формулу, по которой это значение будет рассчитано. Согласно (1.1) значение ЦФ определяется выражением

.

(1.2)

Используя обозначения соответствующих ячеек в Excel (см. рис.1.1), формулу для расчета ЦФ (1.2) можно записать как сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B3, C3, D3, E3), на соответствующую ячейку, отведенную для коэффициентов ЦФ (B6, C6, D6, E6), то есть

.

(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 с помощью режима "Вставка функций", который можно вызвать из меню "Вставка" или при нажатии кнопки "" на стандартной панели инструментов. Так, например, формулу (1.4) можно задать следующим образом:

  •  курсор в поле F6;
  •  нажав кнопку "", вызовите окно "Мастер функций – шаг 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

или

=СУММПРОИЗВ(B$3:E$3;B10:E10)

или

=СУММПРОИЗВ(B$3:E$3;B11:E11)

или

=СУММПРОИЗВ(B$3:E$3;B12:E12)

Как видно из табл.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).

Рис.1.4. Проверка правильности введения формулы в целевую ячейку F6

Рис.1.5. Проверка правильности введения формулы в ячейку F12

для левой части ограничения 3

Задание ЦФ

Дальнейшие действия производятся в окне "Поиск решения", которое вызывается из меню "Сервис" (рис.1.6):

  •  поставьте курсор в поле "Установить целевую ячейку";
  •  введите адрес целевой ячейки $F$6 или сделайте одно нажатие левой клавиши мыши на целевую ячейку в экранной форме это будет равносильно вводу адреса с клавиатуры;
  •  введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке "максимальному значению".

Рис.1.6. Окно "Поиск решения" задачи (1.1)

Ввод ограничений и граничных условий

Задание ячеек переменных

В окно "Поиск решения" в поле "Изменяя ячейки" впишите адреса $B$3:$E$3. Необходимые адреса можно вносить в поле "Изменяя ячейки" и автоматически путем выделения мышью соответствующих ячеек переменных непосредственно в экранной форме.

Задание граничных условий для допустимых значений переменных

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

  •  Нажмите кнопку "Добавить", после чего появится окно "Добавление ограничения" (рис.1.7).
  •  В поле "Ссылка на ячейку" введите адреса ячеек переменных $B$3:$E$3. Это можно сделать как с клавиатуры, так и путем выделения мышью всех ячеек переменных непосредственно в экранной форме.
  •  В поле знака откройте список предлагаемых знаков и выберите .
  •  В поле "Ограничение" введите адреса ячеек нижней границы значений переменных, то есть $B$4:$E$4. Их также можно ввести путем выделения мышью непосредственно в экранной форме.

Рис.1.7. Добавление условия неотрицательности переменных задачи (1.1)

Задание знаков ограничений , , =

  •  Нажмите кнопку "Добавить" в окне "Добавление ограничения".
  •  В поле "Ссылка на ячейку" введите адрес ячейки левой части конкретного ограничения, например $F$10. Это можно сделать как с клавиатуры, так и путем выделения мышью нужной ячейки непосредственно в экранной форме.
  •  В соответствии с условием задачи (1.1) выбрать в поле знака необходимый знак, например =.
  •  В поле "Ограничение" введите адрес ячейки правой части рассматриваемого ограничения, например $H$10.
  •  Аналогично введите ограничения: $F$11>=$H$11, $F$12<=$H$12.
  •  Подтвердите ввод всех перечисленных выше условий нажатием кнопки OK.

Окно "Поиск решения" после ввода всех необходимых данных задачи (1.1) представлено на рис.1.6.

Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делают, нажав кнопки "Изменить" или "Удалить" (см. рис.1.6).

1.3.1.2. Решение задачи

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

Задача запускается на решение в окне "Поиск решения". Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку "Параметры" и заполнить некоторые поля окна "Параметры поиска решения" (рис.1.8).

Рис.1.8. Параметры поиска решения, подходящие для большинства задач ЛП

Параметр "Максимальное время" служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).

Параметр "Предельное число итераций" служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32 767.

Параметр "Относительная погрешность" служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.

Параметр "Допустимое отклонение" служит для задания допуска на отклонение от оптимального решения в целочисленных задачах. При указании большего допуска поиск решения заканчивается быстрее.

Параметр "Сходимость" применяется только при решении нелинейных задач.

Установка флажка "Линейная модель" обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.

Подтвердите установленные параметры нажатием кнопки "OK".

Запуск задачи на решение

Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить".

После запуска на решение задачи ЛП на экране появляется окно "Результаты поиска решения" с одним из сообщений, представленных на рис.1.9, 1.10 и 1.11.

Рис.1.9. Сообщение об успешном решении задачи

Рис.1.10. Сообщение при несовместной системе ограничений задачи

Рис.1.11. Сообщение при неограниченности ЦФ в требуемом направлении

Иногда сообщения, представленные на рис.1.10 и 1.11, свидетельствуют не о характере оптимального решения задачи, а о том, что при вводе условий задачи в Excel были допущены ошибки, не позволяющие Excel найти оптимальное решение, которое в действительности существует (см. ниже подразд.1.3.5).

Если при заполнении полей окна "Поиск решения" были допущены ошибки, не позволяющие Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра "Относительная погрешность" не позволяет найти оптимальное решение. Для исправления этой ситуации увеличивайте погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.

В окне "Результаты поиска решения" представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы". Они необходимы при анализе полученного решения на чувствительность (см. ниже подразд.3.3). Для получения же ответа (значений переменных, ЦФ и левых частей ограничений) прямо в экранной форме просто нажмите кнопку "OK". После этого в экранной форме появляется оптимальное решение задачи (рис.1.12).

Рис.1.12. Экранная форма задачи (1.1) после получения решения

1.3.2. Целочисленное программирование

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

  •  В экранной форме укажите, на какие переменные накладывается требование целочисленности (этот шаг делается для наглядности восприятия условия задачи) (рис.1.13).
  •  В окне "Поиск решения" (меню "Сервис""Поиск решения"), нажмите кнопку "Добавить" и в появившемся окне "Добавление ограничений" введите ограничения следующим образом (рис.1.14):
  •  в поле "Ссылка на ячейку" введите адреса ячеек переменных задачи, то есть $B$3:$E$3;
  •  в поле ввода знака ограничения установите "целое";
  •  подтвердите ввод ограничения нажатием кнопки "OK".

Рис.1.13. Решение задачи (1.1) при условии целочисленности ее переменных

Рис.1.14. Ввод условия целочисленности переменных задачи (1.1)

На рис.1.13 представлено решение задачи (1.1), к ограничениям которой добавлено условие целочисленности значений ее переменных.

1.3.3. Двухиндексные задачи ЛП

Двухиндексные задачи ЛП вводятся и решаются в Excel аналогично одноиндексным задачам. Специфика ввода условия двухиндексной задачи ЛП состоит лишь в удобстве матричного задания переменных задачи и коэффициентов ЦФ.

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


Таблица 1.2

Исходные данные транспортной задачи

Тарифы, руб./шт.

1-й магазин

2-й магазин

3-й магазин

Запасы, шт.

1-й склад

2

9

7

25

2-й склад

1

0

5

50

3-й склад

5

4

100

35

4-й склад

2

3

6

75

Потребности, шт.

45

90

50

Целевая функция и ограничения данной задачи имеют вид

(1.5)

Экранные формы, задание переменных, целевой функции, ограничений и граничных условий двухиндексной задачи (1.5) и ее решение представлены на рис.1.15, 1.16, 1.17 и в табл.1.3.

Рис.1.15. Экранная форма двухиндексной задачи (1.5)

(курсор в целевой ячейке F15)

Таблица 1.3

Формулы экранной формы задачи (1.5)

Объект математической модели

Выражение в Excel

Переменные задачи

C3:E6

Формула в целевой ячейке F15

=СУММПРОИЗВ(C3:E6;C12:E15)

Ограничения по строкам

в ячейках F3, F4, F5, F6

=СУММ(C3:E3)

=СУММ(C4:E4)

=СУММ(C5:E5)

=СУММ(C6:E6)

Ограничения по столбцам

в ячейках С7, D7, E7

=СУММ(C3:C6)

=СУММ(D3:D6)

=СУММ(E3:E6)

Суммарные запасы и потребности

в ячейках H8, G9

=СУММ(H3:H6)

=СУММ(C9:E9)

Рис.1.16. Ограничения и граничные условия задачи (1.5)

Рис.1.17. Экранная форма после получения решения задачи (1.5)

(курсор в целевой ячейке F15)

1.3.4. Задачи с булевыми переменными

Частным случаем задач с целочисленными переменными являются задачи, в результате решения которых искомые переменные  могут принимать только одно из двух значений: 0 или 1. Такие переменные в честь предложившего их английского математика Джорджа Буля называют булевыми. На рис.1.18 представлена экранная форма с решением некоторой двухиндексной задачи с булевыми переменными.

Рис.1.18. Решение двухиндексной задачи с булевыми переменными

Помимо задания требования целочисленности (см. подразд.1.3.2) при вводе условия задач с булевыми переменными необходимо:

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

Рис.1.19. Добавление условия единичной верхней границы значений переменных двухиндексной задачи с булевыми переменными

Вид окна "Поиск решения" для задачи с булевыми переменными, представленной на рис.1.18, приведен на рис.1.20.

Рис.1.20. Окно "Поиск решения" для задачи с булевыми переменными, представленной на рис.1.18

1.3.5. Возможные ошибки при вводе условий задач ЛП

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


Таблица 1.4

Список вопросов, позволяющих выявить ошибки ввода условия задачи в Excel

Месторасположение в Excel

Экранная форма

Экранная форма

Экранная форма

Окно "Поиск решения"

Окно "Поиск решения"

Окно "Поиск решения"

Поле "Изменяя ячейки"

Экранная форма,

Окно "Поиск решения"

Поле "Ограничения"

Окно "Поиск решения"

Поле "Ограничения"

Окно "Поиск решения"

Поле "Ограничения"

Окно "Поиск решения"

Поле "Ограничения"

Окно "Поиск решения"

Поле "Ограничения"

Окно "Параметры поиска решения"

Вопрос

Правильно ли Вы ввели численные значения и знаки (+, —) коэффициентов целевой функции и ограничений, правых частей ограничений ?

Сбалансирована ли двухиндексная задача?

Правильны ли формулы в целевой ячейке и в ячейках левых частей ограничений? Для наглядности проверки поставьте курсор на ячейку с формулой и сделайте двойной щелчок левой клавишей мыши. Рамкой в экранной форме будут выделены ячейки, участвующие в данной формуле (см. рис.1.4, 1.5).

Правильно ли указан адрес целевой ячейки?

Правильно ли указано направление оптимизации ЦФ?

Правильно ли указаны адреса ячеек переменных?

Правильно ли введены знаки ограничений (<=, >=, =) ?

Правильно ли указаны адреса ячеек левых и правых частей ограничений?

Не забыли ли Вы задать требование неотрицательности переменных?

Не забыли ли Вы задать требования по единичному значению верхней границы переменных (для задач с булевыми переменными)

Не забыли ли Вы задать условие целочисленности переменных (согласно условию задачи)?

Проверьте правильность установки параметров (см. подразд.1.3.1.2)

1

2

3

4

5

6

7

8

9

10

11

12

1.4. ПРИМЕРНЫЕ ВОПРОСЫ НА ЗАЩИТЕ РАБОТЫ

  1.  Каковы основные этапы решения задач ЛП в MS Excel?
  2.  Каков вид и способы задания формул для целевой ячейки и ячеек левых частей ограничений?
  3.  В чем смысл использования символа $ в формулах MS Excel?
  4.  В чем различие использования в формулах MS Excel символов ; и :?
  5.  Почему при вводе формул в ячейки ЦФ и левых частей ограничений в них отображаются нулевые значения?
  6.  Каким образом в MS Excel задается направление оптимизации ЦФ?
  7.  Какие ячейки экранной формы выполняют иллюстративную функцию, а какие необходимы для решения задачи?
  8.  Как наглядно отобразить в экранной форме ячейки, используемые в конкретной формуле, с целью проверки ее правильности?
  9.  Поясните общий порядок работы с окном "Поиск решения".
  10.  Каким образом можно изменять, добавлять, удалять ограничения в окне "Поиск решения"?
  11.  Какие сообщения выдаются в MS Excel в случаях: успешного решения задачи ЛП; несовместности системы ограничений задачи; неограниченности ЦФ?
  12.  Объясните смысл параметров, задаваемых в окне "Параметры поиска решения".
  13.  Каковы особенности решения в MS Excel целочисленных задач ЛП?
  14.  Каковы особенности решения в MS Excel двухиндексных задач ЛП?
  15.  Каковы особенности решения в MS Excel задач ЛП с булевыми переменными?

1.5. ВАРИАНТЫ

Используя MS Excel, найти решение для модели ЛП, соответствующей заданному варианту (табл.1.5).

Таблица 1.5

Варианты задач к лабораторной работе №1

№ варианта

Математическая модель

1

2


№ варианта

Математическая модель

3

4

5

6

7


№ варианта

Математическая модель

8

9

10

11

12


2. ЛАБОРАТОРНАЯ РАБОТА №2 (ЧАСТЬ I)

“ОДНОИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ”

2.1. ЦЕЛЬ РАБОТЫ

Приобретение навыков построения математических моделей одноиндексных задач ЛП и решения их в Microsoft Excel.

2.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Согласно номеру своего варианта выберите условие задачи и постройте ее модель.

2. Найдите оптимальное решение задачи в Excel и продемонстрируйте его преподавателю.

Примечание 2.1. Расчет числовых данных, которые непосредственно не заданы в условии задачи, производите непосредственно в ячейках экранной формы. Например, для ввода коэффициента  при  в левой части (2.3) в соответствующую ячейку надо ввести выражение =4/60, после чего в ячейке отобразится результат вычисления, то есть 0,066666667. Для ввода правой части ограничения (2.3) в соответствующую ячейку надо ввести выражение =14*8*1*22, при этом в ячейке отобразится число 2464. Этот способ позволяет четко представлять путь получения числовых данных в ячейках экранной формы, избегать ошибок при расчете параметров задачи, а также обеспечивает высокую точность расчетов.

3. Оформите отчет по лабораторной работе, который должен содержать:

  •  титульный лист (рис.2.1);
  •  исходные данные варианта;
  •  построенную модель задачи с указанием всех единиц измерения;
  •  результаты решения задачи.

Министерство образования РФ

ТРТУ

Кафедра МЭМ

Отчет по лабораторной работе №1

”Решение задач линейного программирования

с использованием Microsoft Excel

                                                                                  Выполнил: Ф.И.О.

                                                                                  Проверил: Ф.И.О.

Таганрог 2001

Рис.2.1. Пример оформления титульного листа отчета по лабораторной работе

2.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [1,2,3,4,6,7]

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

Для решения таких задач используются методы математического программирования. Математическое программирование – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Слово "программирование" заимствовано из зарубежной литературы, где оно используется в смысле "планирование".

Наиболее простыми и лучше всего изученными среди задач математического программирования являются задачи линейного программирования.

Характерные черты задач ЛП следующие:

1) показатель эффективности L представляет собой линейную функцию, заданную на элементах решения ;

2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.

В общей форме записи модель задачи ЛП имеет вид:

                                        целевая функция (ЦФ)

;

                                  при ограничениях

(2.1)

Допустимое решение – это совокупность чисел , удовлетворяющих ограничениям задачи (2.1).

Оптимальное решение – это план , при котором ЦФ принимает свое максимальное (минимальное) значение.

Для построения математической модели необходимо ответить на следующие три вопроса.

1. Что является искомыми величинами, то есть переменными этой задачи?

2. В чем состоит цель, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать наилучшему, то есть оптимальному, решению?

3. Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, описанные в задаче?

В данной лабораторной работе рассматривается одноиндексная задача ЛП, представляющая собой общую распределительную задачу, которая характеризуется различными единицами измерения работ и ресурсов.

Рассмотрим следующую задачу (вариант 0 из табл.2.1).

Постановка задачи

Мебельный комбинат выпускает книжные полки А из натурального дерева со стеклом, полки B1 из полированной ДСП (древесно-стружечной плиты) без стекла и полки B2 из полированной ДСП со стеклом. Габариты полок А, B1 и В2 следующие: длина 1100 (d) мм, ширина 250 (w) мм, высота 300 (h) мм (рис.2.2). Размер листа ДСП  м.

Рис.2.2. Габариты полок, выпускаемых мебельным комбинатом

При изготовлении полок А выполняются следующие работы: столярные, покрытие лаком, сушка, резка стекла, упаковка. Все операции, производимые в ходе столярных работ и упаковки, выполняются вручную. Полки B1 и В2 поставляются в торговую сеть в разобранном виде. За исключением операции упаковки, все остальные операции (производство комплектующих полки, резка стекла) при изготовлении полок B1 и В2, выполняются на специализированных автоматах.

Трудоемкость столярных работ по выпуску одной полки А составляет 4 (Тр1) ч. Производительность автомата, покрывающего полки А лаком – 10 (Пр1) полок в час, автомата, режущего стекло – 100 (Пp2) стекол в час. Сменный фонд времени автомата для покрытия лаком – 7 (ФВ1) ч, автомата для резки стекла – 7,5 (ФВ2) ч. Сушка полок, покрытых лаком, происходит в течение суток в специальных сушилках, вмещающих 50 (V1) полок. На упаковку полки А требуется 4 (Тр2) минуты. В производстве полок заняты 40 (Р1) столяров и 14 (Р2) упаковщиков.

Производительность автомата, производящего комплектующие полок B1 и В2, равна 3 (Пр3) полки в час, а его сменный фонд времени равен 7,4 (ФВ3) ч, трудоемкость упаковочных работ составляет 8 (Тр3) мин для полки В1 и 10 (Тр4) мин для полки В2.

От поставщиков комбинат получает в месяц 400 (Z1) листов полированной ДСП, 230 (Z2) листов ДВП (древесно-волокнистой плиты), а также 260 (Z3) листов стекла. Из каждого листа ДВП можно выкроить 14 (К1) задних стенок полок B1 и В2, а из каждого листа стекла – 10 (К2) стекол для полок А и В2.

Склад готовой продукции может разместить не более 350 (V2) полок и комплектов полок, причем ежедневно в торговую сеть вывозится в среднем 40 (N) полок и комплектов. На начало текущего месяца на складе осталось 100 (Ост) полок, произведенных ранее. Себестоимость полки А равна 205 (C1) руб., полки В без стекла – 142 (C2) руб., со стеклом – 160 (С3) руб.

Маркетинговые исследования показали, что доля продаж полок обоих видов со стеклом составляет не менее 60% (Д) в общем объеме продаж, а емкость рынка полок производимого типа составляет около 5300 (V3) штук в месяц. Мебельный комбинат заключил договор на поставку заказчику 50 (З) полок типа В2 в текущем месяце.

Составьте план производства полок на текущий месяц. Известны цены реализации полок: полка А – 295 (Ц1) руб., полка В без стекла – 182 (Ц2) руб., полка В со стеклом – 220 (Ц3) руб.

Построение модели

I этап построения модели заключается в определении (описании, задании, идентификации) переменных. В данной задаче искомыми неизвестными величинами является количество полок каждого вида, которые будут произведены в текущем месяце. Таким образом, – количество полок А (шт./мес.); – количество полок В1 (шт./мес.); – количество полок В2 (шт./мес.).

II этап построения модели заключается в построении целевой функции, представляющей цель решения задачи. В данном случае цель – это максимизация прибыли, получаемой от продажи полок всех видов в течение месяца. Поскольку в этой задаче прибыль может быть определена как разность между ценой (Ц1, Ц2, Ц3) и себестоимостью (С1, С2, С3), то ЦФ имеет вид

III этап построения модели заключается в задании ограничений, моделирующих условия задачи. Все ограничения рассматриваемой задачи можно разделить на несколько типов.

Ограничения по фонду времени (с использованием трудоемкости работ)

Левая часть ограничений по фонду времени представляет собой время, затрачиваемое на производство полок в течение месяца в количестве , ,  штук. Правая часть ограничения – это фонд рабочего времени исполнителя работы (рабочего или автомата) за смену. Неравенство (2.2) описывает ограничение по фонду времени на выполнение столярных работ. Коэффициент 4 ч/шт. (Тр1) – это время, затрачиваемое на столярные работы при производстве одной полки типа А (трудоемкость); 40 чел. (Р1) – это количество столяров, участвующих в производстве; 8  – количество часов работы одного человека в течение смены; 1 см./дн. – количество смен в одном рабочем дне; 22 дн./мес . – количество рабочих дней в месяце (табл.2.1):

(2.2)

Примечание 2.2. Важным моментом проверки правильности составления ограничений является проверка совпадения единиц измерения левой и правой частей ограничения. В ограничении (2.2) левая и правая части измеряются в часах, потраченных на выпуск продукции в течение месяца.

Аналогично записывается ограничение (2.3) по фонду времени на упаковочные работы, в котором 14 чел. (Р2) – это количество упаковщиков:

(2.3)

Ограничения по фонду времени (с использованием производительности работ)

Неравенство (2.4) описывает ограничение по фонду времени на покрытие лаком полок типа А. Отличие ограничений, учитывающих данные о производительности работ, от ограничений, учитывающих данные о трудоемкости работ, состоит в том, что производительность необходимо преобразовать в трудоемкость. Трудоемкость является величиной, обратной производительности. Коэффициент  () при  в (2.4) – это количество часов, приходящихся на покрытие лаком одной полки типа А. При записи правой части ограничения учитываем, что автомат, выполняющий покрытие лаком, работает не полную смену (8 ч), а в течение сменного фонда времени 7 ч (ФВ1). Это связано с необходимостью подготовки автомата к работе и обслуживанием его после окончания работы.

(2.4)

Неравенство (2.5) описывает ограничение по фонду времени на резку стекла для полок типа А и В2:

(2.5)

Неравенство (2.6) описывает ограничение по фонду времени на производство комплектующих полок типа В1 и В2:

(2.6)

Ограничения по запасу расходуемых в производстве материалов

(по запасу используемых для производства полок деталей)

Неравенство (2.7) описывает ограничение по запасу листов ДСП, поставляемых на комбинат ежемесячно. При этом следует учесть, что из листа ДСП надо выкраивать комплекты (верхнюю и нижнюю стороны полок, 2 боковые стороны) для производства полок. Поэтому при задании ограничения имеет смысл ориентироваться не на количество листов ДСП, а на количество комплектов для полок [правая часть (2.7)], которые можно получить из имеющегося запаса ДСП. Но поскольку листы ДСП можно раскраивать различными способами и получать при этом различное количество деталей и комплектов, то обозначим месячный запас комплектов в правой части (2.7) как  и рассмотрим способ его численного определения позже. В левой части ограничения (2.7) задается количество комплектов (по одному на полку), необходимых на производство полок в течение месяца в объеме , :

(2.7)

Аналогично ограничению по ДСП неравенство (2.8.) – это ограничение по запасу задних стенок из ДВП для полок В1 и В2, а неравенство (2.9) – ограничение по запасу стекол для полок А и В2. В отличие от ДСП листы ДВП и листы стекла кроятся стандартным способом, и из каждого листа ДВП получается 14 (К1) задних стенок полок, а из каждого листа стекла получается 10 (К2) стекол. Ежемесячный запас листов ДВП и стекла составляет соответственно 230 (Z2) и 260 (Z3). При составлении левых частей ограничений (2.8) и (2.9) следует учесть, что на каждую полку В1 и В2 приходится по одной задней стенке, а на каждую полку А и В2 – по 2 стекла:

(2.8)

(2.9)

Ограничения по емкости вспомогательных помещений и рынка

Неравенство (2.10) является ограничением по количеству полок А, которые может вместить сушилка. В правой части (2.10) представлено количество полок, которые могут быть просушены в течение месяца (в день может быть просушено 50 (V1) полок):

(2.10)

Неравенство (2.11) описывает ограничение по количеству полок всех видов, которые может вместить склад готовой продукции. При этом правая часть (2.11) учитывает, что общая емкость склада уменьшена на 100 (Ост) полок, которые остались невывезенными с прошлого месяца. Кроме того, в течение месяца каждый день будет освобождаться по 40 (N) мест для полок:

(2.11)

Неравенство (2.12) описывает ограничение по примерной емкости рынка, равной 5300 (V3) полкам всех видов:

(2.12)

Ограничения по гарантированному заказу

Неравенство (2.13) показывает, что необходимо произвести как минимум 50 (З) заказанных полок В2, а возможно, и большее количество, но уже для свободной продажи:

(2.13)

Ограничения по соотношению объемов продаж различных товаров

Неравенство (2.14) показывает, что доля полок А и В2 в общем объеме полок, производимых для свободной продажи, должна составлять не менее 60% (Д). К такому выводу приводят результаты маркетинговых исследований. Поскольку из всех полок В2 в свободную продажу поступит лишь , то это учитывается при составлении ограничения (2.14), которое после алгебраических преобразований принимает вид (2.15).

(2.14)

(2.15)

Определение количества комплектов для полок В1 и В2

Рассмотрим подробно вопрос определения максимально возможного количества комплектов для полок В1 и В2, которое можно произвести из ежемесячного запаса ДСП. В зависимости от размеров листов ДСП ( мм) и габаритов полок ( мм) детали полок В1 и В2 можно выкроить различными способами. Рассмотрим три возможных варианта такого раскроя, представленные на рис.2.3 (затемненные участки – это неиспользованная площадь ДСП).

Согласно 1-му варианту из одного листа ДСП для полок В1 и В2 можно выкроить 19 деталей верхней или нижней стенок, а также 9 деталей боковых стенок. По 2-му варианту раскроя получаем 12 деталей верхней или нижней стенок и 36 деталей боковых стенок. По 3-му варианту раскроя получаем 16 деталей верхней или нижней стенок и 18 деталей боковых стенок. Обозначим количество листов ДСП, раскроенных в течение месяца: по 1-му варианту через  (лист./мес.); по 2-му варианту -  (лист./мес.); по 3-му варианту –  (лист./мес.). При производстве полок нам выгодно стремиться к такому раскрою листов ДСП, при котором из полученных деталей можно укомплектовать максимальное количество полок. Количество комплектов, получаемых из раскроенных деталей, мы ранее обозначили через. Таким образом, наша цель описывается целевой функцией

компл./мес.

Рис.2.3. Возможные варианты раскроя листов ДСП


Количество всех раскроенных листов ДСП не должно превышать 400 (
Z1), то есть ежемесячный запас их на складе:

лист./мес.

При этом, поскольку в каждый комплект входит одна верхняя и одна нижняя стенки, количество нижних и верхних стенок, получаемых при раскрое всех листов ДСП [левая часть (2.16)], должно быть не меньше чем :

(2.16)

Аналогичный смысл имеет ограничение (2.17), которое задает нижнюю границу количества боковых стенок полок:

(2.17)

После преобразования описанных неравенств получим модель задачи (2.18), позволяющую раскроить максимальное количество комплектов:

;

(2.18)

Таким образом, при решении задачи (2.18) симплекс-методом (например, в  MS Excel) переменная  непосредственно определяет значение ЦФ, а переменные ,  и  влияют на изменение значения ЦФ косвенно, через ограничения. Решив задачу (2.18) для варианта 0, мы получим значение правой части ограничения (2.7) Y=3387 компл, после чего сможем решить исходную задачу, модель которой имеет вид:

(2.19)

Решив задачу (2.19), получаем

шт./мес.,  шт./мес.,  шт./мес.,

руб./мес.,

(2.20)

то есть в текущем месяце необходимо произвести 1100 полок А и 120 полок В2, а производство полок В1 нецелесообразно. После реализации всех произведенных полок комбинат получит прибыль в размере 106 200 рублей.

2.4. ПРИМЕРНЫЕ ВОПРОСЫ НА ЗАЩИТЕ РАБОТЫ

1. Что такое распределительная задача, общая распределительная задача?

2. Что такое математическое и линейное программирование?

3. Какова общая форма записи модели ЛП?

4. Что такое допустимое и оптимальное решения?

5. Каковы основные этапы построения математической модели ЛП?

6. Каков экономический смысл и математический вид ЦФ задачи о производстве полок?

7. Как можно классифицировать ограничения задачи о полках по их экономическому смыслу?

8. Чем отличается построение ограничений, использующих данные о трудоемкости и производительности работ?

9. Объясните способ построения каждого конкретного ограничения задачи о полках.

10. Каким образом решается задача оптимального раскроя листов ДСП?

11. Каким образом единицы измерения параметров задачи используются для выявления ошибок построения ограничений?


2.5. ВАРИАНТЫ

Таблица 2.1

Исходные данные вариантов задач к лабораторной работе №2

12

1340

270

360

1,6

10

16

20

7

9

6

220

15

7,4

7,2

7,6

375

155

200

9

17

80

420

1900

35

40

11

870

230

350

6,4

7

14

16

14

2

8

140

14

7,3

7,1

7,5

420

140

270

11

9

30

340

3100

70

120

10

1300

260

340

2

9

15

18

30

10

5

210

13

7,0

7,7

7,4

385

175

210

18

16

25

410

4300

30

50

9

910

240

330

6

6

10

13

8

8

3

110

12

7,2

7,6

7,8

410

160

230

13

8

70

330

2700

65

140

8

1260

270

320

2,4

8

11

14

11

6

4

200

11

7,1

7,5

7,7

395

205

220

8

15

35

390

1400

38

60

7

950

230

310

5,6

5

8

9

25

3

7

120

10

7,7

7,4

7,6

350

180

290

12

7

60

320

1500

60

150

6

1220

260

240

2,8

7

10

11

9

13

4

190

9

7,6

7,3

7,5

405

195

230

7

14

45

380

2500

44

70

5

990

240

250

5,2

8

13

14

16

5

6

130

8

7,5

7,2

7,4

370

200

180

17

6

75

310

4000

55

160

4

1180

270

260

3,2

6

9

10

27

7

2

180

7

7,4

7,1

7,8

415

215

240

6

13

55

370

1100

72

80

3

1030

230

270

4,8

9

13

14

6

11

5

250

6

7,3

7,0

7,7

380

220

190

16

5

40

300

3000

50

170

2

1140

260

280

3,6

5

10

12

19

12

9

170

5

7,2

7,7

7,6

365

235

250

5

12

65

360

3700

67

90

1

1070

240

290

4,4

10

15

16

22

16

4

150

4

7,1

7,6

7,5

390

240

200

15

11

20

400

2000

45

110

0

1100

250

300

4

4

8

10

40

14

10

100

3

7

7,5

7,4

400

230

260

14

10

50

350

5300

40

100

№ вар.

D

w

h

Тр1

Тр2

Тр3

Тр4

Р1

Р2

Пp1

Пp2

Пp3

ФВ1

ФВ2

ФВ3

Z1

Z2

Z3

К1

К2

V1

V2

V3

N

Ост


Продолжение табл.2.1

12

9(A,B1)

84B2

195

126

146

249

186

187

3 варианта раскроя листов ДСП; 8 ч в смене; работа в 1 смену; 22 рабочих дня в месяце

11

13(B1,B2)

23B1,

20B2

230

207

214

276

287

246

10

59B1

38A,

62B2

180

143

162

224

214

202

9

46A

14A,

21B1

225

195

210

281

263

267

8

23(A,B2)

80B1

165

129

142

203

194

167

7

16(B1,B2)

24А

220

176

197

274

246

242

6

12B2

60В2

170

125

148

198

175

180

5

72A

40B1,

3B2

215

187

205

243

230

243

4

43(A,B1)

5A,

12B2

150

120

134

192

154

147

3

15(B1,B2)

10A,

18B1

200

164

178

284

190

206

2

10B1

15B1

145

125

133

213

149

158

1

15A

30А

210

150

170

256

202

224

0

60(A,B2)

50В2

205

142

160

295

182

220

№ вар.

Д

З

C1

C2

C3

Ц1

Ц2

Ц3


3. ЛАБОРАТОРНАЯ РАБОТА №2 (ЧАСТЬ
II)

“АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ ОДНОИНДЕКСНЫХ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ”

3.1. ЦЕЛЬ РАБОТЫ

Приобретение навыков анализа чувствительности задач ЛП на основе различных типов отчетов, выдаваемых Microsoft Excel, о результат поиска решения.

3.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

  1.  Для задачи, решенной в лабораторной работе №2 (часть I) , получите в Excel все типы отчетов по результатам поиска решения, необходимые для анализа чувствительности.
  2.  Проанализируйте задачу на чувствительность к изменениям параметров исходной модели.
  3.  Результаты анализа задачи на чувствительность внесите в общий отчет по лабораторной работе №2.

3.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [5,6,7]

3.3.1. Задачи анализа оптимального решения на чувствительность

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

Ограничения линейной модели классифицируются следующим образом (рис.3.1). Связывающие ограничения проходят через оптимальную точку, например (1) и (2). Несвязывающие ограничения не проходят через оптимальную точку, например (3), (4) и (5). Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным, а ресурс, представляемый несвязывающим ограничением, – недефицитным. Ограничение называют избыточным в том случае, если его исключение не влияет на область допустимых решений и, следовательно, на оптимальное решение, например, (5). Выделяют следующие три задачи анализа на чувствительность.

1. Анализ сокращения или увеличения ресурсов:

1) на сколько можно увеличить (ограничения типа ) или уменьшить (ограничения типа ) запас дефицитного ресурса для улучшения оптимального значения ЦФ?

2) на сколько можно уменьшить (ограничения типа ) или увеличить (ограничения типа ) запас недефицитного ресурса при сохранении полученного оптимального значения ЦФ?

2. Увеличение (уменьшение) запаса какого из ресурсов наиболее выгодно?

3. Анализ изменения целевых коэффициентов: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?

3.3.2. Графический анализ оптимального решения на чувствительность

Область допустимых решений задачи на рис.3.1 – многоугольник ОABCDE. Если связывающее ограничение (дефицитный ресурс) (2) передвигать до точки F, то это приведет к расширению области допустимых решений до многоугольника ОABCFE и к получению нового оптимального решения в точке F. При этом ограничение (2) станет избыточным. Новое решение (F) лучше прежнего (C), поскольку для пересечения с точкой F линия ЦФ должна пройти по направлению вектора (выходящего из начала координат и показывающего направление максимизации ЦФ) дальше точки С (рис.3.2).

              (3)

             (5)

              (2)      (4)

              В

        А        С

         F

         D  (1)

        О    Е

Рис.3.1. Исходная задача ЛП для графического анализа чувствительности


              (3)

        (5)

        (2)    (4)

              В

        А   С

          F

         (1)

        О    E

Рис.3.2. Анализ максимального изменения запаса

дефицитного ресурса (2) с целью улучшения оптимального решения

Таким образом, чтобы графически определить максимальное изменение запаса дефицитного ресурса, улучшающее оптимальное решение, необходимо передвигать соответствующую прямую в направлении улучшения ЦФ до тех пор, пока это ограничение не станет избыточным.

Графический анализ максимально возможного изменения запаса недефицитного ресурса показан на рис.3.3. Передвинем несвязывающее ограничение (3) до пересечения с оптимальным решением в точке С.

        (5)

         (4)

    (2)           (3)

         С

         F

          G       (1)

          D

        О    E

Рис.3.3. Анализ максимального изменения запаса

недефицитного ресурса (3), не изменяющего оптимальное решение С


Это соответствует уменьшению запаса недефицитного ресурса (3), который в оптимальной точке С исходной задачи (см. рис.3.1) расходовался не полностью. Областью допустимых решений станет многоугольник
OGCDE. Оптимальное решение останется прежним (точка С). Таким образом, чтобы графически определить максимальное изменение запаса недефицитного ресурса, не меняющее оптимального решения, необходимо передвигать соответствующую прямую до пересечения с оптимальной точкой.

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

.

То есть сначала наращивается запас ресурса, имеющего максимальное значение , затем – второе по величине и т.д.

Графический анализ изменения целевых коэффициентов (например, цен на производимую продукцию), не приводящих к изменению оптимального решения, проводится путем вращения линии ЦФ. При увеличении коэффициента ЦФ  или уменьшении коэффициента  целевая прямая на графике вращается вокруг оптимальной точки по часовой стрелке. Если  уменьшается или же увеличивается , то целевая прямая вращается вокруг оптимальной точки против часовой стрелки (рис.3.4).

Уменьшение цены 1 ()           (3)

или уменьшение 

цены 2 ()

       (2)       (4)

         Н        С         (5)

                  (1)

              J

             Увеличение

            цены 1 ()

         или уменьшение

                   цены 2 ()

Рис.3.4. Анализ изменения коэффициентов  и  ЦФ

Зафиксируем значение . Оптимальное решение в точке С не будет меняться при увеличении  до тех пор, пока целевая прямая не совпадет с прямой (2). Аналогично оптимальное решение в точке С не будет меняться при уменьшении  до тех пор, пока целевая прямая не совпадет с прямой (1).

При таких поворотах точка С будет оставаться оптимальной до тех пор, пока наклон целевой прямой не выйдет за пределы, определяемые наклоном прямых ограничений (1) и (2). Если целевая прямая выйдет за пределы наклона  (1) или (2), то оптимальной станет соответственно точка H или J.

Таким образом, нижний и верхний пределы изменения цены 1 определяются значениями коэффициента , при которых наклон целевой прямой совпадает соответственно с наклонами прямых ограничений (1) и (2).

3.3.3. Анализ оптимального решения на чувствительность в Excel

Проведем анализ чувствительности задачи о мебельном комбинате из лабораторной работы №2 (часть I). Для этого необходимо после запуска в Excel задачи на решение в окне "Результаты поиска решения" выделить с помощью мыши два типа отчетов: "Результаты" и "Устойчивость" (рис.3.5).

Рис.3.5. Выделение типов отчетов требуемых для анализа чувствительности

3.3.3.1. Отчет по результатам

Отчет по результатам состоит из трех таблиц (рис.3.6):

  1.  таблица 1 содержит информацию о ЦФ;
  2.  таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи;
  3.  таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.

Рис.3.6. Лист отчета по результатам

Если ресурс используется полностью (то есть ресурс дефицитный), то в графе "Статус" ("Состояние") соответствующее ограничение указывается как "связанное"; при неполном использовании ресурса (то есть ресурс недефицитный) в этой графе указывается "не связан". В графе "Значение" приведены величины использованного ресурса.

Для граничных условий (строки 24, 25, 26 на рис. 3.6) в графе "Разница" показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.

Таблица 3 отчета по результам дает информацию для анализа возможного изменения запасов недефицитных ресурсов при сохранении полученного оптимального значения ЦФ. Так, если на ресурс наложено ограничение типа , то в графе "Разница" дается количество ресурса, на которое была превышена минимально необходимая норма. Например, анализ строки 26 (см. рис. 3.6) отчета по результатам для задачи о мебельном комбинате показывает, что полок выпущено на 70 шт. больше, чем было заказано. То есть из 120 полок только 70 шт. пойдут в свободную продажу. Таким образом, можно дать следующий ответ на вопрос об изменении запаса недефицитного ресурса “Значение XB2”: обязательный заказ на производство полок В2 можно увеличить на 70 шт., то есть заказывать до 120 шт., и при этом оптимальное решение (2.20) задачи не изменится.

Если на ресурс наложено ограничение типа , то в графе "Разница" дается количество ресурса, которое не используется при реализации оптимального решения. Так, анализ строки 13 (см. рис. 3.6) отчета по результатам для задачи о мебельном комбинате показывает, что время столярных работ составило 4440 ч. Неизрасходованным остается 2640 ч из общего фонда времени, отведенного на столярные работы. Из этого следует, что запас недефицитного ресурса “Фонд времени по столярным работам” можно уменьшить на 2640 ч и это никак не повлияет на оптимальное решение (2.20). Отсюда следует, что количество столяров можно уменьшить на 15 человек

или перевести их на выпуск другой продукции.

Анализ строки 23 показывает, что общее количество выпускаемых полок составляет 1220 шт., что меньше предполагаемой емкости рынка на 4080 шт. То есть запас недефицитного ресурса “Емкость рынка” может быть уменьшен до 1220 полок и это никак не повлияет на оптимальное решение (2.20). Другими словами, уменьшение спроса до 1220 полок в месяц никак не скажется на оптимальных объемах выпуска полок.

На основании проведенного анализа можно сделать вывод о том, что существуют причины (ограничения), не позволяющие мебельному комбинату выпускать большее количество полок и получать большую прибыль. Проанализировать эти причины позволяет отчет по устойчивости.

3.3.3.2. Отчет по устойчивости

Отчет по устойчивости состоит из двух таблиц (рис.3.7).

Таблица 1 содержит информацию, относящуюся к переменным.

1. Результат решения задачи.

2. Нормированная стоимость, которая показывает, на сколько изменится значение ЦФ в случае принудительного включения единицы этой продукции в оптимальное решение. Например, в отчете по устойчивости для рассматриваемой задачи (см. рис.3.7) нормированная стоимость для полок В1 равна –20 руб./шт. (строка 5). Это означает, что если мы, несмотря на оптимальное решение (2.20), потребуем включить в план выпуска 1 полку В1, то новый план выпуска (; ; ) принесет нам прибыль 106 180 руб./мес., что на 20 руб. меньше, чем в прежнем оптимальном решении.

3. Коэффициенты ЦФ.

4. Предельные значения приращения целевых коэффициентов , при которых сохраняется первоначальное оптимальное решение. Например, допустимое увеличение цены на полки В1 равно 20 руб./шт., а допустимое уменьшение – практически не ограничено (строка 5 на рис.3.7). Это означает, что если цена на полки В1 возрастет более чем на 20 руб./шт., например станет равной 61 руб./шт., то оптимальное решение изменится: станет целесообразным выпуск В1 в количестве 70 шт. А если их цена будет снижаться вплоть до нуля, то оптимальное решение (2.20) останется прежним.

Примечание 3.1. При выходе за указанные в отчете по устойчивости пределы измения цен оптимальное решение может меняться как по номенклатуре выпускаемой продукции, так и по объемам выпуска (без изменения номенклатуры).

Рис.3.7. Отчет по устойчивости для задачи о мебельном комбинате

Таблица 2 (см. рис.3.7) содержит информацию, относящуюся к ограничениям.

1. Величина использованных ресурсов в колонке "Результ. значение".

2. Предельные значения приращения ресурсов . В графе "Допустимое Уменьшение" показывают, на сколько можно уменьшить (устранить излишек) или увеличить (повысить минимально необходимое требование) ресурс, сохранив при этом оптимальное решение. Рассмотрим анализ дефицитных ресурсов, так как анализ недефицитных ресурсов был дан в подразд.3.3.3.1. Анализируя отчет по результатам, мы установили, что существуют причины (ограничения), не позволяющие мебельному комбинату выпускать большее, чем в оптимальном решении, количество полок и получать более высокую прибыль. В рассматриваемой задаче (вариант 0) такими ограничениями являются дефицитные ресурсы “Емкость сушилки” и “Емкость склада готовой продукции”. Поскольку знак ограничений этих запасов имеет вид , то возникает вопрос, на сколько максимально должна возрасти емкость этих помещений, чтобы обеспечить увеличение выпуска продукции. Ответ на этот вопрос показан в графе "Допустимое Увеличение". Емкость сушилки имеет смысл увеличить самое большее на 70 полок, а емкость склада готовой продукции – на 80 полок. Это приведет к новым оптимальным решениям, увеличивающим прибыль по сравнению с (2.20). Дальнейшее увеличение емкостей сушилки и склада сверх указанных пределов не будет больше улучшать решение, т.к. уже другие ресурсы станут связывающими.

3. Ценность дополнительной единицы i-го ресурса (теневая цена) рассчитывается только для дефицитных ресурсов. После того как мы установили, что увеличение емкостей сушилки и склада приведет к новым планам выпуска, обеспечивающим более высокую прибыль, возникает следующий вопрос. Что выгоднее в первую очередь расширять: сушилку или склад? Ответ на этот вопрос дает графа "Теневая цена". Для емкости сушилки она равна 30 руб./шт., а для склада – 60 руб./шт. (см. рис.3.7), то есть каждая полка, которую дополнительно можно будет поместить в сушилку, увеличит прибыль на 30 руб., а каждая полка, которую дополнительно можно будет поместить на склад, увеличит прибыль на 60 руб. Отсюда вывод: в первую очередь выгодно увеличивать емкость склада готовой продукции.

3.4. ПРИМЕРНЫЕ ВОПРОСЫ НА ЗАЩИТЕ РАБОТЫ

1. Что такое связывающие, несвязывающие, избыточные ограничения; дефицитные и недефицитные ресурсы?

2. Каковы предпосылки и основные задачи анализа оптимального решения на чувствительность?

3. Как графически проводится анализ изменения запаса дефицитных ресурсов?

4*. Каким образом, опираясь на результаты графического анализа, можно численно рассчитать новый (улучшенный) запас дефицитного ресурса?

5. Как графически проводится анализ изменения запаса недефицитных ресурсов?

6*. Каким образом, опираясь на результаты графического анализа, можно численно рассчитать новый запас недефицитного ресурса?

7. Что такое ценность дополнительной единицы i-го ресурса?

8. Как проводится графический анализ изменения коэффициентов ЦФ?

9*. Как численно определить диапазон изменения коэффициентов ЦФ, не изменяющий оптимального решения?

10. Какую информацию о чувствительности оптимального решения задачи ЛП можно получить из отчета по результатам и отчета по устойчивости?

11. Проанализируйте на чувствительность задачу о производстве полок (согласно своему варианту)?

4. ЛАБОРАТОРНАЯ РАБОТА №3 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СТАНДАРТНАЯ ТРАНСПОРТНАЯ ЗАДАЧА”

4.1. ЦЕЛЬ РАБОТЫ

Приобретение навыков построения математических моделей стандартных транспортных задач ЛП и решения их в Microsoft Excel.

4.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Согласно номеру своего варианта выберите условие задачи.

2. Постройте модель задачи, включая транспортную таблицу.

3. Найдите оптимальное решение задачи в Excel и продемонстрируйте его преподавателю.

4. Оформите отчет по лабораторной работе, который должен содержать:

  •  титульный лист (см. рис.2.1);
  •  транспортную таблицу и модель задачи с указанием всех единиц измерения;
  •  результаты решения задачи с указанием единиц измерения.

4.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [1,2,3,4,6,7]

4.3.1. Стандартная модель транспортной задачи (ТЗ)

Задача о размещении (транспортная задача) – это РЗ, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям.

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

Исходные параметры модели ТЗ

  1.  n – количество пунктов отправления, – количество пунктов назначения.
  2.   – запас продукции в пункте отправления  () [ед. тов.].
  3.   – спрос на продукцию в пункте назначения  () [ед. тов.].
  4.   – тариф (стоимость) перевозки единицы продукции из пункта отправления  в пункт назначения  [руб./ед. тов.].

Искомые параметры модели ТЗ

1.  – количество продукции, перевозимой из пункта отправления  в пункт назначения  [ед. тов.].

2.  – транспортные расходы на перевозку всей продукции [руб.].

Этапы построения модели

  1.  Определение переменных.
  2.  Проверка сбалансированности задачи.
  3.  Построение сбалансированной транспортной матрицы.
  4.  Задание ЦФ.
  5.  Задание ограничений.

Транспортная модель

;

(4.1)

Целевая функция представляет собой транспортные расходы на осуществление всех перевозок в целом. Первая группа ограничений указывает, что запас продукции в любом пункте отправления должен быть равен суммарному объему перевозок продукции из этого пункта. Вторая группа ограничений указывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворить спрос на продукцию в этом пункте. Наглядной формой представления модели ТЗ является транспортная матрица (табл.4.1).


Таблица 4.1

Общий вид транспортной матрицы

Пункты

отправления,

Пункты потребления,

Запасы,

[ед. прод.]

Потребность

[ед. прод.]

Из модели (4.1) следует, что сумма запасов продукции во всех пунктах отправления должна равняться суммарной потребности во всех пунктах потребления, то есть

.

(4.2)

Если (4.2) выполняется, то ТЗ называется сбалансированной, в противном случае – несбалансированной. Поскольку ограничения модели (4.1) могут быть выполнены только при сбалансированной ТЗ, то при построении транспортной модели необходимо проверять условие баланса (4.2). В случае, когда суммарные запасы превышают суммарные потребности, необходим дополнительный фиктивный пункт потребления, который будет формально потреблять существующий излишек запасов, то есть

.

(4.3)

Если суммарные потребности превышают суммарные запасы, то необходим дополнительный фиктивный пункт отправления, формально восполняющий существующий недостаток продукции в пунктах отправления:

.

(4.4)

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

.

На практике возможны ситуации, когда в определенных направлениях перевозки продукции невозможны, например, по причине ремонта транспортных магистралей. Такие ситуации моделируются с помощью введения так называемых запрещающих тарифов . Запрещающие тарифы должны сделать невозможными, то есть совершенно невыгодными, перевозки в соответствующих направлениях. Для этого величина запрещающих тарифов должна превышать максимальный из реальных тарифов, используемых в модели:

.

4.3.2. Пример построения модели ТЗ

Пусть необходимо организовать оптимальные по транспортным расходам перевозки муки с двух складов в три хлебопекарни. Ежемесячные запасы муки на складах равны 79,515 и 101,925 т, а ежемесячные потребности хлебопекарен составляют 68,5, 29,5 и 117,4 т соответственно. Мука на складах хранится и транспортируется в мешках по 45 кг. Транспортные расходы (руб./т) по доставке муки представлены в табл.4.2. Между первым складом и второй хлебопекарней заключен договор о гарантированной поставке 4,5 т муки ежемесячно. В связи с ремонтными работами временно невозможна перевозка из второго склада в третью хлебопекарню.

Таблица 4.2

Транспортные расходы по доставке муки (руб./т)

Склады

Хлебопекарни

Х1

Х2

Х3

С1

350

190

420

С2

400

100

530

ТЗ представляет собой задачу ЛП, которую можно решать симплекс-методом, что и происходит при решении таких задач в Excel. В то же время существует более эффективный вычислительный метод – метод потенциалов, в случае применения которого используется специфическая структура условий ТЗ (4.1) и, по существу, воспроизводятся шаги симплекс-алгоритма. Исходя из этого, в лабораторной работе необходимо построить модель задачи вида (4.1), пригодную для ее решения методом потенциалов.


Определение переменных

Обозначим через  [меш.] количество мешков с мукой, которые будут перевезены с i-го склада в j-ю хлебопекарню.

Проверка сбалансированности задачи

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

  •  из запаса первого склада ;
  •  из потребности в муке второй хлебопекарни

Согласно условию задачи  мука хранится и перевозится в мешках по 45 кг, то есть единицами измерения переменных  являются мешки муки. Но запасы муки на складах и потребности в ней магазинов заданы в тоннах. Поэтому для проверки баланса и дальнейшего решения задачи приведем эти величины к одной единице измерения – мешкам. Например, запас муки на первом складе равен 75,015 т/мес., или, а потребность первой хлебопекарни составляет 68 т/мес., или  Округление при расчете потребностей надо проводить в большую сторону, иначе потребность в муке не будет удовлетворена полностью.

Для данной ТЗ имеет место соотношение

.

Ежемесячный суммарный запас муки на складах меньше суммарной потребности хлебопекарен на 4677-3932=745 мешков муки, откуда следует вывод: ТЗ не сбалансирована.

Построение сбалансированной транспортной матрицы

Сбалансированная транспортная матрица представлена в таблице 4.3. Стоимость перевозки муки должна быть отнесена к единице продукции, то есть к 1 мешку муки. Так, например, тариф перевозки из первого склада в третий магазин равен

Для установления баланса необходим дополнительный фиктивный склад, то есть дополнительная строка в транспортной таблице задачи. Фиктивные тарифы перевозки зададим таким образом, чтобы они были дороже реальных тарифов, например, 50,00 руб./меш.

Невозможность доставки грузов со второго склада в третью хлебопекарню задается в модели с помощью запрещающего тарифа, который должен превышать величину фиктивного тарифа, например,  руб./меш.

Таблица 4.3

Транспортная матрица задачи

Хлебопекарни

Запас, мешки

Склады

Х1

Х2

Х3

С1

15,75

8,55

18,90

1667

С2

18,00

4,50

100,00

2265

Сф

50,00

50,00

50,00

745

Потребность, мешки

1512

556

2609

4677

Задание ЦФ

Формальная ЦФ, то есть суммарные затраты на все возможные перевозки муки, учитываемые в модели, задается следующим выражением:

(4.5)

При этом следует учитывать, что вследствие использования фиктивных тарифов реальная ЦФ (то есть средства, которые в действительности придется заплатить за транспортировку муки) будет меньше формальной ЦФ (4.5) на стоимость найденных в процессе решения фиктивных перевозок.

Задание ограничений

(меш./мес.)

4.4. ВАРИАНТЫ

Постановка задачи

На складах хранится мука, которую необходимо завезти в хлебопекарни. Номера складов и номера хлебопекарен выбираются в соответствии с вариантами табл.4.4. Текущие тарифы перевозки муки [руб./т], ежемесячные запасы муки [т/мес.] на складах и потребности хлебопекарен в муке [т/мес.] указаны в табл.4.5.

При этом необходимо учитывать, что из-за ремонтных работ временно нет возможности перевозить муку с некоторых складов в некоторые хлебопекарни. В табл.4.4 это показано в графе "Запрет перевозки" в формате № склада  хлебопекарни. Например, «2x3» обозначает, что нельзя перевозить муку со склада №2 в хлебопекарню №3.

Кроме того, необходимо учесть, что некоторые хлебопекарни имеют договоры на гарантированную поставку муки с определенных складов. В табл.4.4 это показано в графе "Гарантированная поставка" в формате № склада x № хлебопекарни = объем поставки. Например, «1x4=40» обозначает, что между складом №1 и магазином №4 заключен договор на обязательную поставку 40 т муки.

Необходимо организовать поставки наилучшим образом, учитывая, что мука хранится и транспортируется в мешках весом по 50 кг.

Таблица 4.4

Номера складов, хлебопекарен, запрещенные и гарантированные поставки

№ Варианта

№ Складов

№ Хлебопекарен

Запрет перевозки

Гарантированная

поставка, т/мес.

1

1, 2, 3

1, 2, 3, 4

2x2, 3x4

3x3=50

2

2, 3, 4, 5

1, 2, 5

2x2, 3x5

3x2=40

3

1, 2, 4

1, 2, 3, 5

1x5, 2x3

4x3=45

4

1, 2, 3, 4

3, 4, 5

3x3, 4x5

3x5=40

5

1, 2, 5

2, 3, 4, 5

1x4, 5x3

1x5=60

6

1, 2, 3, 5

2, 3, 5

5x5, 2x2

3x5=30

7

2, 3, 4

2, 3, 4, 5

3x3, 2x5

4x3=45

8

1, 2, 3, 5

1, 2, 4

1x2, 5x4

3x2=20

9

2, 3, 5

1, 2, 3, 5

5x1, 3x5

5x2=30

10

2, 3, 4, 5

2, 3, 4

5x4, 3x2

4x3=35

11

3, 4, 5

1, 2, 3, 4

3x4, 5x1

4x1=40

12

1, 2, 3, 4

1, 2, 3

3x2, 4x1

2x2=50


Таблица 4.5

Запасы, потребности и тарифы перевозок

Склады

Хлебопекарни

1

2

3

4

5

Запас, т/мес.

1

400

600

800

200

200

80

2

300

100

500

600

500

70

3

500

200

100

600

300

60

4

300

700

200

400

900

55

5

200

500

800

200

400

65

Спрос, т/мес.

77,86

56,78

58,88

62,44

73,92

4.6. ПРИМЕРНЫЕ ВОПРОСЫ НА ЗАЩИТЕ РАБОТЫ

1. Что такое задача о размещении?

2. Какова постановка стандартной ТЗ?

3. Запишите математическую модель ТЗ.

4. Перечислите исходные и искомые параметры модели ТЗ.

5. Какова суть каждого из этапов построения модели ТЗ?

6. Раскройте понятие сбалансированности ТЗ.

7. Что такое фиктивные и запрещающие тарифы?

8. В каком соотношении должны находиться величины фиктивных и запрещающих тарифов при необходимости их одновременного использования в транспортной модели?

5. ЛАБОРАТОРНАЯ РАБОТА №4 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ЗАДАЧА О НАЗНАЧЕНИЯХ”

5.1. ЦЕЛЬ РАБОТЫ

Приобретение навыков построения математических моделей задач о назначении и решения этих задач в Microsoft Excel.

5.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Согласно номеру своего варианта выберите условие задачи.

2. Постройте модель задачи, включая транспортную таблицу.

3. Найдите оптимальное решение задачи с помощью Excel и представьте его преподавателю.

4. Оформите отчет по лабораторной работе, который должен содержать:

  •  титульный лист (см. рис.2.1);
  •  транспортную таблицу и модель задачи с указанием всех единиц измерения;
  •  результат решения задачи с указанием единиц измерения.

5.3. ЗАДАЧА О НАЗНАЧЕНИЯХ. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ [1,3,6,7]

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

Исходные параметры модели задачи о назначениях

1. n – количество ресурсов, – количество работ.

2.  – единичное количество ресурса  (), например: один работник; одно транспортное средство; одна научная тема и т.д.

3.  – единичное количество работы  (), например: одна должность; один маршрут; одна лаборатория.

4.  – характеристика качества выполнения работы  с помощью ресурса . Например, компетентность i-го работника при работе на j-й должности; время, за которое i-е транспортное средство перевезет груз по j-му маршруту; степень квалификации i-й лаборатории при работе над j-й научной темой.

Искомые параметры

1.  – факт назначения или неназначения ресурса  на работу :

2.  – общая (суммарная) характеристика качества распределения ресурсов по работам.

Таблица 5.1

Общий вид транспортной матрицы задачи о назначениях

Ресурсы,

Работы,

Количество ресурсов

1

1

1

Количество работ

1

1

1

Модель задачи о назначениях

;

(5.1)

Специфическая структура задачи о назначениях позволила разработать так называемый "Венгерский метод" ее решения. Поэтому, хотя в Excel такие задачи решаются обычным симплекс-методом, в лабораторной работе требуется построить модель задачи о назначениях вида (5.1). В некоторых случаях, например, когда  – это компетентность, опыт работы, или квалификация работников, условие задачи может требовать максимизации ЦФ, в отличие от (5.1). В этом случае ЦФ  заменяют на  и решают задачу с ЦФ , что равносильно решению задачи с ЦФ .

5.4. ПОСТАНОВКА ЗАДАЧИ О НАЗНАЧЕНИЯХ

Отдел кадров предприятия устроил конкурсный набор специалистов на две вакантные должности. На эти новые места (НМ) претендуют 3 прежних сотрудника (ПС), уже работающие в других отделах, и 4 новых сотрудника (НС). Номера новых сотрудников, новых и прежних мест выбираются по вариантам из табл.5.2. Номера прежних мест являются номерами прежних сотрудников.

Отдел кадров оценил по десятибалльной шкале компетентность новых сотрудников (табл.5.3) и прежних сотрудников (табл.5.4) для работы и на новых местах, и на прежних местах (ПМ), то есть занимаемых прежними сотрудниками. Необходимо учесть, что руководство предприятия, во-первых, предпочитает, чтобы прежние сотрудники не претендовали на места друг друга, и, во-вторых, не намерено увольнять прежних сотрудников.

Необходимо распределить сотрудников по должностям наилучшим образом.

5.5. РЕКОМЕНДАЦИИ К РЕШЕНИЮ ЗАДАЧИ О НАЗНАЧЕНИЯХ

1. Процесс приведения задачи о назначениях к сбалансированному виду имеет свои особенности по сравнению с ТЗ. Если условие сбалансированности задачи (4.2) не выполняется из-за нехватки работ или исполнителей в количестве , то для создания баланса надо ввести такое же количество  фиктивных строк или столбцов.

2. Особенностью решения данной задачи является моделирование системы предпочтений, сложившейся у руководства предприятия по описанному в условии задачи кадровому вопросу.

3. В задаче о назначениях увольнение прежнего сотрудника или непринятие на работу нового сотрудника моделируется попаданием единицы в фиктивный столбец матрицы решений задачи, поэтому для запрещения или разрешения таких ситуации необходимо использовать соответствующие "тарифы".

4. Значения "тарифов"  выбираются в зависимости от направления оптимизации ЦФ задачи о назначениях ( или ). При этом руководствуются принципом "невыгодности" запрещенных назначений. Так, если  – это общая компетентность работников, то в качестве запрещающих надо выбирать нулевые компетентности . А если  – это общее время прохождения машинами транспортных маршрутов, то в качестве запрещающих надо выбирать значения , превосходящие по величине максимальные реальные значения .

5. При решении задач о назначении в Excel необходимо учитывать, что переменные  являются булевыми.

5.4. ВАРИАНТЫ

Таблица 5.2

Номера сотрудников и мест их работы для конкретного варианта

№ варианта

Новые сотрудники

(НС)

Места работы прежних сотрудников (ПМ)

Новые места

(НМ)

1

3, 4, 7, 8

1, 2, 3

1, 2

2

1, 2, 5, 6

2, 5, 6

2, 3

3

5, 6, 7, 8

1, 2, 5

3, 4

4

3, 4, 5, 6

4, 5, 6

1, 4

5

1, 2, 3, 4

2, 3, 4

2, 4

6

2, 4, 6, 8

3, 4, 6

1, 3

7

1, 3, 5, 7

2, 3, 6

1, 4

8

2, 3, 6, 7

3, 4, 5

2, 3

9

1, 4, 5, 8

2, 3, 5

3, 4

10

2, 3, 4, 5

1, 2, 6

1, 2

11

4, 5, 6, 7

1, 3, 5

2, 4

12

1, 2, 7, 8

2, 4, 6

1, 3


Таблица 5.3

Компетентность новых сотрудников

НМ1

НМ2

НМ3

НМ4

ПМ1

ПМ2

ПМ3

ПМ4

ПМ5

ПМ6

НС1

6

5

7

6

5

6

7

6

7

5

НС2

5

5

8

8

7

6

4

5

8

8

НС3

6

7

5

6

4

5

4

5

6

6

НС4

7

8

7

6

5

7

6

8

5

5

НС5

7

6

6

5

5

4

5

5

4

6

НС6

8

8

9

7

6

7

8

7

9

8

НС7

9

8

9

9

8

7

8

9

8

7

НС8

7

7

8

9

7

8

9

6

7

8

Таблица 5.4

Компетентность прежних сотрудников

НМ1

НМ2

НМ3

НМ4

Занимаемое место

ПС1

7

6

6

7

7

ПС2

8

9

7

7

8

ПС3

6

5

6

6

6

ПС4

7

9

6

8

8

ПС5

8

7

8

8

7

ПС6

4

5

6

4

5

5.5. ПРИМЕРНЫЕ ВОПРОСЫ НА ЗАЩИТЕ РАБОТЫ

1. Какова постановка задачи о назначениях?

2. В чем отличие модели задачи о назначениях от модели ТЗ?

3. Каковы исходные и искомые параметры задачи о назначениях?

4. Запишите математическую модель задачи о назначениях.

5. Как записать модель задачи о назначениях, подразумевающую максимизацию ЦФ, в виде (5.1)?

6. Каким образом в модели задачи о назначениях можно запретить конкретное назначение?

7. В чем особенности процесса приведения задачи о назначениях к сбалансированному виду?

8. Поясните модель задачи о назначениях, построенную по заданному варианту.


6. ЛАБОРАТОРНАЯ РАБОТА №5 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ОРГАНИЗАЦИЯ ОПТИМАЛЬНОЙ СИСТЕМЫ СНАБЖЕНИЯ”

6.1. ЦЕЛЬ РАБОТЫ

Приобретение навыков адаптации транспортной модели ЛП для оптимизации системы снабжения, допускающей транзитные перевозки.

6.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Согласно номеру своего варианта, выберите условие задачи.

2. Постройте транспортные таблицы для каждой подзадачи.

3. Решите в Excel все подзадачи, сделайте выбор оптимальной системы снабжения и представьте результаты преподавателю.

4. Оформите отчет по лабораторной работе, который должен содержать:

  •  титульный лист (см. рис.2.1);
  •  транспортные таблицы всех подзадач и результаты их решения;
  •  вывод о том, какая из систем снабжения является оптимальной.

6.3. ПОСТАНОВКА ЗАДАЧИ

По заказу пяти потребителей А, Б, В, Г, Д на четырех предприятиях-изготовителях производится продукция. В процессе доставки к потребителям продукция может храниться на трех оптовых базах. Существуют следующие три способа организации снабжения потребителей продукцией:

  1.  ИЗГОТОВИТЕЛЬ  ОПТОВАЯ БАЗА  ПОТРЕБИТЕЛЬ,

то есть вся продукция, произведенная изготовителями, сначала складируется на оптовых базах и только потом развозится потребителям;

  1.  ИЗГОТОВИТЕЛЬ  ПОТРЕБИТЕЛЬ,

то есть вся продукция, произведенная изготовителями, напрямую доставляется потребителям, минуя оптовые базы;

  1.  ИЗГОТОВИТЕЛЬ     ОПТОВАЯ БАЗА

              ПОТРЕБИТЕЛЬ,

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

Необходимо выбрать оптимальный способ организации снабжения потребителей продукцией предприятий-изготовителей.

6.4. РЕКОМЕНДАЦИИ К РЕШЕНИЮ ЗАДАЧИ

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

2. При моделировании различных систем снабжения необходимо учитывать следующее. В транспортной таблице системы 1 и в транспортной таблице системы 3 пунктами отправления являются как изготовители, так и оптовые базы; пунктами потребления являются как потребители, так и оптовые базы. Транспортные таблицы систем 1 и 3 отличаются расстановкой реальных и запрещающих тарифов (см. подразд.4.3.1).

6.5. ВАРИАНТЫ

Ежемесячный спрос на продукцию [шт.], емкость оптовых баз [шт.] и тарифы [руб./шт.] за доставку продукции с оптовых баз к потребителям приведены в табл.6.1. Ежемесячные объемы производства [шт.], емкость оптовых баз [шт.] и суммарные затраты [руб./шт.] на производство и доставку продукции от изготовителей к оптовым базам приведены в табл.6.2. Ежемесячные объемы производства [шт.], спрос на продукцию [шт.] и суммарные затраты [руб./шт.] на производство и доставку продукции от изготовителей к потребителям приведены в табл.6.3. Номер варианта состоит из двух цифр. Первая цифра (0 или 1) выбирается в табл.6.1 и 6.3 по вертикали, а в табл.6.2 – по горизонтали. Вторая цифра (0, 1, 2, 3, 4, 5, 6) выбирается в табл.6.1 и 6.3 по горизонтали, а в табл.6.2 – по вертикали. Таким образом, номера вариантов имеют вид 01, 02, …, 06, 11, 12, …, 16.

Таблица 6.1

Параметры перевозок из оптовых баз к потребителям

Потр-ль А

Потр-ль Б

Потр-ль В

Потр-ль Г

Потр-ль Д

Запас

Вариант

Вариант

Вариант

Вариант

Вариант

0

1

0

1

0

1

0

1

0

1

Оптовая  база  1

В а р и а н т

1

15

18

12

12

11

14

10

16

20

14

300

2

12

20

32

28

14

25

22

19

36

40

540

3

20

12

15

10

28

20

30

22

17

11

720

4

20

35

32

25

36

18

20

34

25

15

620

5

14

20

25

14

18

22

15

30

21

14

560

6

22

14

20

10

25

32

30

35

24

18

780

Оптовая  база  2

В а р и а н т

1

20

10

14

16

25

30

24

32

15

24

420

2

16

15

20

11

31

18

20

40

17

30

380

3

21

28

12

20

24

35

15

21

24

45

460

4

16

16

27

14

20

20

21

25

28

38

350

5

15

31

34

20

14

15

18

30

20

22

410

6

14

30

10

26

18

16

24

36

34

25

450

Оптовая  база  3

В а р и а н т

1

12

20

36

18

20

27

16

18

36

35

730

2

16

12

26

10

32

42

34

14

10

16

690

3

20

15

20

16

36

28

30

20

18

10

620

4

18

28

15

26

28

31

18

40

20

27

580

5

15

24

35

35

40

34

10

35

35

40

740

6

22

32

28

14

25

20

35

24

20

35

610

Спрос на товар

600

480

550

750

420

360

780

200

400

180


6.6. ЗАЩИТА РАБОТЫ

Защита работы заключается в пояснении:

  •  транспортных таблиц каждого способа организации перевозок;
  •  результатов решения задачи.


Таблица 6.2

Параметры перевозок от изготовителей к оптовым базам

Произ-во

510

480

620

570

660

280

420

390

450

Оптовая база 3

В А Р И А Н Т

6

22

12

12

31

21

14

20

12

610

5

17

10

31

18

19

30

11

18

740

4

25

18

17

26

10

21

25

25

580

3

20

24

21

30

15

10

19

36

620

2

27

30

36

18

30

18

15

32

690

1

31

28

25

24

27

27

20

21

730

Оптовая база 2

В А Р И А Н Т

6

16

8

7

6

14

10

27

20

450

5

12

19

17

20

24

15

12

14

410

4

8

17

15

16

19

21

18

10

350

3

9

12

20

9

10

19

11

19

460

2

14

20

14

10

18

12

15

27

380

1

10

7

21

14

22

17

20

16

420

Оптовая база 1

В А Р И А Н Т

6

10

11

30

21

6

13

19

18

780

5

24

12

17

29

9

10

7

11

560

4

20

30

28

10

20

18

15

9

620

3

12

29

24

14

26

22

28

14

720

2

18

25

19

27

7

7

10

25

540

1

27

14

15

20

11

15

26

20

300

Вариант

0

1

0

1

0

1

0

1

Запас

Изг-ль

Изг-ль 1

Изг-ль 2

Изг-ль 3

Изг-ль 4


Таблица 6.3

Параметры перевозок от изготовителей к потребителям

Потр-ль А

Потр-ль Б

Потр-ль В

Потр-ль Г

Потр-ль Д

Произ-во

Вариант

Вариант

Вариант

Вариант

Вариант

0

1

0

1

0

1

0

1

0

1

Изготовитель 1

В а р и а н т

1

10

2

2

12

1

14

10

6

20

14

510

2

26

37

12

45

10

24

39

14

35

42

200

3

11

28

6

10

18

20

22

34

16

14

550

4

25

8

12

17

5

40

25

32

38

30

720

5

24

14

27

40

48

35

21

30

12

40

200

6

16

24

14

30

42

50

35

22

30

52

420

Изготовитель 2

В а р и а н т

1

24

8

18

30

20

35

14

40

26

30

400

2

10

12

50

58

8

58

20

58

48

26

800

3

32

16

45

34

10

16

32

8

25

16

250

4

26

35

42

52

35

30

30

22

38

20

480

5

16

20

30

38

26

48

50

50

48

52

900

6

20

12

48

44

30

22

25

18

15

20

420

Изготовитель 3

В а р и а н т

1

32

28

54

40

16

28

28

24

10

20

460

2

10

30

60

30

20

35

38

50

44

28

650

3

8

24

25

21

52

42

50

48

48

22

800

4

15

40

38

28

25

10

20

15

12

10

160

5

18

37

16

32

40

35

9

10

25

16

360

6

26

34

20

46

45

30

14

26

24

10

480

Изготовитель 4

В а р и а н т

1

16

41

30

17

55

45

45

50

46

30

790

2

24

30

24

35

23

28

38

30

30

25

510

3

30

25

37

20

30

32

35

28

25

9

560

4

16

20

18

33

48

50

48

52

50

20

800

5

22

36

10

42

36

48

40

48

45

24

700

6

28

40

40

25

18

20

28

16

18

15

400

Спрос на товар

600

480

550

750

420

360

780

200

400

180

7. ЛАБОРАТОРНАЯ РАБОТА №6 “ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛП. ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПРОИЗВОДСТВЕННЫХ МОЩНОСТЕЙ”

7.1. ЦЕЛЬ РАБОТЫ

Приобретение навыков решения двухиндексной общей распределительной задачи ЛП и ее применения к оптимальному распределению производственных мощностей.

7.2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Согласно номеру своего варианта выберите условие задачи.

2. Постройте распределительную таблицу для варианта производства без специализации и преобразуйте ее в транспортную таблицу.

3. Решите в Excel полученную транспортную задачу и преобразуйте полученное решение в решение распределительной задачи.

4. Проанализируйте результаты организации производства без специализации и примите решение о том, какой корпус будет специализироваться на выпуске какого вида продукции.

5. Решите вторую подзадачу для варианта производства со специализацией аналогично первой подзадаче (п.1–4).

6. Сделайте выбор оптимального распределения производственных мощностей (со специализацией или без специализации) на основании результатов решения обеих подзадач.

7. Оформите отчет по лабораторной работе, который должен содержать:

  •  титульный лист (см. рис.2.1);
  •  распределительные и транспортные таблицы обеих подзадач с указанием единиц измерения;
  •  результаты решения каждой подзадачи;
  •  вывод о том, какой из вариантов распределения производственных мощностей является оптимальным.

7.3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

Исходные параметры модели двухиндексной общей РЗ

1. n – количество исполнителей (станков, работников, транспортных средств и т.д.), – количество видов работ (выпускаемой продукции, выполняемых заданий, перевозимых товаров и т.д.).

2.  – запас рабочего ресурса исполнителя  () (фонд времени работы оборудования или работника; количество транспортных средств и т.д.), пример единиц измерения [ед. t].

3.  – план по выполнению работы  ()(объем выпуска продукции; объем выполнения заданий; потребность в перевозимом товаре и т.д.), пример единиц измерения [ед. тов].

4.  – тариф (стоимость) выполнения работы  исполнителем  (себестоимость единицы выпуска продукции; затраты на выполнение одного задания; тарифы перевозки единицы товара), пример единиц измерения [руб./ед. тов.].

5.  – интенсивность выполнения работы  исполнителем  (производительность выпуска продукции, выполнения заданий; вместимость транспортного средства и т.д.), пример единиц измерения [ед. тов./ед. t].

Искомые параметры модели РЗ

1.  – загруженность исполнителя  при выполнении работы  (время, затрачиваемое на выпуск продукции или на выполнение заданий; количество транспортных средств определенного вида, задействованных в перевозке), пример единиц измерения [ед. t].

2.  – количество работ , которые должен будет произвести исполнитель  (объем выпущенной продукции, выполненных заданий, перевезенных товаров и т.д.), пример единиц измерения [ед. тов.].

3.  – общие расходы на выполнение всего запланированного объема работ, пример единиц измерения [руб.].

Этапы построения модели

I. Определение переменных.

II. Построение распределительной матрицы (табл.7.1).

III.Задание ЦФ.

IV. Задание ограничений.

Таблица 7.1

Общий вид распределительной матрицы

Исполнители,

Работы,

Запас ресурса

[ед.ресурса]

План [ед.работы]


Модель двухиндексной общей РЗ

;

(7.1)

Таким образом, формально модель общей РЗ отличается от модели ТЗ использованием параметра интенсивности выполняемых работ  в ЦФ и для задания ограничений по выполняемым работам (столбцам).

Этапы решения РЗ

I. Преобразование РЗ в ТЗ:

1) выбор базового ресурса и расчет нормированных производительностей ресурсов ;

(7.2)

2) пересчет запаса рабочего ресурса исполнителей ;

ед. t

(7.3)

3) пересчет планового задания ;

(7.4)

4) пересчет себестоимостей работ;

(7.5)

II. Проверка баланса пересчитанных параметров  и построение транспортной матрицы.

III. Поиск оптимального решения ТЗ.

IV. Преобразование оптимального решения ТЗ  в оптимальное решение РЗ , причем переход  выполняется по формуле (7.6):

ед. t

(7.6)

где  и  – соответственно элементы решения РЗ и ТЗ.

V. Определение количества работ , соответствующее оптимальному решению РЗ :

(7.7)

VI. Определение ЦФ распределительной задачи (см. подразд.7.1).

7.4. ПОСТАНОВКА ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ПРОИЗВОДСТВЕННЫХ МОЩНОСТЕЙ

На АО “Светлана” подготовлены к серийному производству 5 новых изделий , , , , , оптовые цены  которых равны соответственно (46, 27, 40, 35, 23) [руб./шт.]. Производство может быть развёрнуто в четырёх сборочных корпусах , , , . Затраты в рублях на изготовление j-го изделия в i-м корпусе задаются матрицей . Предлагается специализировать один (несколько) сборочный корпус, для чего потребуется его дополнительное переоборудование. Затраты на переоборудование в тыс.руб. задаются матрицей .

(руб./шт.); (тыс.руб.).

При выпуске изделий со специализацией затраты  упадут на 15–20% в каждом корпусе. Фонды времени  работы корпусов в плановом периоде равны соответственно 550, 870, 620, 790 часов, план выпуска продукции  в штуках составляет соответственно 6400, 8700, 16 400, 4800, 4600, а трудоёмкость в минутах изготовления одной единицы продукции в соответствующем корпусе задается матрицей .

(мин/шт.).

Рассмотрите два варианта работы предприятия: без специализации и со специализацией. Выберите наилучший вариант и обоснуйте свой выбор.

7.5. ПОСТРОЕНИЕ И РЕШЕНИЕ РЗ ЛП

Построение распределительной модели

Пусть  – количество времени (ч), которое корпус  будет тратить на выпуск изделия  в течение планового периода.

Производство без специализации

Рассмотрим производство без специализации корпусов. Распределительная матрица такой задачи приведена в табл.7.2.

Таблица 7.2

Распределительная матрица задачи без специализации

Корпуса,

Изделия,

Фонд

времени [ч]

20

8

120

19

30

7

15

21

10

9

550

16,66

43

100

12

25

40

12,50

26

8,33

15

870

10

9

60

18

15

23

7,50

27

5

20

620

8,33

21

50

16

12,50

22

6,25

13

4,17

21

790

План [шт.]

6400

8700

16 400

4800

4600

При ее построении необходимо учитывать, что параметр интенсивности выполнения работ  в данном случае – это производительность корпуса  по выпуску изделия . Но в исходных данных вместо  дано количество минут, затрачиваемых в корпусе  на производство одного изделия , то есть трудоемкость . Производительность и трудоемкость по своему смыслу – обратные величины, то есть

.

(7.8)

Например, на производство изделия  в корпусе  требуется 0,5 минуты, поэтому в течение часа (60 мин) будет произведено120 изделий:

.

Примечание 7.1При решении РЗ в Excel можно обойтись без округлений промежуточных значений всех параметров задачи. Для этого расчет этих значений необходимо производить прямо в соответствующих ячейках. Например, в ячейку для  вместо округленного числа 8,333 надо ввести выражение . Результаты решения рассматриваемой задачи (, , , ) получены в Excel без округления промежуточных вычислений.

На основании распределительной табл.7.2 строим модель РЗ – ЦФ (приведены округленные значения) и ограничения:

(7.9)

Преобразуем РЗ в ТЗ. В качестве базового корпуса можно выбрать любой, но мы предпочтем корпус с максимальной производительностью, то есть корпус . По формуле (7.2) определим производительности корпусов , нормированные относительно производительности базового станка:

;

;

; .

Пересчитаем фонды времени корпусов по формуле (7.3):

[ч];  [ч];  [ч];

[ч].

Пересчитаем плановое задание по формуле (7.4):

[ч]; [ч];  [ч];

[ч];  [ч]

.

Пересчет себестоимостей производим по формуле (7.5), например:

 [руб./ч];  [руб./ч];

 [руб./ч];  [руб./ч]

.

Все пересчитанные параметры РЗ сведены в транспортную матрицу задачи без специализации (табл.7.3). Перед записью этой матрицы надо проверить сбалансированность полученной ТЗ, то есть условие

.

В данной задаче условие баланса не выполняется, так как 1914,167>1719,167, то есть

.

Это означает, что фонды времени корпусов позволяют произвести больше продукции, чем это предусмотрено плановым заданием. Для получения баланса добавим в транспортную таблицу фиктивный столбец  с плановым заданием

 [ч]

и фиктивными тарифами  [руб./ч], превосходящими по своему значению все реальные тарифы  полученной ТЗ.

Таблица 7.3

Транспортная матрица задачи без специализации

Корпуса,

Изделия,

 [ч]

Иф

160

2280

210

315

90

10 000

940

860

1440

1200

390

150

10 000

141,61

180

2160

690

405

200

10 000

275

420

1920

660

195

210

10 000

282,88

[ч]

300

81,667

580

346,667

38,334

195

1914,167

Примечание 7.2. При решении ТЗ в Excel, возможно, придется увеличить относительную погрешность решения в параметрах окна "Поиск решения".

Оптимальное решение ТЗ  [ч] из табл.7.3 без фиктивного столбца (все значения округлены до трех знаков после запятой) имеет следующий вид:

3,333333

0

546,6667

0

0

0

72,5

0

0

460

310

0

0

0

0

6,667

0

0

320

0

Оптимальное решение РЗ  [ч] получаем из оптимального решения ТЗ  [ч] по формуле (7.6), например:

 [ч];  [ч];  [ч];

3,33333

0

546,667

0

0

0

87

0

0

552

620

0

0

0

0

16

0

0

768

0

Значения  – это время, в течение которого корпус  будет выпускать изделия . Чтобы узнать, какое количество продукции будут выпускать корпуса, то есть  [шт.], воспользуемся формулой (7.7), например:

 [шт.];  [шт.].

В данном расчете округления (до меньшего целого) обязательны, поскольку выпускаемая продукция штучная:

66

0

16400