Итоговый тест
2) вектор, направленный в сторону наименьшего возрастания функции и равный по величине производной в этом направлении:
3) набор из максимального числа линейно независимых векторов данного пространства;
4) набор из максимального числа линейно независимых векторов данного пространства;
5) набор из максимального числа линейно зависимых векторов данного пространства;
2. Оптимальное решение можно искать только:
1) среди опорных решений;
2) среди допустимых решений;
3) среди базисных решений;
4) графическим способом.
3. Задача о рационе является примером задачи:
1) линейного программирования;
2) дискретного программирования;
3) целочисленного программирования;
4) относится к теории игр.
4. Критерием оптимальности является
1) показатель, выражающий предельную норму экономического эффекта принимаемого решения для сравнительной оценки возможных решений и выбора наилучшего из них;
2)показатель, невыражающий предельную норму экономического эффекта принимаемого решения для сравнительной оценки возможных решений и выбора наилучшего из них;
3)показатель, выражающий экономический эффект; 4) один из методов поиска условного экстремума.
- В шар данного радиуса вписать циллиндр с наибольшей боковой поверхностью.
Предлагаемые варианты ответов: 1) 
; 2)
; 3)
; 4)
.
- Задача линейного программирования считается поставленной, если
1) указана линейная целевая функция 2) записана система ограничений 3) определено, к какому типу (максимизации или минимизации) принадлежит данная задача. 4) если выполнены условия 1), 2) и 3)
- Данное положительное число а размножить на 2 слагаемых так, чтобы их произведение было наибольшим.
Предлагаемые варианты ответов: 1) Они равны 
; 2) Они оба равны 
; 3) Ответа нет; 4) Для разных чисел ответы получаются разными.
- Симплекс – метод конечен:
1) всегда; 2) если задача не имеет вырожденных опорных решений; 3) если задача имеет вырожденные опорные решения; 4) если мы решаем двойственную задачу.
- Линией уровня является:
1) геометрическое место точек пространства, для которых значения исследуемой функции одинаковы; 2) геометрическое место точек пространства, для которых значения исследуемой функции неодинаковы; 3) геометрическое место точек пространства, для которых значения исследуемой функции различны; 4) геометрическое место точек пространства, равноудаленных от данной плоскости.
- Метод множителей Лагранжа является:
1) единственным методом поиска условного экстремума; 2) одним из методов поиска условного экстремума; 3) необходимым условием экстремума; 4) не применяется при решении задач на условный экстремум. 11. Симплекс – метод целесообразно применять, если: 1) количество неизвестных превышает две; 2) количество неизвестных не имеет значения; 3) если целевая функция неограничена; 4) если задача решается на компьютере. 12. Приравнивание к нулю частных производных функций в точке (если она дифференцируема в ней) является: 1) необходимым условием экстремума; 2) достаточным условием экстремума; 3) необходимым и достаточным условием экстремума; 4) алгоритмом сведения задач на условный экстремум к задачам на безусловный экстремум. 13. Графическим методом можно решить задачу линейного программирования, если количество её переменных: 1) не более трех; 2) две; 3) особого значения не имеет; 4) не менее двух. 14. Если допустимое множество задачи линейного программирования в канонической форме не пусто, то эта задача: 1) имеет опорные решения; 2) не имеет опорных решений; 3) имеет бесконечное число различных опорных решений; 4) не может быть решена симплекс – методом. 15. Если допустимое множество задачи линейного программирования не пусто, а целевая функция ограничена снизу (для задачи минимизации) на этом множестве, то задача линейного программирования: 1) имеет оптимальное решение; 2) не имеет оптимального решения; 3) вообще не имеет решения; 4) имеет несколько оптимальных решений. 16. Задача линейного программирования считается поставленной, если: 1) указана линейная целевая функция; 2) записана система ограничений; 3) определено к какому типу (максимизации или минимизации) принадлежит данная задача; 4) выполняются все перечисленные выше условия. 17. Единичной матрицей является: 1) прямоугольная матрица, у которой все элементы по главной диагонали – единицы, а остальные – нули; 2) квадратная матрица, у которой все элементы по главной диагонали – единицы, а остальные – нули; 3) прямоугольная матрица, у которой все элементы по главной диагонали — нули, а остальные — единицы. 4) прямоугольная матрица, у которой все элементы являются единицами. 18. Линейное программирование — область математического программирования: 1) посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными; 2) посвященная теории и методам решения экстремальных задач, характеризующихся квадратичной зависимостью между переменными; 3) посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между функциями; 4) посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между экстремумами функций. 19. Задача линейного программирования имеет каноническую форму, если в ее систему ограничений входят: 1) линейные уравнения; 2) условия неотрицательности всех неизвестных; 3) условия неотрицательности не всех неизвестных; 4) линейные уравнения и условия неотрицательности всех неизвестных.
- Понятие гиперплоскости:
1) обобщает наши представления о роли прямой на плоскости и плоскости в пространстве; 2)гиперплоскость делит пространство на два полупространства; 3) обобщает наши представления о роли прямой на плоскости и плоскости в пространстве. Гиперплоскость делит пространство на два полупространства; 4) термин линейного программирования. Так называется одно из допустимых решений, находящихся в вершинах области допустимых решений.
Тест по разделу МДК 02.01.01 «Линейное программирование»
2. Экономико-математическая модель – это
1) математическое представление экономической системы (объектов, задачи, явлений, процессов и т. п.) +
2) качественный анализ и интуитивное представление объектов, задач, явлений, процессов экономической системы и ее параметров
3) эвристические описание экономической системы (объектов, задачи, явлений, процессов и т. п.)
3. Метод – это
1) подходы, пути и способы постановки и решения той или иной задачи в различных областях человеческой деятельности +
2) описание особенностей задачи (проблемы) и условий ее решения
3) требования к условиям решения той или иной задачи
4. Задача, включающая целевую функцию f и функции Ф, входящие в 1) ограничения, является задачей линейного программирования, если
1) все Ф и f являются линейными функциями относительно своих аргументов +
2) все Ф являются линейными функциями относительно своих аргументов, а функция f – нелинейна
3) функция f является линейной относительно своих аргументов, а функции Ф – нелинейны
4) только часть функций Ф и функция f являются линейными относительно своих аргументов
5. Множество всех допустимых решений системы задачи линейного программирования является
1) выпуклым +
2) вогнутым
3) одновременно выпуклым и вогнутым
6. Если задача линейного программирования имеет оптимальное решение, то целевая функция достигает нужного экстремального значения в одной из
1) вершин многоугольника (многогранника) допустимых решений +
2) внутренних точек многоугольника (многогранника) допустимых решений
3) точек многоугольника (многогранника) допустимых решений
7. В задачах линейного программирования решаемых симплекс-методом искомые переменные должны быть
1) неотрицательными +
2) положительными
3) свободными от ограничений
4) любыми
8. Симплексный метод решения задач линейного программирования включает
1) определение одного из допустимых базисных решений поставленной задачи (опорного плана)
2) определение правила перехода к не худшему решению
проверку оптимальности найденного решения
3) определение одного из допустимых базисных решений поставленной задачи (опорного плана), определение правила перехода к не худшему решению, проверка оптимальности найденного решения +
9. Графический способ решения задачи линейного программирования – это
1) построение прямых, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств
2) нахождение полуплоскости, определяемой каждым из ограничений задачи
3) нахождение многоугольника допустимых решений
4) построение прямой F = h = const >= 0, проходящей через многоугольник решений
5) построение вектора C, перпендикулярного прямой F = h = const
6) передвижение прямой F = h = const в направлении вектора C (в сторону увеличения h), в результате чего находят либо точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве допустимых решений
7) определение координат точки максимума функции и вычисление значения целевой функции в этой точке
8) все перечисленные ответы в этом задании +
10. Задача линейного программирования не имеет конечного оптимума, если
1) в точке А области допустимых значений достигается максимум целевой функции F
2) в точке А области допустимых значений достигается минимум целевой функции F
3) система ограничений задачи несовместна
4) целевая функция не ограничена сверху на множестве допустимых решений +
11. Модель задачи линейного программирования, в которой целевая функция исследуется на максимум и система ограничений задачи является системой уравнений, называется
1) стандартной
2) канонической +
3) общей
4) основной
5) нормальной
12. В линейных оптимизационных моделях, решаемых с помощью геометрических построений число переменных должно быть
1) не больше двух +
2) равно двум
3) не меньше двух
4) не больше числа ограничений +2
5) сколько угодно
13. Задача линейного программирования может достигать максимального значения
1) только в одной точке
2) в двух точках
3) во множестве точек +
4) в одной или двух точках
5) в одной или во множестве точек
14. Если в прямой задаче, какое либо ограничение является неравенством, то в двойственной задаче соответствующая переменная
1) неотрицательна +
2) положительна
3) свободна от ограничений
4) отрицательная
15. Транспортная задача является задачей …. Программирования
1) динамического
2) нелинейного
3) линейного +
4) целочисленного
5) параметрического
16. Если в транспортной задаче объем спроса равен объему предложения, то такая задача называется
1) замкнутой
2) закрытой +
3) сбалансированной
4) открытой
5) незамкнутой
17. Если в транспортной задаче объем запасов превышает объем потребностей, в рассмотрение вводят
1) фиктивный пункт производства
2) фиктивный пункт потребления +
3) изменения структуры не требуются
Тесты МФЮА*. Методы оптимальных решений 43 вопросов (26 из 30). Вариант 1261
1. Переменные задачи линейного программирования, соответствующие r векторам базиса, называют
Выберите один ответ:
a. Внебазисными
b. антибазисными
c. Базисными
d. Свободными
Вопрос 2
В канонической форме задача оптимизации является задачей на максимум (минимум) некоторой линейной функции F и ее система ограничений состоит:
Выберите один ответ:
a. только из равенств (уравнений)
b. значения параметров только отрицательны
c. только из строгих неравенств
d. только из неравенств
Вопрос 3
Целевая функция — это
Выберите один ответ:
a. только одномерная функция
b. функция, формирующая область допустимых значений вектора параметров
c. только многомерная функция
d. математическое представление зависимости критерия оптимальности от искомых переменных
Вопрос 4
Для выпуклого многоугольника угловыми точками являются
Выберите один ответ:
a. его грани.
b. все его вершины
c. прямые, на которых лежат грани многоугольника.
d. все его внутренние точки.
Вопрос 5
Сколько дополнительных переменных будет иметь задача, двойственная к данной z=2x_+x_->max
2x_+6x_ \le 15;
4x_+3x_ \le 11;
x_ \ge 0, x_ \ge 0
Выберите один ответ:
a. 4
b. 0
c. 2
d. 1
Вопрос 6
В стандартной форме линейная задача оптимизации является задачей на максимум (минимум) некоторой линейной функции F и ее система ограничений состоит:
Выберите один ответ:
a. все переменные задачи отрицательны
b. только из неравенств
c. только из строгих неравенств
d. только из равенств (уравнений)
Вопрос 7
Особенностью задач линейного программирования является то, что экстремума целевая функция достигает:
Выберите один ответ:
a. во внутренних точках области допустимых решений.
b. на границе области допустимых решений.
c. на границе области определения только последнего параметра
d. на границе области определения только первого параметра.
Вопрос 8
Дан следующий вид задачи линейного программирования F=CX->max(min), AX=A0, X>=0, Этот вид называется:
Выберите один ответ:
a. стандартной формой записи
b. общей формой записи
c. канонической формой записи
d. векторной формой записи
Вопрос 9
Задачей выпуклого программирования называется задача нелинейного программирования, у которой функция f(x) является выпуклой(вогнутой) функцией и все функции-ограничения:
Выберите один ответ:
a. только квадратичные функции
b. не являются выпуклыми функциями
c. также являются выпуклыми функциями
d. невогнутые функции
Вопрос 10
Параметры плана — это:
Выберите один ответ:
a. ограничения на параметры
b. размерность задачи
c. оптимальное решение
d. переменные параметры, которые определяют решаемую задачу
Вопрос 11
В задачах линейного программирования целевая функция
Выберите один ответ:
a. Квадратичная
b. Логарифмическая
c. тригонометрическая
d. Линейная
Вопрос 12
Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления:
Выберите один ответ:
a. были равны потребностям в грузе в пунктах назначения
b. были неравны потребностям в грузе в пунктах назначения
c. были больше потребностей в грузе в пунктах назначения
d. были меньше потребностей в грузе в пунктах назначения
Вопрос 13
Основное преимущество геометрического способа решения задач линейного программирования является
Выберите один ответ:
a. Наглядность
b. Точность
c. скорость
Вопрос 14
Если критерий оптимальности F(X) есть отношение двух линейных функций, а множество D — выпуклый многогранник, детерминированная задача оптимизации называется задачей:
Выберите один ответ:
a. кусочно-непрерывного программирования
b. дробно-линейного программирования
c. динамического программирования
d. стохастического программирования
Вопрос 15
Если целевая функция исходной задачи оптимизации задается на максимум, то целевая функция двойственной ей задачи задается:
Выберите один ответ:
a. и на максимум и на минимум
b. на 0
c. на максимум
d. на минимум
Вопрос 16
Производная функции z=x^2-2xy+3y-1 в точке (1;2) по направлению l (-1; 1) равна:
Выберите один ответ:
a. 2
b. 3
c. -3
d. 0
e. -2
Вопрос 17
Производная функции z=x^2-2xy+3y-1 в точке (1;2) по направлению l (1; -1) равна:
Выберите один ответ:
a. -3
b. -2
c. 0
d. 3
e. 2
Вопрос 18
Общая идея симплексного метода (метода последовательного улучшения плана) для решения задачи линейного программирования не включает в себя один из следующих пунктов:
Выберите один ответ:
a. переходить к нехудшему опорному плану
b. находить начальный опорный план;
c. наличие признака оптимальности опорного плана.
d. находить штрафную функцию
Вопрос 19
В MathCad для решения оптимизационных задач с ограничениями используются функции:
Выберите один ответ:
a. pbinom(k,n,p)
b. median(A)
c. mean(A)
d. find(var1,var2. )
Вопрос 20
К наиболее известным задачам линейного программировании не относится:
Выберите один ответ:
a. задача о ресурсах
b. задача о раскрое
c. задача о распределении оптимального значения
d. задача о рационе
Вопрос 21
Ограничивающие функции — это:
Выберите один ответ:
a. только неравенства
b. всегда только целевые функции
c. только равенства
d. функции, формирующие область допустимых значений вектора параметров
Вопрос 22
Метод Свенна — это:
Выберите один ответ:
a. метод штрафных функций
b. метод предварительной локализации экстремума
c. метод множителей Лагранжа
d. метод Золотого сечения
Вопрос 23
Основная задача метода штрафных функций состоит в преобразовании задачи минимизации функции Z=f(x) с соответствующими ограничениями, наложенными на х, в задачу поиска минимума без ограничений функции Z=f(x) + P(x) Что здесь является штрафной функцией?
Выберите один ответ:
a. Z
b. f(x)
c. X
d. P(x)
Вопрос 24
Направление вектора-антиградиента является направлением:
Выберите один ответ:
a. наиболее быстрого возрастания функции в данной точке
b. наиболее быстрого убывания функции в данной токче
c. наиболее медленного возрастания функции в данной точке
d. наиболее медленного убывания функции в данной точке
Вопрос 25
Геометрический способ решения задач линейного программирования имеет смысл использовать для решения задач следующей размерности:
Выберите один ответ:
a. 4-х мерных
b. 1-мерных и 2-мерных
c. 3-х-мерных и выше
d. 4-х мерных и выше
Вопрос 26
Целевая функция может быть представлена:
Выберите один ответ:
a. только в виде функции, таблицы, отдельных значений
b. только в виде отдельных значений
c. только в виде таблицы
d. только в виде функции
Вопрос 27
Один из перечисленных ниже методов не является градиентным методом:
Выберите один ответ:
a. метод градиентного спуска с переменным шагом
b. метод градиентного спуска с постоянным шагом
c. метод штрафных функций
d. метод наискорейшего спуска
Вопрос 28
Какой из перечисленных ниже методов не является методом исключения интервалов?
Выберите один ответ:
a. метод штрафных функций
b. метод золотого сечения
c. метод деления отрезка пополам
d. метод общего поиска
Вопрос 29
В MathCad для решения задач оптимизации используются функции:
Выберите один ответ:
a. matrix(m, n, f)
b. augment(A,B)
c. maximize(f,); minimize(f,)
d. pbinom(k,n,p)
Вопрос 30
При решении транспортной задачи — если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, то модель такой транспортной задачи называется:
Выберите один ответ:
a. Свободной
b. Открытой
c. закрытой
d. Замкнутой
31. При решении транспортной задачи в качестве критерия оптимальности обычно берется:
Выберите один ответ:
a. либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки
b. максимальное время доставки груза
c. максимальный путь перемещения груза
d. минимальная скорость перевозки груза
32. Направление вектора-градиента является направлением:
Выберите один ответ:
a. наиболее быстрого возрастания функции в данной точке
b. наиболее быстрого убывания функции в данной точке
c. наиболее медленного убывания функции в данной точке
d. наиболее медленного возрастания функции в данной точке
33. Какой способ не является способом построения опорного плана транспортной задачи?
Выберите один ответ:
a. метод Свенна
b. способ минимального элемента
c. метод потенциалов
d. метод Северо-Западного угла
34. Метод покоординатного спуска неприменим в случае, если функция:
Выберите один ответ:
a. имеет «овраг»
b. унимодальная
c. Гладкая
d. непрерывная
35. Множеством решений системы m линейных неравенств с n переменными является:
Выберите один ответ:
a. выпуклый многогранник в n-мерном пространстве(за исключением случая, когда система несовместна).
b. только пустое множество.
c. невыпуклый многогранник в n-мерном пространстве
d. только прямая.
36. Математические модели любых транспортных задач линейного программирования имеют общие черты:
Выберите один ответ:
a. коэффициенты правых частей ограничений отрицательны
b. имеется только один параметр плана
c. коэффициенты целевой функции отрицательны
d. коэффициенты целевой функции неотрицательны (стоимости перевозок не могут быть отрицательными величинами)
37. Градиент функции z=x^2-2xy+3y-1 в точке (1;2) равен:
Выберите один ответ:
a. -2i
b. i+j
c. i-2j
d. 2j
e. -2i+j
38. Вектор, компонентами которого служат значения частных производных функции, называется:
Выберите один ответ:
a. Антиградиентом
b. Уровнем
c. параметром
d. Градиентом
39. Существует универсальный способ решения задач линейного программирования, называемый:
Выберите один ответ:
a. методом Золотого сечения.
b. градиентным методом с постоянным шагом
c. симплекс-методом
d. методом штрафных функций.
40. Градиент функции z=7x^2+2y^3 в точке (0;-2) равен:
Выберите один ответ:
a. -2i
b. I-2j
c. 24j
d. i+j
e. 2j
41. Задачи оптимизации принято различать по типам
Выберите один ответ:
a. детерминированные и недетерминированные (стохастические).
b. внешние и внутренние
c. макроэкономические и микроэкономические
d. фиксированные и нефиксированные
42. Если целевая функция F(X) является выпуклой, то детерминированная задача оптимизации называется задачей:
Выберите один ответ:
a. выпуклого программирования
b. динамического программирования
c. целочисленного программиров
d. стохастического программирования
43. Для решения задач многомерной оптимизации не используются:
Выберите один ответ:
a. метод наискорейшего спуска
b. методы градиентного спуска
c. метод простого перебора
d. метод штрафных функций
Контакты автора
Автор: Виктор Новиков
Решение задач линейного программирования методом структурной оптимизации Текст научной статьи по специальности «Математика»
Аннотация научной статьи по математике, автор научной работы — Карганов Сергей Александрович
— перечислены проблемы, препятствующие использованию в хозяйственной практике результатов решения прямых и обратных задач линейного программирования ; — показано, что преодоление этих препятствий лежит на пути использования разработанного автором и описанного в данной работе метода структурной оптимизации и алгоритмов его реализации; — приведены примеры решения методом структурной оптимизации задач производственного планирования.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по математике , автор научной работы — Карганов Сергей Александрович
Методика итерационно-интерактивного планирования на основе моделей линейного программирования
Ввод в область допустимых решений методом внутренних точек
Задача размещения сельскохозяйственного производства
Исследование и разработка интеллектуальных методов управления современным предприятием
Опыт декомпозиции метода конечных элементов с использованием теории структурированных оптимизационных задач
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Текст научной работы на тему «Решение задач линейного программирования методом структурной оптимизации»
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ СТРУКТУРНОЙ ОПТИМИЗАЦИИ Solving of Linear Programming by Method of Structural Optimization
Карганов Сергей Александрович доктор экономических наук, профессор e-mail: Sergey.Karganov@Gmail.com
— перечислены проблемы, препятствующие использованию в хозяйственной практике результатов решения прямых и обратных задач линейного программирования;
— показано, что преодоление этих препятствий лежит на пути использования разработанного автором и описанного в данной работе метода структурной оптимизации и алгоритмов его реализации;
— приведены примеры решения методом структурной оптимизации задач производственного планирования.
Ключевые слова: линейное программирование, прямые и обратные задачи, симплекс-метод, объективно обусловленные оценки, общественно-необходимые затраты труда, структурная оптимизация.
The paper lists the problems hindering the use in business practices of the results of solving direct and inverse problems in linear programming. It is shown that overcoming these obstacles lies in the way of use developed by the author and described in this paper the method of structural optimization and algorithms for its implementation. Here are examples of decisions by the structural optimization of production planning problems.
Key words: linear programming, direct and inverse problems, the simplex method, the objectively determined valuations, the socially necessary labor costs, structural optimization.
1. О проблемах связанных с постановкой и решением задач линейного
Известно, что значительное количество задач производственного планирования могут быть представлены в виде линейных математических моделей двух типов: основных и двойственных основным задач линейного программирования.
Считается, что решение основных задач линейного программирования создаёт
необходимые предпосылки для повышения эффективности производства: роста доходов и прибыли или снижения затрат на производство продукции и технологических отходов при её производстве.
Двойственные задачи линейного программирования формируются на той же
нормативной базе что и основные задачи, но с целью определения системы ресурсных оценок, названных их автором, Л.В. Канторовичем, разрешающими множителями или объёктивно обусловленными оценками (о. о. оценками).
По мнению Л.В. Канторовича [1, стр. 155] и современных экономистов [2] рыночные цены используемых ресурсов должны приближаться к о. о. оценкам, а при вычислении о.
о. оценок для полной номенклатуры ресурсов в масштабах страны эти оценки в
состоянии обеспечить оптимизацию хозяйственных решений и стать основой
Способы вычисления о. о. оценок были предложены Л.В. Канторовичем ещё в 1939 г., однако «. чистую победу. » в способе их определения в 1947 г. одержал симплекс-метод, предложенный Дж. Б. Данцигом [3, стр. 79-86].
С тех пор и до настоящего времени симплекс-метод служит основным методом решения задач линейного программирования, однако надежды на его широкое использование не оправдались. И дело не в размерности задач хозяйственного планирования, а в ошибочности экономических предпосылок формирования основной и двойственной задач линейного программирования, а также особенностей алгоритма реализации самого симплекс-метода.
Проиллюстрируем сказанное на примере выбора оптимального плана производства продукции, приводимом в учебном пособии В.Л. Тарасова [4, стр. 17]:
Таблица 1. Исходные данные для планирования.
Ресурсы Запасы ресурсов Затраты ресурсов на единицу готовой продукции
Оборудование 64 1 4
Прибыль от реализации единицы готовой продукции в денежных единицах (д.ед.) 5 6
Основная задача линейного программирования в данном примере состоит в определении объёмов производства продукции (xi и х2) двух видов продукции (Р1 и Р2), максимализирующих величину прибыли предприятия:
F(x) = Z Cj • x>. = 5х1 + 6х2 ^ max, (1)
при заданных ресурсных ограничениях ( Z ai>. • x>. < bt ):
и при x1 > 0 и x2 > 0 .
Оптимальное решение этой задачи симплекс-методом [(F(x) = 124] имеет место при объёмах производства х1 = 8, х2 = 14 и недоиспользовании второго вида ресурса в размере 18 ед..
В учебном пособии [4] постулируется широко распространённое мнение о том, что решение двойственной (для данной основной) задачи линейного программирования состоит в определении цен за единицу каждого из используемых видов ресурсов y1, y2 и y3, при которых выручка производителя от продажи ресурсов была бы равна ожидаемой прибыли от реализации готовых изделий.
Математическая модель двойственной задачи линейного программирования в данном примере имеет вид:
G(y) = Z Ь • У, = 140y 1 + 64y2 + 64уз ^ min, (3)
при ограничениях (Zai • Уг > CJ ): 7У1 + 4У2 + У3 > 5 (4)
6y1 + У2 + 4уз > 6
если y1 > 0, у2 > 0, у3 > 0.
При решении данной двойственной задачи симплекс-методом значения о. о. оценок ресурсов составят: y1 = 0,636; у2 = 0 и у3 = 0,545. Согласно учебного пособия равенство
значений целевых функций основной и двойственной задач [Р(х) = G(y) = 124] служит лучшим подтверждением оптимальности и объективности решений рассматриваемых задач, а также экономической ценности самого симплекс-метода.
Однако существуют проблемы, исключающие использование о. о. оценок в задачах оптимального ценообразования и ограничивающие возможности оптимального планирования и прогнозирования хозяйственных ситуаций на основе симплекс-метода.
Проблема первая (гносеологическая) имеет четыре аспекта.
Первый аспект заключается в экономической интерпретации результатов решения двойственной задачи линейного программирования.
Так о. о. оценки, получаемые в результате решения двойственной задачи линейного программирования, теряют экономический смысл, если критериями оптимизации основной задачи линейного программирования служат: «минимизация затрат
производства», «максимизация прибыли», «минимизация отходов» или «брак на производстве», а также максимализация и минимализация значений социальных критериев.
Во всех перечисленных случаях найденные значения переменных двойственной задачи (о. о. оценок) не имеют экономического смысла, однако пригодны для поиска оптимальных решений основных задач линейного программирования и, поэтому, оправдывают своё первоначальное название: «разрешающие множители».
В тоже время очевидно, что при реализации ресурсов по таким «ценам» производители вернут себе только ожидаемую прибыль в размере 124 денежных единиц, а используемые для её получения ресурсы отдадут покупателю «в презенте». , т.е. бесплатно.
Второй аспект этой проблемы можно проиллюстрировать на примере решения задачи (3) — (4). Экономический смысл о. о. оценок (у1, у2, уз), определяемых в результате решения в этой задачи можно было бы трактовать как усреднённую по двум продуктам долю прибыли, приходящуюся на единицу ресурсов (первого, второго и третьего вида) и рассчитанную с учётом имеющихся запасов этих ресурсов.
Однако полученное решение (у1 = 0,636; у2 = 0; у3 = 0,545) даёт основания утверждать, что использование второго вида ресурса не приносит прибыли. Поскольку ошибочность подобного вывода очевидна, то появляется твёрдое убеждение, что о. о. оценки первого и третьего видов ресурсов определены с ошибками.
Подобная ситуация является характерной особенностью результатов применения симплекс-метода в ситуациях, когда полученное оптимальное решение не обеспечивает полного использования одного и более распределяемых видов ресурсов. А это почти все получаемые решения.
Третий аспект этой проблемы состоит в том, что для ресурсообладателей качество плана определяется не только полнотой (средним процентом) использования наличных ресурсов, но и степенью пропорциональности планируемых остатков ресурсов их располагаемому наличию. Такая пропорциональность гарантирует комплектность и стабильность производства и потребления ресурсов производства.
Очевидно, что чем комплектнее и полнее будут использованы располагаемые ресурсы, тем выше эффективность результатов решения задачи оптимизации.
Показателем комплектности (пропорциональности) использования средств достижения цели может служить показатель величины структурных сдвигов S в использовании располагаемых ресурсов, который равен нулю в случае полного совпадения структуры наличных ресурсов и структуры их планируемого использования:
где di, и di,,o — удельные веса отдельных видов ресурсов в общем объёме их наличия и планируемого потребления соответственно, , = 1. т;
Тогда выбор наиболее эффективного метода для решения той или иной задачи линейного программирования можно произвести на основе показателя эффективности плановых расчетов Epr :
где: ЕЬг — суммарный объём располагаемых ресурсов, а ЕЬго — объём их планируемого использования.
Чем меньше значение показателя Epr, тем лучше в оцениваемом варианте плана использованы располагаемые ресурсы для его реализации.
Поскольку значения показателей S и Epr при решении задачи (5)-(2) симплекс-методом составили соответственно 0,040 и 0,043, а при использовании метода структурной оптимизации — 0,033 и 0,036, то для практической реализации следует принять вариант плана, рассчитанный методом структурной оптимизации.
Четвёртый аспект этой проблемы состоит в том, что объёмы производства и, следовательно, значения целевых функций в задачах линейного программирования определяют в конечном итоге структурой и объёмами располагаемых ресурсов. Поэтому величину недоиспользования производственных ресурсов следует рассматривать как дополнительные затраты производства, не приносящие желаемого результата, или убытки производства. Эти потери в настоящее время не учитываются при оценке решений задач линейного программирования. В тоже время, как показывают данные таб. 2, при использовании симплекс-метода они могут быть значительными. Так при решении задачи оптимизации для системы ограничений (11) эти потери в 3,98 раза [(268 — 192) : (268 -248,9)] превысили величину аналогичных потерь при использовании метода
структурной оптимизации. Поэтому в задачах линейного программирования, предусматривающих максимизацию какого-либо критерия (прибыли, дохода и т.п.), для правильной оценки результатов оптимизации их значения каждый раз следует уменьшить на совокупную стоимость недоиспользованных ресурсов производства, а при минимизации критериев оптимизации (бака, отходов, затрат и т.п.) — увеличить.
При условии, что цены единицы каждого вида используемых ресурсов в задаче (1) —
(2) равны одной денежной единице, единственным критерием оптимизации, который не требует подобной корректировки, может служить критерий максимизации
использования заданных ограничений (5).
F(x)* = ZC, ■ Xj =ZZa„ ■ xt = (7+4+1)x1 + (6+1+4)x2 =12×1 + 11×2—— max. (5)
При решении симплекс-методом задачи (5) и (2), оптимальные значения переменных составили: х1 = 8, х2 = 14; новое значение функции цели, отражающее потребление ограниченных ресурсов, составило 250 ед., или 93,3 % от их общего объёма (268 ед.).
При решении задачи (5) и (2) методом структурной оптимизации1 значения переменных составят: х1 = 11,519 и х2 = 9,895, а объём потребления ограниченных ресурсов — 247,073, что составляет 92,2% от их наличия.
Эти и приведённые в таб. 2 данные свидетельствуют, что метод структурной оптимизации не только конкурентоспособен, но и обеспечивает более полное и пропорциональное использование располагаемых ресурсов.
Остаётся дополнительно отметить, что о. о. оценки, рассчитанные на основе решения прямых задач линейного программирования симплекс-методом с целевыми функциями отличными от (5) обладают теми же недостатками.
1 Описание метода и примеры его использования приведены в тексте данной работы.
Проблема вторая (экономическая) имеет три аспекта.
Первый аспект состоит в том, что, несмотря на равенство критериев оптимизации1, оптимальные решения основной и двойственной задач линейного программирования не тождественны по экономическим результатам.
Как было отмечено, при решении задачи (5) и (2) симплекс-методом значение целевой функции F(х)* составит 250 ед.. При этом первый и третий виды ресурсов будут использованы полностью, а второй вид ресурса только на 72 %.
Двойственная (или обратная) задаче (5) и (2) задача линейного программирования примет вид:
С(у)* = 140у1 + 64у2 + 64у3 ^ тт, (6)
при ограничениях: 7у1 + 4у2 + у3 > 12 (7)
6у1 + У2 + 4у3 > 11
При решении этой задачи симплекс-методом о. о. оценки ресурсов составят: у1 = 1,682; у2 = 0; у3 = 0,227, а суммарная оценка их наличия G(y)* также равна 250 ед..
Однако полученные оценки ресурсов нельзя назвать «объективными», поскольку нулевую оценку (у2 = 0) получил используемый вид ресурса. Нельзя также назвать эти оценки «обусловленными», поскольку принятые в расчёте ,Р(х) рыночные цены используемых ресурсов по всем параметрам несопоставимы с оценками тех же ресурсов, оптимизирующими критерий G(y).
Оценки, получаемые при решении обратных задач линейного программирования методом структурной оптимизации, также нельзя «объективными» и «обусловленными» ценами располагаемых ресурсов, однако они ближе по структуре к структуре объёмов располагаемых ресурсов и позволяют проследить сбалансированность их потребления.
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
Так при решении этим методом задачи (5) и (2) значения переменных составили: х1 =
11,519 и х2 = 9,895, а F(х)* = 247,1; в результате решения тем же методом2 задачи (6)-(7) значения оценок ресурсов составили: у1 = 1,212; у2 = 0,693; у3 = 0,759, а суммарная оценка ресурсов — величину G(y)* = 262,61.
Различие в этих оценках стоимости произведённой продукции и стоимости используемых ресурсов возникло:
— на величину ДG1 = (С1* — С1) • Х1* = (12,014-12,0) • 11,519 = 0,16 в результате завышения в оптимальном решении норматива С1* = 12,014 по сравнению с его исходным значением С1 = 12;
— на величину стоимости неиспользуемой части (остатка) второго вида ресурса в размере ДG2 = (64-55,97) -0,693 = 5,57:
— на величину стоимости неиспользуемой части (остатка) третьего вида ресурса в размере ДGз = (64-51,10) -0,758 = 9,78.
В итоге имеем результат: G(y1, у2, у3,)* — ДG1 — ДG2 — ДG3 = F(х)* или 262,61 — 0,16 -5,57 — 9,78 = 247,1, который невозможно получить при использовании о. о. оценок, рассчитанных симплекс-методом.
Второй аспект данной проблемы состоит в том, что использование о. о. оценок в качестве рыночных цен или инструмента для их корректировки противоречит не только экономической теории, но и здравому смыслу, поскольку:
— рыночные цены используемых ресурсов известны, как правило, ещё до решения задач линейного программирования и не могут быть изменены;
— использование двойственных оценок для определения планируемых рыночных цен также бесперспективно, поскольку их значения определяются наличием и комплектностью ресурсов отдельных производств, а не величиной общественно-
1 Считается, что подтверждением этому служит равенство: F(х) = в(у) = 250.
2 Расчёт этих оценок методом структурной оптимизации приведён в данной работе на стр. 12.
необходимых затрат производства. По этой причине найденные о. о. оценки ресурсов будут несопоставимы даже для предприятий, выпускающих однородную продукцию.
Для иллюстрации сказанного допустим, что в рассматриваемом примере средняя рыночная стоимость использования единицы ресурса составляет: для затрат труда, используемого на данном предприятии, — 3 д.е.; для сырья — 2 д.е., а для оборудования — 3 д.е..
Возможны три варианта формирования условий двойственной задачи с целью получения о. о. оценок.
Первый вариант предполагает определение о. о. оценок ресурсов исходя из ожидаемых (планируемых) рыночных цен на производимую продукцию в денежных единицах (в д.е.), обеспечивающих производителям получение планируемой прибыли на каждую единицу производимой продукции. Поскольку состав технологических затрат производства (в натуральных единицах измерения) и величины прибыли на единицу продукции (в д.е.) нам даны, то с учётом принятых рыночных цен на единицу каждого вида ресурса рыночная стоимость единицы продукции Pi составит 37 д.е. (7-3 + 4-2 +1-3 +5), а единицы Р2 — 38 д.е. (6-3 + 1-2 + 4-3 + 6). В этом случае двойственная задача, аналогичная задаче
(3) — (4), примет вид:
G(y) = 140y1 + 64y2 + 64y3 — min, (8)
при ограничениях: 7y1 + 4y2 + y3 > 37 (9)
6y1 + У2 + 4y3 > 38 ,
а о. о. оценки, рассчитанные симплекс-методом, получат значения ( y1 = 5,0; y2 = 0 и y3 = 2,0), ничего общего не имеющие с принятыми рыночными ценами на использованные виды ресурсов.
Второй вариант предполагает использование о. о. оценок в качестве показателей, уточняющих рыночные цены на используемые ресурсы в связи с оптимизацией симплекс-методом не прибыли, а доходов производства.
В этом случае оценку производимой продукции, а также затраты и наличие каждого вида используемых ресурсов следует представить в денежном измерении. В результате исходная основная задача (1) — (2) примет вид:
F(x) = 37х1 + 38х2 — max, (10)
при заданных ресурсных ограничениях:
и при х1 > 0 и х2 > 0;
а двойственная задача (3) — (4) примет вид:
G(y) = 420y 1 + 128y2 + 192y3 — min, (12)
при ограничениях: 21y1 + 8y2 + 3y3 > 37 (13)
18y1 + 2y2 + 12y3 > 38
и при y1 > 0, y2 > 0, y3 > 0.
В результате решения симплекс-методом задач (10) — (11) и (12) — (13) имеем:
F(x) = G(y) = 828; x1 = 8, х2 = 14, а y1 = 1,667; y2 = 0 и y3 = 0,667.
Очевидно, что при использовании найденных значений о. о. оценок для корректировки сложившихся рыночных цен на используемые производственные ресурсы (y1*=3,04,667= 5,0; y2*=2-0=0 и y3*=3,0-0,667=2,0) полученные цены совпадут со значениями о. о. оценок, полученных при решении задачи (8) — (9). Следовательно, обе рассмотренных версии формирования цен на ресурсы производства не соответствуют экономическим принципам формирования рыночных цен, а именно — их формированию на основе общественнонеобходимых затрат производства.
Третий вариант предусматривает формирование значений о. о. оценок исходя из фактических затрат производства, т.е. исходя из себестоимости производимой продукции.
Так если в ограничениях (13) из рыночных цен продукции Pi и Р2 исключить прибыль и принять их в размере стоимости фактических технологических затрат производства, т.е. 32 д.е и 32 д.е. соответственно, то рассчитанные симплекс-методом значения о. о. оценок существенно не изменятся (они составят: y1 = 1,455; y2 = 0 и y3 = 0,485), чем подтвердят ошибочность и данного варианта формирования о. о. оценок.
Следовательно, единственным решением второй проблемы следует считать отказ от придания значениям о. о. оценок какого-либо экономического содержания и от постулируемой перспективы их использования в системах оптимального ценообразования.
Третий аспект этой проблемы состоит в том, что полученные, в результате использования симплекс-метода, оптимальные решения могут предусматривать отказ от производства необходимых стране товаров и услуг, а также неэффективное использование отдельных видов ресурсов.
Для лучшей иллюстрации сказанного добавим в исходном примере ещё один производимый продукт (Р3) с единичным потреблением каждого вида ресурса и прибылью от реализации единицы продукции в размере 7 д.е.. В результате система (1) -(2) примет вид:
F(x) = 5х1 + 6х2 + 7х3 — max, (14)
при заданных ресурсных ограничениях:
и при х1 > 0, х2 > 0, х3 > 0 .
Оптимальное решение задачи (14) — (15) симплекс-методом (х1= 0, х2= 0 и х3 = 64) предусматривает полный отказ от производства продуктов Р1 и Р2, а также обеспечит полное использование только второго и третьего видов ограниченных ресурсов. При этом решении первый вид ресурса будет использован лишь в объёме 64 натуральных единиц, что составляет менее половины (45,7%) от его наличия.
Важно отметить, что приведённое оптимальное решение задачи (14) — (15) не изменится при изменении значений коэффициентов С, функции цели (14) в широких пределах, например при:
Ci = 1+19, С2 = 6 и Сз = 5;
Ci = 1, С2 = 7+28 и Сз = 7; (16)
С1 = 1, С2 = 6 и С3 = 7 + да
В тоже время при значениях коэффициентов функции цели: С1 = 19, С2 = 6 и С3 = 5
система (14) — (15) будет иметь два альтернативных оптимальных решения при одном и том же значении критерия оптимизации (F=448 д.е.). Первое решение будет аналогичным ранее описанному, а второе — обеспечит рост использования первого вида ресурса до 91,8%, т.е. в два раза.
Наибольшая диспропорция в загрузке и недоиспользование объёмов лимитированных ресурсов в задаче (14) — (15) будет иметь место при значениях коэффициентов: С1 = 1, С2 = 29 и С3 =7. В этом решении имеем: х1= 0, х2= 16 и х3 = 0; использование первого вида ресурса составит только 68,6%, а второго — 25%.
Приведённые примеры свидетельствуют, что при использовании симплекс-метода:
1. Значения коэффициентов функции цели далеко не всегда определяют направление поиска оптимального решения. Как только что было показано оптимальное решение может не измениться при варьировании в широких пределах значений коэффициентов функции цели и наоборот — при одних и тех же значениях коэффициентов функции цели могут иметь место различные по объёмам использования ресурсов оптимальные планы производства.
Те же обстоятельства служат дополнительной причиной непригодности рассчитываемых
о. о. оценок для решения проблем оптимального ценообразования.
2. Оптимальные планы производства рассчитанные симплекс-методом не гарантируют стабильности, полноты и пропорциональности использования ограниченных ресурсов. В тоже время решение задачи (14) — (15) методом структурной оптимизации обеспечит использование располагаемых ресурсов первого вида на 100%, второго — на 89%, а третьего — на 81,4%.
3. Найденные оптимальные решения допускают возможность полного отказа от производства части ранее производимой продукции, что может повысить спрос на эти виды продукции и привести к росту инфляции в стране.
Так, например, любое из оптимальных решений задачи (14) — (15) симплекс-методом при всех рассмотренных значениях коэффициентов функции цели (16) предусматривает отказ от производства первого и второго видов продукции (х1= 0, х2= 0).
Данная особенность симплекс-метода исключает возможность его использования в задачах оптимизации с обязательной номенклатурой (необходимым ассортиментом) продукции без введения в математических моделях линейного программирования дополнительных ограничений на значения переменных .
Для оценки расчётных возможностей симплекс-метода введём такие ограничения на значения переменных и примем х1 < 5 и х3 >10. в результате система (14) — (15) примет вид:
F(x) = 5х1 + 6х2 + 7х3 — max, (17)
при ресурсных ограничениях:
и при: х1 > 0, х2 > 0, х3 > 0.
Однако решение задачи (17)-(18) симплекс-методом не позволило получить значение переменной х1 отличное от нуля. В целом полученное решение системы (18) не отличается от решения системы (15) и значения переменных по-прежнему составят: х1= 0, х2= 0 и х3 = 64.
Решение системы (18) методом структурной оптимизации имеет вид: х1= 1,43, х2= 12,37 и х3 = 13,1.
При строгих ограничениях на значения переменных (х1 = 5; х3 = 10) решения системы (18) симплекс-методом и методом структурной оптимизации совпадают: х1= 5, х2= 12,25 и х3 = 10.
С учётом изложенного можно отметить, что формирование планов производства с позиций получения предпринимателями финансовой выгоды, покрывающей их потери от непропорционального и неполного использования располагаемых ресурсов, приводит не к росту эффективности общественного производства и богатства страны, а служит источником неконтролируемого роста диспропорций производства и потребления продукции отдельных отраслей и, как результат, к росту инфляции и безработицы в стране.
Обобщённое представление о сравнительной эффективности метода структурной оптимизации могут дать данные таблицы 2.
Оценка результатов использования производственных ресурсов при распределении ограниченных ресурсов симплекс-методом (СМ) и методом структурной оптимизации
Показатели Типы производственных систем и методы планирования
Система (2) Система (11) Система (15) Система (18)
СМ МСО СМ МСО СМ МСО СМ МСО
х1 8 11,519 8 1О,О2 О 7,11 0 5,0
х2 14 9,895 14 11,67 О 7,11 0 6,64
х3 — — — — 64 28,44 64 32,44
d 1 О,522 О,522 О,568 О,568 О,522 0,522 0,522 0,522
d 2 О,239 О,239 0,173 0,173 О,239 0,239 0,239 0,239
d 3 О,239 О,239 О,259 О,259 О,239 0,239 0,239 0,239
d 1,о О,56О О,567 О,597 О,6О6 О,333 0,486 0,333 0,468
d 2,о 0,184 О,226 О,131 О,149 О,333 0,257 0,333 0,255
d3^ О,256 О,2О7 О,272 О,245 О,333 0,257 0,333 0,277
Ebi 268 268 74О 74О 268 268 268 268
2bi,o 25О 247,О7 7О4 693,53 192 248,9 192 231,4
Ebi,o :Sbi О,933 О,922 О,951 О,937 О,716 0,929 0,716 0,863
S О,О4О О,О33 О,О3О О,О27 О,133 0,025 0,133 0,039
E \->pr О,О43 О,О36 О,О32 О,О29 0,186 0,027 0,186 0,045
Наличие описанных проблем и данные таб. 2 свидетельствуют, что переход от использования симплекс-метода к использованию метода структурной оптимизации при разработке планов производства и программ развития народного хозяйства улучшит использование богатства страны, а также повысит объективность и однозначность принимаемых экономических решений.
Решение задач линейного программирования методом структурной оптимизации можно реализовать на основе полного (более точного) и упрощённого (ускоренного) алгоритмов его реализации.
2. Полный алгоритм реализации метода структурной оптимизации при решении
задач линейного программирования
Каждая итерация данного алгоритма структурной оптимизации состоит из повторяющихся шагов вычислений.
Приведём презентацию пошаговой реализации алгоритма структурной оптимизации на том же примере задачи линейного программирования (5) и (2), а именно:
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
F(x)= 12х1 + 11 х2 ^ max 7xi + 6х2 < 140 4х1 + х2 < 64 х1 + 4х2 < 64,
при х1 > 0 и х2 > 0 .
1. На первой итерации определяем и корректируем на последующих итерациях базисные значения Xj) — коэффициентов структуры потребления i -того вида ограниченных
ресурсов для каждого j — того способа их использования на k — ой итерации: Xj) =
avjТ atj . Тогда для ресурсных ограничений (2) значения базисных коэффициентов Xj1
при i = 1: 0,538; 0,462;
2. В задачах линейного программирования с ограничениями типа « < » (задачах
максимизации функции цели) среди найденных значений X(k) на каждой к — той итерации
для каждого j находим минимальное значение ( X j)= min Xk ), а в задачах с ограничениями
типа « > » (задачах минимизации функции цели)- максимальное значение ( X j) = max XJ)).
В данном примере минимальные значения X(k) равны: X1(1) = 0,2 ; X^ = 0,2.
3. Определяем потребности в ограниченных ресурсах bk при найденных значениях Xj по формуле: b(k) = Т а у • X J).
b1 = 7 • 0,2 + 6 • 0.2 = 2,6 b1 = 4 • 0,2 +1-0.2 = 1,0 b3 = 1-0,2 + 4 • 0.2 = 1,6
Если расчётные значения bk не удовлетворяют заданным, следует перейти к следующей итерации алгоритма структурной оптимизации.
1. Корректируем значения базисных коэффициентов Xj1, полученные на предыдущем шаге вычислений. В общем случае имеем: Xjk+1) = Xj) • bt /bk
В рассматриваемом примере значения базисных коэффициентов , необходимые для реализации второй итерации, то есть значения Xj2, составят:
при i = 1: 28,97 ( 0,538 • 140/2,6); 24,88 (0,462- 140/2,6);
i = 2: 51,2 ( 0,800 • 64/1); 12,8 (0,200 • 64/1);
i = 3: 12,8 (0,200 • 64/1); 51,2 ( 0,800 • 64/1).
2. X 1(2) =12,8; X 22)=12,8.
3. b2 = 7 12,8 + 6 12.8 = 166,4 b22 = 4 12,8 +1 • 12.8 = 64
b32 = 112,8 + 4 • 12.8 = 64 Вычисления следует продолжить, поскольку не соблюдены ресурсные ограничения.
1. При i = 1: 24,374 (28,97 • 140/166,4);
i = 2: 51,2 (51,2 • 64/64);
i = 3: 12,8 (12,8 • 64/64);
2. X1(3) =12,8; X 23) =12,8.
3. bf = 7 • 12,8 + 6 12.8 = 166,4 b23 = 4 12,8 +1 • 12.8 = 64 b33 = 112,8 + 4 • 12.8 = 64
Вычисления следует продолжить, поскольку не соблюдены ресурсные ограничения.
1. При i = 1: 20,507 (24,374 • 140/166,4); 17,612 (20,933 • 140/166,4);
i = 2: 51,2 (51,2 • 64/64); 12,8 (12,8 • 64/64);
i = 3: 12,8 (12,8 • 64/64); 51,2 (51,2 • 64/64).
2. X 1(4) =12,8; X24)=12,8.
4. b14 = 7 12,8 + 6 12.8 = 166,4
20,933 (24,88 • 140/166,4); 12,8 (12,8 • 64/64);
Ь24 = 4-12,8 +1-12.8 = 64 Ь34 = 1-12,8 + 4-12.8 = 64 Вычисления следует продолжить, поскольку не соблюдены ресурсные ограничения.
1. При i = 1: 17,253 (20,507 • 140/166,4); 14,817 (17,612 • 140/166,4);
i = 2: 51,2 (51,2 • 64/64); 12,8 (12,8 • 64/64);
i = 3: 12,8 (12,8 • 64/64); 51,2 (51,2 • 64/64).
2. Х1(5) =12,8; X25) =12,8.
3. Ь1 = 7 -12,8 + 6 -12.8 = 166,4 Ь25 = 4-12,8 +1-12.8 = 64 Ь35 = 1-12,8 + 4-12.8 = 64
Вычисления следует продолжить, поскольку не соблюдены ресурсные ограничения.
1. При i = 1: 14,516 (17,253 • 140/166,4); 12,467 (14,817 • 140/166,4);
i = 2: 51,2 (51,2 • 64/64); 12,8 (12,8 • 64/64);
i = 3: 12,8 (12,8 • 64/64); 51,2 (51,2 • 64/64).
2. Х1(6) =12,8; Х26) =12,467.
3. Ь6 = 7-12,8 + 6-12.467 = 164,402 Ь26 = 4 -12,8 +1 -12.467 = 63,667 Ь36 = 1-12,8 + 4 -12.467 = 62,668
Вычисления следует продолжить, поскольку не соблюдены ресурсные ограничения .
1. При i = 1: 12,36 (14,516 • 140/164,402); 10,617 (12,467 • 140/164,402);
i = 2: 51,468 (51,2 • 64/63,667); 12,867 (12,8 • 64/63,667);
i = 3: 13,072 (12,8 • 64/62,668); 52,288 (51,2 • 64/62,668).
2. Х1(7) =12,36; X 27) =10,617.
3. Ь/ = 7-12,36 + 6-10.617 = 150,222 Ь27 = 4-12,36 +1-10,617 = 60,057 Ь37 = 1-12,36 + 4-10.617 = 54,828
Вычисления следует продолжить, поскольку не соблюдены ресурсные ограничения.
1. При i = 1: 11,519 (12,36 • 140/150,222);
i = 2: 54,847 (51,468 • 64/60,057);
i = 3: 15,259 (13,072 • 64/54,828);
2. X™ =11,519; Х28) =9,895.
3. Ь8 = 7-11,519 + 6 — 9,895 = 140,00 Ь28 = 4 -11,519 +1- 9,895 = 55,971 Ь38 = 1-11,519 + 4 — 9,895 = 51,099
На этой итерации процесс вычислений следует считать законченным, поскольку ресурсные ограничения соблюдены и последующие итерации не приведут к улучшению использования ограниченных ресурсов. Обозначим значения переменных, определяющие
9,895 (10,617 • 140/150,222);
13,712 (12,867 • 64/60,057);
61,035 (52,288 • 64/54,828).
оптимальное решение задачи линейного программирования, через X**. Тогда имеем: Х* =
11,519 и X2=9.895. При данных значениях переменных функция цели (5) будет иметь значение:
F(x)= 11,519-12 + 9,895-11 = 247,073. и её величина полностью совпадает со значением величины использованных ресурсов.
Результаты решения других задач линейного программирования методом структурной оптимизации приведены в таб. 2.
Примечания к алгоритму структурной оптимизации:
1) При наличии ограничений на минимальные значения переменных (например X>. > М)
ресурсы, необходимые для реализации j — того способа производства в минимальном объёме М следует резервировать (исключать их из распределяемого наличия) до решения задачи оптимизации, а по завершении оптимизации производить расчёт оптимального значения X*:
2) При наличии ограничений на соотношение расчётных значений переменных типа:
где К — любое число;
определение значений переменных (Xv или Xу ) следует производить по формуле (20),
исходя из величины той переменной, которая на первой итерации имела меньшее значение.
3) Если значение какой-либо переменной ограничено сверху ( X>. < М), то при значениях Xj >М на к — ой итерации вычислений следует принимать Xj =М .
р=max (21) где b* — значения ограничений в модели линейного программирования, для которых необходимо соблюдение условий: b((k) > b’*, а при фактических расчётных значениях
В случаях исходных условий b(( <) < b'* и расчётных значений b((<) >bi; нормировочный коэффициент р следует рассчитывать по формуле: b*
Важно отметить: нормированию подлежат только те значения переменных X (к), которые обеспечивают соблюдение i — того невыполненного ресурсного ограничения.
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
Пример расчёта о. о. оценок методом структурной оптимизации.
Двойственной (или обратной) задаче линейного программирования (5) и (2) служит задача (6) — (7):
G= 140y1 + 64y2 + 64y3 ^ min, при ограничениях: 7y1 + 4y2 + y3 > 12
6y1 + У2 + 4y3 > 11
1. Расчёт значений исходных (базисных) коэффициентов (У^(к)) структуры потребления i -того вида ограниченных ресурсов при j — том способе их использования, определяемые по формуле Yijlc)= а^j^ aiJ, которые на этой итерации примут значения Yijr> и составят:
при i = 1: 0,583; 0,333; 0,084
i = 2: 0,545; 0,091; 0,364
2. Поскольку данная задача предусматривает минимизацию целевой функции, то на этом шаге вычислений из найденных значений Y() для каждого j выбираем значение
коэффициента Yjk) = max Y(). В нашем примере это величины:
Y1(1) = 0,583 ; Y2(1) = 0,333 и Y3(1) = 0,364
3. Расчёт потребности в ограниченных ресурсах Ь1 при найденных значениях YJ< ) по формуле: Ь(к)= 2 аг>^1
b = 7 • 0,583 + 4 • 0.333 +1 • 0,364 = 5,777
Ь1 = 6 — 0,583 +1 — 0.333 + 4 — 0,364 = 5,287 Продолжаем вычисления, поскольку не соблюдены линейные ограничения .
1. Корректируем значения базисных коэффициентов Y^(1) по формуле Yj■k+1) = Yj■k) — bi /Ьк .
при i = 1: 1,211 (0,58342/5,777); 0,692 (0,33342/5,777); 0,174 (0,084-12/5,777); i = 2: 1,134 (0,545^ 11/5,287); 0,189 (0,09141/5,287); 0,757 (0,364-11/5,287)
2. ^(2)=1,211; Y2(2) =0,692: Yз(2) = 0,757
3. Ь12 = 7-1,211 + 4-0,692 +1-0,757 = 12,002 Ь22 = 6 -1,211 +1-0,692 + 4 — 0,757 = 10,986
Вычисления следует продолжить, поскольку не соблюдено второе ограничение.
1. Корректируем значения базисных коэффициентов Y^(1) по формуле Yj■k+1) = Yj■k) — bi /Ьк .
i=1: 1,211 (1,211^ 12,0/12,002); 0,692 (0,69242,0/12,002); 0,174 (0,17442,0/12,002); i=2: 1,135 (1,134 • 11,0/10,986); 0,189 (0,189 41,0/10,986); 0,758 (0,757 -11,0/10,986).
2. ^(2)=1,211; Y2(2) =0,692: Y3(2) = 0,758
3. Ь12 = 7-1,211 + 4-0,692 +1-0,758 = 12,003 Ь22 = 6 -1,211 +1 — 0,692 + 4 — 0,758 = 10,99
Для сокращения процесса вычислений произведём нормирование значений переменных по формулам (21) и (22). Имеем:
Y|■n)= 1,212; Y2n) = 0,693; Y3(n) = 0,759; С1* =12,014; С2* =11,0
Р = max—к- = —-— = 1,0009;
3. Упрощённый алгоритм решения задач линейного программирования методом
Использование упрощённого алгоритма предусматривает выполнение следующих действий:
1. Расчёт суммарной интенсивности потребления ограниченных ресурсов Aj для каждого (j — того) технологического способа потребления ограничений:
2. Расчёт предельных значений прототипов ограничений В< для каждого вида ограничений:
3. Расчёт значений коэффициентов корректировки у, величин Aj:
4. Выбор предельного значения коэффициента корректировки у *:
4.1. Для задач линейного программирования с ограничениями « < »:
4.2. Для задач линейного программирования с ограничениями « > »:
5. Расчёт значений неизвестных задачи линейного программирования:
6. Определяем потребности в ресурсах для найденного решения задачи линейного программирования :
7. Определение значения функции цели:
Рассмотрим пример реализации упрощённого алгоритма метода структурной оптимизации (экспресс алгоритма) на примере задачи линейного программирования (5) и
(2), а именно: F= 12х1 + 11х2 ^ max
1. Имеем: Аi = 7+4+1 = 12; А2 = 6+1+4 = 11.
2. Имеем: Bi = 7-12+6-11=150; В2 = 4-12+1^11=59; В3 = 1-12+4-11=56.
3. Имеем: у =-= 0,933 ; у2 = — = 1,085 ; у3 = — = 1,143 .
4.1. Для данной задачи имеем: у * = 0,933.
5. Имеем: X = 12-0,933 = 11,196; Х2 = 11-0,933 = 10,263.
6. Имеем: 7-11,196 + 6-10,263 = 140,0
4-11,196 + 1-10,263 = 55,05
1-11,196 + 4-10,263 = 52,25 F= 12×1 + 11×2 = 12-11,196 + 11-10,263 = 247, 245
Упрощённая реализация решения задачи линейного программирования (6)-(7):
G= 140у1 + 64у2 + 64у3 ^ min,
7у1 + 4у2 + у3>12 6у1 + У2 + 4уз > 11
при использовании упрощённого алгоритма метода структурной оптимизации примет вид:
1. Имеем: А1 = 7+6 = 13; А2 = 4+1 = 5; Аз = 1+4 = 5.
2. Имеем: В1 = 7-13 + 4-5 + 1-5 = 116; В2 = 6-13 + 1-5 + 4-5 = 103
3. Имеем: у = — = 0,1034; у2 = — = 0,1068.
4. Учитывая тип ограничений для данной задачи (« > »), имеем: у * = 0,1068.
5. Имеем: 71 = 13-0,1068 = 1,388; У2 = 5-0,1068 = 0,534; У3 = 5-0,1068 = 0,534.
6. Значения ограничений для найденного решения задачи линейного программирования составит:
7-1,388 + 4-0,534 + 1-0,534 = 12,386 6-1,388 + 1-0,534 + 4-0,534 = 10,998.
7. Значение функции цели: G= 1404,388 + 64-0,534 + 64-0,534 = 262,672
Приведённые примеры свидетельствуют, что упрощённый алгоритм метода структурной оптимизации позволяет получать достаточно точные решения любых систем линейных неравенств и задач линейного программирования, предусматривающих оптимизацию использования заданных ограничений.
Подводя итоги презентации метода структурной оптимизации следует отметить простоту и универсальность его использования при поиске оптимальных планов или способов производства продукции в условиях ограниченности используемых ресурсов производства.
В работе также показано, что любые дополнительные критерии эффективности и значимости продукции или технологических способов её производства — коэффициенты функции цели в задачах линейного программирования — контрпродуктивны критерию эффективного использования заданных ограничений. Объективность этого постулата подтверждается не только примерами, приведёнными в данной работе, но и самим фактом лимитированности ресурсов. Более того, рост национального богатства обеспечивают только те предприниматели, которые получают прибыль от увеличения объёмов производства продукции при базисных затратах производства, а не за счёт их экономии и высвобождения.
Для оценки степени практической реализации этого принципа при сравнении вариантов планов, составленных различными методами, в данной работе предложен комплексный показатель эффективности плановых расчетов — Ерг. Преимуществом показателя Ерг служит то, что его величина пропорциональна величине возможных потерь от неполноты и некомплектности использования располагаемых ресурсов, т.е. тех факторов, которые символизируют потери ресурсов в процессе народнохозяйственного планирования, но до сих пор не служили критериями качества плановых решений. Поэтому тот факт, что метод структурной оптимизации позволяет улучшить (уменьшить) значение этих показателей при тех же объёмах располагаемых ресурсов производства позволяет сделать вывод о высокой эффективности и перспективности использования
метода структурной оптимизации при решении производственных задач линейного программирования и в процессе народнохозяйственного планирования.
На сегодняшний день метод структурной оптимизации служит единственным инструментом способным обеспечить реализацию в планировании производства принципа демократического централизма, т.е. условий, при которых оптимизация планов отдельных производителей обеспечит оптимальное развитие общественного производства в стране.
Результаты использования метода структурной оптимизации может служить также инструментом для уточнения обоснованности оценок экономической эффективности нововведений. Для этого следует расчётные величины оценок экономической эффективности нововведений уменьшить на величину прироста затрат производства в оптимальном плане, либо увеличить оценку экономического эффекта на величину их сокращения.
[1] Канторович Л.В. «Экономический расчёт наилучшего использования ресурсов».
Из-во Академии Наук СССР, Москва. 1960г.
[2] Лопатников, 2003. Объективно обусловленные оценки — Лопатников —
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
[3] DANTZIG G.B. Reminiscences About the Origins of Linear Programming
//Mathematical Programming: The State of the Art / Ed. by A. Bachem, M. Groetschel and
B. Korte.-Berlin: Springer Verlag,1983.-P.79-86.
[4] Тарасов В.Л. Экономико-математические методы и модели. Учебное пособие.
Нижний Новгород, 2003 г. (unn038.pdf — Adobe Reader)