7. Возможные ошибки при вводе условий задач линейного программирования

№

Вопрос

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

в Excel

1

2

3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проверьте правильность установки параметров

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

Абсолютный прирост

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

Адекватность модели

соответствие модели реальному процессу по свойствам которые считаются существенными для исследования

Анализ чувствительности решения

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

Балансовые модели

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

Булевые (логические) переменные

переменные, которые могут принимать только два значения 0 и 1. Эти значения можно сопоставить с ответом на некоторый вопрос типа «да-нет», «брать-не брать» и т. п.

Используются, когда требуется решить, какие из большого набора элементов нужно выбрать, чтобы опти­мизировать целевую функцию и удовлетворить задан­ным ограничениям, а какие отбросить

Вершинная сетевая диаграмма

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

Временной (динамический) ряд

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

Временной резерв

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

Время поставки

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

Вторая теорема двойственности –

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

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

Для любой ЛП-задачи можно сформулировать двойственную задачу, тесно связанную с исходной ЛП-задачей. При решении исходной задачи одновременно может быть получено и решение ее двойственной задачи. Решением двойственной задачи являются теневые цены для ресурсов исходной задачи

Детерминированные модели

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

Диаграмма Гантта

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

Динамическое программирование (ДП)

метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги)

Дисперсия (D)

характеристика значений показателя, отражающая степень разброса отдельных значений показателя от среднего значения

Дисперсия регрессии –

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

Допустимое базисное решение

решение, которое удовлетворяет всем условиям ограничениям

Допустимое решение (план)

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

Зависимые факторы (элементы решения)

факторы, которые в известных пределах можно выбирать по своему усмотрению. Обозначаются как неизвестные х₁, х₂, ...

Задача динамического программирования

задача математического программирования, в которой имеется пе­ременная времени, и критерий эффективности выражается через уравнения, описывающие протекание операции во времени

Задача линейного программирования –

задача, в которой критерий эффективности представляет ли­нейную функцию и функции в системе ограничений также линейны

Задача о назначениях

частный случай ЛП-задачи. Наиболее распространенный вариант задачи состоит в выборе такого распре­деления работ между исполнителями, который мини­мизирует суммарные временные затраты на выполне­ние работ или другие характеристики эффективности работ

Задача о раскрое материалов

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

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

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

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

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

Задача составления рациона (задача о диете, задача о смесях)

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

Издержки размещения заказа

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

Издержки хранения запаса

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

Интервал устойчивости оптимального решения

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

Интервальный ряд динамики

ряд числовых значений определенного статистического показателя, характеризующего размеры изучаемого явления за определенные промежутки (периоды, интервалы) времени

Исследование операций

научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различ­ными организационными системами

Каноническая задача линейного программирования

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

Канторович Л.В.

российский ученый, академик, лауреат Нобелевской премии, поло­жил начало новому направлению прикладной математики – линей­ному программированию

Корреляционное отношение ŋ

характеристика тесноты связи результативного и факторного признаков при криволинейной зависимости

Корреляционный момент (ковариация)

характеристика тесноты связи показателей у и х, значения которых y_i, x_i, i = содержат случайные составляющие. Вычисляется по формуле:

Коэффициент парной корреляции

показатель тесноты связи для линейных однофакторных зависимостей:

Коэффициент регрессии

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

Коэффициент частной корреляции

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

Коэффициент эластичности

коэффициент, показывающий, на сколько процентов изменится величина результативного признака Y при изменении факторного признака х на один процент

Критерий Фишера (F)

критерий оценки соответствия уравнения регрессии реальной статистике где п – число наблюдении, k – число факторных признаков в уравнении

Критическая стадия

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

Критический путь

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

Линейная многофакторная модель

модель вида

Линейная однофакторная регрессия

уравнение связи результативного показателя и фактора в виде линейного уравнения: ,

где – результирующий показатель, х – фактор

Линейный тренд

уравнение прямой линии, выражающее тенденцию изменения временного ряда

Линия уровня линейной функции

линия, вдоль которой эта функция принимает одно и то же фиксированное значение

Метод «северо-западного угла»

один из возможных методов нахождения первоначального базисно­го распределения поставок в транспортной задаче начиная с верхней левой клетки и заканчивая нижней правой

Метод Гаусса решения системы линейных уравнений

метод, основанный на последовательном исключении неизвестных

Метод критического пути

определяет последовательность стадий на сетевой диаграмме с максимальной суммарной длительностью (критический путь). Позволяет также определить временные резервы не­критических стадий. Используется для оценки соот­ношения «длительность проекта – издержки» и для оптимизации длительности проекта. Основан на предположении о том, что длительность каждой стадии проекта строго определена и не под­вержена случайным изменениям

Метод наименьших квадратов

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

Множественный коэффициент корреляции

характеристика тесноты связи между результативным и несколькими факторными признаками

Модель операции

достаточно точное описание операции с помощью математического аппарата (различного рода систем уравнений и неравенств)

Моментный временной ряд динамики

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

Мультиколлинеарность

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

Нормированная (редуцированная) стоимость

величина, выдаваемая отчетом по устойчивости MS-Excel, показывает, насколько нужно увеличить прибыль па единицу данного продукта, чтобы он во­шел в оптимальный план. Для продукта, входящего в оптимальный план, редуцированная стоимость равна 0

Общая задача линейного программирования

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

Ограничения

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

Однофакторная параболическая модель второй степени

модель вида

Операция

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

Опорный план

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

Оптимальное решение (план)

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

Оптимизационная задача в общем виде

найти переменные x₁, x₂, ..., x_n, удовлетворяющие системе неравенств (уравнений) ω_i(x₁, x₂, ..., x_n) ≤ b_j, i = 1,2,...,m и обращающие в макси­мум (минимум) целевую функцию, т.е. Z = f(x_1, x₂, ..., x_n) → max (min)

Основная (первая) теорема двойственности

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

Остаточная дисперсия

характеристика отклонения фактических значений результативного показателя от расчетных, полученных с помощью уравнения регрессии

Открытая модель транспортной задачи

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

Отчет по устойчи­вости

один из отчетов, выдаваемый надстройкой «Поиск решения», содержащий информацию об интервалах устойчивости при изменении коэффициентов целе­вой функции и правых частей ограничений, а также информацию о теневых ценах

Параметры модели

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

Переменные решения

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

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

надстройка MS Exсel, позволяющая осуществить по­иск оптимального решения для задач линейной (и нелинейной) оптимизации с ограничениями. Число переменных решения не может превышать 200. Для каждой изменяемой ячейки (переменной) может быть за­дано по 2 ограничения (снизу и сверху). Кроме того, можно задать 100 дополнительных ограничений

Показатель

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

Постоянные факторы (условия проведения операции)

факторы, входящие в описание операции, на которые влиять невоз­можно. Обозначаются ₁, ₂, …

Признак

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

Принцип оптимальности

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

Проблема постоян­ных издержек

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

Регрессионная модель

запись выявленной связи между результативным показателем и факторами в виде уравнения в постановке, когда реализация результирующего показателя имеет случайную составляющую, а факторы – детерминированные

Результативный признак

исследуемый показатель экономического процесса, как правило, характеризующий эффективность процесса

Решение

всякий определённый выбор параметров операции

Свободный член регрессии

коэффициент а₀ уравнения регрессии, выражающий совокупное влияние всех неучтенных факторов; его вклад в значение результирующего показателя не зависит от изменения факторов

Сетевое планирование

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

Симплекс

геометрическая область в многомерном пространстве, каждая точка которой является образом допустимого решения ЛП-задачи

Симплекс-метод

1. эффективный метод перебора угловых точек области допустимых решений с целью нахождения оптимального решения ЛП-задачи. Предложен Дж. Данцигом в 1947 г. Метод (или его последующие модификации) лежи в основе всех компьютерных алгоритмов для решения ЛП-задач;

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

Симплексная таблица

таблица, используемая для решения задач линейного программирования без ЭВМ

Среднее квадратическое отклонение (σ)

отклонение, представляющее собой корень квадратный из дисперсии

Средний абсолютный прирост

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

Средняя относительная ошибка аппроксимации

характеристика точности модели временного ряда. Определяется формулой *100%,

где y_t – фактическое значение признака;

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

Стандартная задача линейного программирования

задача, в которой все переменные неотрицательны и система ограничений состоит лишь из одних неравенств

Стохастические (вероятностные) модели

модели с неизвестными факторами - случайными величинами, для которых известны функции распределения и различные статистические характеристики

Темп прироста

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

Темп роста

характеристика скорости изменения показателя в единицу времени, выраженная в процентах

Теневая цена

показывает, как изменится целевая функция ЛП-задачи, если количество соответствующего дефицитного ресурса увеличить на единицу. Для недефицнтного ресурса теневая цена равна нулю

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

частный случай задачи линейного программирования, формули­рующийся так: заданы поставщики и размеры их запасов, потреби­тели и размеры их заявок; известна стоимость перевозки единицы груза от каждого поставщика до каждого потребителя; требуется найти объёмы перевозок для каждой пары «поставщик-потребитель» так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех потребителей были удовлетворены;

3) суммарные затраты на перевозку всех грузов были бы мини­мальны

Тренд

функция от времени, определяющая основную тенденцию развития показателя во времени

Трендовая модель

экономико-математическая динамическая модель, в которой развитие моделируемой экономической системы отражается через тренд ее основных показателей

Фактор (факторный признак)

показатель, влияющий на значение результативного показателя

Фиктивный поставщик (потребитель)

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

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

количественный показатель эффективности управле­ния, зависящий от переменных решения и от параметров. При оптимальном выборе переменных решения достигает максимального или минимального значения (в зависимости от целей управления). Записывается в виде Z = (x₁, x₂, ..., ₁, ₂, ...)

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

методы решения ЛП-задач с дополнительным огра­ничением: все или часть переменных могут принимать только целые значения. По форме ЛП-задачн и ЦЛП очень похожи. Однако задачи ЦЛП гораздо более сложны, их решение тре­бует использования гораздо более сложных алгорит­мов и больших переменных затрат

Циклические перестановки

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

Эконометрика

наука, исследующая количественные закономерности и взаимозависимости в экономике при помощи методов математической статистики

Экономические методы

методы исследования экономики, изучающие экономические процессы с количественной стороны

Экономический смысл основной (первой) теоремы двойственности

план производства X^* = (х^*₁,х^*₂, ..., х^*_n) и набор цен (оценок) ресурсов Y^* = (у^*₁, у^*₂, …, у*_n) оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при «внешних» известных заранее ценах с₁, с₂, ..., с_n, равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) це­нам у₁, у₂, ..., у_n. Для всех других планов прибыль (выручка) от про­дукции всегда меньше (или равна) затрат на ресурсы

Эффективность операции

степень ее приспособленности к выполнению задачи; количествен­но выражается в виде критерия эффективности