Методичка по методам оптимальных решений. Методы принятия оптимальных решений

Методы оптимальных решений

СОДЕРЖАНИЕ

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

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

Таблица 1.График самостоятельной работы по дисциплине «Методы оптимальных решений»

Содержание Сроки сдачи Критерии оценки
1.Изучение теоретического материала

2. Решение заданий кон-трольной работы За 1,5 месяца до сессии Каждое задание оцени-вается по десятибалль-ной системе
3. Подготовка к итоговой атт естации Во время сессии

1. ВВЕДЕНИЕ. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ

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

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

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

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

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

Под принятием решений в курсе «Методы оптимальных решений» понимают сложный процесс, в котором можно выделить следующие основные этапы:

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

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

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

3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия решения.

Широкий класс задач управления составляют такие экстремальные задачи, в математических моделях которых условия на переменные задаются равенствами и неравенствами. Теория и методы решения этих задач как раз и составляют содержание математического программирования. На третьем этапе, пользуясь математическим аппаратом, находят решение соответствующих экстремальных задач. Обратим внимание на то, что задачи матема-тического программирования, связанные с решением практических вопросов, как правило, имеют большое число переменных и ограничений. Объем вычислительных работ для нахождения соответствующих решений столь велик, что весь процесс не мыслится без применения современных электронных вычислительных машин (ЭВМ), а значит, требует либо создания программ для ЭВМ, реализующих те или иные алгоритмы, либо использования уже имеющихся стандартных программ.

4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая:

1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и, в случае необходимости, уточняется постановка задачи (1-й этап); уточняется или строится заново математическая модель (2-й этап); решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).

2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.

В математическом программировании можно выделить два направления.

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

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

Традиционно в математическом программировании выделяют следующие основные разделы:

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

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

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

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

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

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

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

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

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

Задача линейного программирования (ЗЛП):

найти вектор X = (x 1 ,x 2 ,...,x n) максимизирующий линейную форму

F = Σ c j x j → max (2.1)

J=1

и удовлетворяющий условиям:

Σa ij x j ≤ b i (2.2)

J=1

x j ≥0 , j = 1,…,n (2.3)

Линейная функция F называется целевой функцией задачи.

Перепишем эту задачу в векторной форме:

Найдем тах функции:

F = c 1 x 1 + c 2 x 2 + … + c n x n (2.4)

x 1 P 1 + x 2 P 2 + … + x n P n = P 0 , (2.5)

x j ≥0 , j = 1,…,n (2.6)

где P 1 , …, P n и P 0 - m-мерные вектор столбцы, из коэффициентов при неизвестных и свободных членов системы уравнений задачи:

B 1 a 11 a 12 a 1n

P 0 = (b 2) ; P 1 = (a 21) ; P 2 = (a 22) ;……. P n = (a 2n) ; (2.7)

… … … …

B n a m1 a m2 a mn

План X = (x 1 ,x 2 ,...,x n) называется опорным планом основной ЗЛП, если положительные коэффициенты х j стоят при линейно независимых векторах Р j .

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

Теорема

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

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

Выводы:

Непустое множество планов основной ЗЛП образует выпуклый многогранник;

Каждая вершина этого многогранника определяет опорный план;

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

Двумерный случай ЗЛП

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

F = c 1 x 1 + c 2 x 2 (2.8)

при условиях

a i1 x 1 + a i2 x 2 ≤ b i , (i=1,…,k) (2.9)

x j ≥0 (j=1,2) (2.10)

Задача линейного программирования состоит в нахождении такой точ-ки многоугольника решений, в которой целевая функция F принимает максимальное значение. Эта точка существует тогда, когда многоугольник ре-шений не пуст и на нем целевая функция ограничена сверху.

Для определения данной вершины построим линию уровня c 1 x 1 +c 2 x 2 =h, (где h – некоторая постоянная), проходящую через многоугольник решений, и будем передвигать ее в направлении вектора С=(с 1 ,с 2) до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений. Координаты указанной точки и определяют оптимальный план данной задачи.

Этапы решения ЗЛП геометрическим методом:

1. Построить прямые по уравнениям (2.9), (2.10).

2. Найти полуплоскости, определяемые каждым из ограничений задачи.

3. Найти многоугольник решений.

4. Построить вектор С.

5. Построить прямую c 1 x 1 +c 2 x 2 =h, проходящую через многоугольник решений.

6. Передвинуть прямую c 1 x 1 +c 2 x 2 =h в направлении вектора С.

7. Определить координаты точки максимума функции и вычислить значение целевой функции в этой точке.

Пример 1.

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

Таблица 2.1

В иды сырья
 		Нормы расхода сырья (кг)
на одно изделие 		Общее количество сырья (кг)
А
 		В
1
12 4 300
2
4 4 120
3
 		3 12 252
Прибыль одного изделия от реализации (руб.)
 		30 40

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

Решение:

х1 – выпуск изделий вида А

х2 – выпуск изделий вида В

Тогда ограничения задачи:

Общая прибыль от реализации изделий вида А и В составит: F = 30х 1 + 40x 2

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

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

Найдем координаты точки В – пересечения прямых:

Решив эту систему уравнений, получим: x 1 = 12 ; x 2 = 18

Следовательно, если предприятие изготовит 12 изделий вида А и 18 изделий вида В, то оно получит максимальную прибыль, равную

F max = 30·12+40·18 = 1080 руб.

Пример 2.

Решить ЗЛП

max(min)F = 2x 1 +3x 2 ;

Решение. Для построения области допустимых решений строим в системе x 1 Ox 2 соответствующие данным ограничениям-неравенствам граничные прямые:

x 1 +x 2 ≤ 6, x 1 +4x 2 ≥ 4, 2x 1 -x 2­ ≥ 0.

Находим полуплоскости, в которых выполняются данные неравенства. Для этого вследствие выпуклости любой полуплоскости достаточно взять произвольную точку, через которую не проходит соответствующая граничная прямая, и проверить, удовлетворяет ли эта пробная точка ограничению-неравенству. Если удовлетворяет, то данное неравенство выполняется в по-луплоскости, содержащей пробную точку. В противном случае берется полуплоскость, не содержащая пробной точки. В качестве пробной точки часто удобно брать начало координат О(0; 0). Для нашего примера область допус-тимых решений - множество точек четырехугольника АВСD (рис. 6).

Строим вектор с = (с 1 ; с 2) = (2; 3). Так как он необходим лишь для вы-яснения направления возрастания целевой функции, иногда для большей на-глядности удобно строить λс(λ > 0). Перпендикулярно к вектору с проводим линию уровня F=0. Параллельным перемещением прямой F=0 находим край-нюю точку В. в которой целевая функция принимает максимальное значение и точку А, в которой достигается минимальное значение.

Координаты точки В определяются системой


Откуда Fmax = F (A) = 32/9

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задачи 1.1-1.10 решить графически.

Задача со многими переменными

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

Для того чтобы решить еѐ графически, следует преобразовать систему ограничений таким образом, чтобы в форме основной задачи система вклю-чала не более 2-х переменных.

Сделать это можно, последовательно, исключая переменные или мето-дом Жордана-Гаусса. Рассмотрим метод Жордана-Гаусса.

Таблица 1


x 1 x 2
x 3
x 4
x 5
b

7

3

2

2

3

1

1

1

6

3

3

-1

1

1

0

0

1

0

1

-1

10

3

4

0

(-3) 1 , (-1) 3,4

Таблица 2

x 2

-2

3

1

-1

0

1

0

0

-3

3

0

-4

-2

1

1

-1

1

0

-1

-1

1

3

-1

-3

(2) 1 , (-1) 2 ,(1) 3

Таблица 3

x 2

x 4

0

2

1

0

0

1

0

0

3

3

0

-4

0

0

1

0

1

1

-1

-2

1

4

-1

-4

(-1) 2 , (1) 3 ,(2) 4

Таблица 4

x 5

x 2

x 4

0

2

1

0

0

1

0

0

3

0

3

2

0

0

1

0

1

0

0

0

1

3

0

-2

(-1) 2 , (1) 3 ,(2) 4

Отбросим в уравнениях-ограничениях неотрицательные разрешенные неизвестные

x 2 , x 4 , x 5 и заменим знак равенства знаками неравенства, по-лучим вспомогательную задачу линейного программирования с двумя переменными:

F (x) = 2 x 3 +2 → max

F (x) = 0: 2 x 3 +2 -0 (0;-1) ;(5;-1)

F max = 2 при x 1 = 0; x 3 = 0

3. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

3.1. Геометрическая интерпретация симплексного метода

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

Симплексный метод состоит в:

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

2) переходе к лучшему решению;

3) проверке оптимального допустимого решения.

3.2. Табличная интерпретация симплексного метода

Симплексным методом решаются задачи линейного программирования, записанные в канонической форме:

Найти оптимальное решение

X = (x 1 ,x 2 ,...,x n) (3.1)

удовлетворяющее системе ограничений (уравнений)

Σa ij x j = b i (i=1,m) (3.2)

j=1

и условиям x j ≥ 0 (j=1,n)

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

Z(x) = Σ c j x j (3.3)

j=1

Пусть найдено первоначальное неотрицательное базисное решение системы (3.2), где х 1, х 2 , х 3 … х m - базисные неизвестные, а х m+1 , x m+2 , …, x n – свободные неизвестные.

Тогда система (3.2) превращается в разрешенную систему

(3.4)

Данной системе соответствует неотрицательное базисное решение вида

X 0 = (b 1 ,b 2 ,...,b m ,0,0...0)

Подставим полученное решение в целевую функцию

Δ 0 = L(X 0) = Σ C j B j (3.5)

J=1

и преобразуем ее таким образом, чтобы она зависела только от свобод-ных неизвестных х m+1, х m+2 , … х n

Все базисные неизвестные х 1, х 2 , х 3 … х m выразим через свободные х m+1, х m+2 , … х n и подставим в целевую функцию.

Тогда целевая функция примет вид (3.6)

Введем понятие оценки Δ j свободных неизвестных

(3.7)

Тогда целевая функция примет вид

(3.8)

Введем в рассмотрение векторы C = (c 1 , c 2 , …, c m) и B = (a 1j , a 2j , …, a mj) (j=m+1,n), тогда равенство (3.7) можно записать в векторной форме

Δ j =CB j -c j (3.9)

Равенство (3.8) по характеру записи не отличается от уравнений систе-мы, поэтому добавим его к этой системе и получим расширенную систему:

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

Б.Н.
C
B
c 1 c 2 ... c m c m+1 ... c j ... c n
x 1 x 2 ... x m x m+1 ... x j ... x n
x 1 c 1 β 1
1 0 ...
0 a 1(m+1) ...
a 1j ...
a 1n
x 2
c 2
β 2
0 1 ...
0 a 2(m+1)
...
a 2j
...
a 2n
... ... ... ...
...
... ...
...
...
...
...
...
x m
c m
β m
0 0 ...
1 a m(m+1)
...
a mj
...
a mn
L(X) Δ j ≥0
Δ 0
0 0 ...
0 Δ m+1
...
Δ j
...
Δ n

первом столбце записаны базисные неизвестные x 1 ,x 2 , …, x m ; в столбце C записаны коэффициенты из целевой функции, соответствующие этим базисным неизвестным; в столбце B - свободные члены уравнений системы, совпадающие с положительными компонентами первоначального неотрицательного базисного решения X 0 . Под неизвестными x 1 ,x 2 , …, x n в столбцах записаны коэффициенты из системы.

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

В оценочной строке неравенство Δ j ≥0 и означает критерий оптимальности опорного плана.

Алгоритм решения ЗЛП симплекс-методом.

1. Найти опорный план.

2. Составить симплекс-таблицу.

3. Выяснить, имеется ли хотя бы одно отрицательное число Δ j

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

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

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

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

Пример 3.1.

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

Составить план производства изделий, при котором общая стоимость всей произведенной продукции будет максимальной.

Решение:

Составим математическую модель. Обозначим:

х 1 – выпуск изделий вида А;

х 2 – выпуск изделий вида В;

х3 – выпуск изделий вида С.

Запишем систему ограничений:

Общая стоимость произведенных товаров составляет:

F = 9x 1 +10x 2 +16x 3

По экономическому содержанию переменные х 1 , х 2 , х 3 могут принимать только неотрицательные значения:

x 1 ,x 2 ,x 3 ≥0

Запишем эту задачу в виде основной ЗЛП, для этого перейдем от системы неравенств к равенствам, для этого введем три дополнительные переменные:

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

Запишем преобразованную систему уравнений в векторной форме:

x 1 P 1 +x 2 P 2 +x 3 P 3 +x 4 P 4 +x 5 P 5 +x 6 P 6 =P 0

где

Поскольку среди векторов Рj имеется три единичных вектора, то дляданной задачи можно записать опорный план Х=(0, 0, 0, 360, 192, 180) определяемый системой единичных векторов Р 4 , Р 5 , Р 6 , которые образуют базис трехмерного пространства.

Составляем симплексную таблицу I итерации и подсчитываем значения F 0 , z j -c j .

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

F 0 = (С,P 0)=0; z 1 =(С,P 1)=0; z 2 =(С,P 2)=0; z 3 =(С,P 3)=0;

z 1 -c 1 = 0-9 = -9; z 2 -c 2 = 0-10 = -10; z 3 -c 3 = 0-16 = -16;

Для векторов базиса z j -c j = 0 (j=4,5,6).

Максимальное отрицательное число Δ j стоит в 4-ой строке столбца Р 3 . Следовательно, в базис введем вектор Р 3 . Определим вектор, подлежащий исключению из базиса, для этого находим Θ 0 = min(b i /a ij) для a i3 >0 т.е. Θ = min (360/12 ; 192/8; 180/3) =192/8 =24.

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

Следовательно, вектор Р 5 подлежит исключению из базиса. Столбец вектора Р 3 и 2-я строка являются направляющими.

Составим таблицу II итерации. Сначала заполняем строку вектора, вновь введенного в базис, т.е. направляющую строку 2. Элементы этой строки получаются путем деления соответствующих элементов таблицы 1 наразрешающий элемент (т.е. 8). При этом в столбец С б записываем коэффи циент С 3 =16, стоящий в столбце вводимого в базис вектора Р 3

Для определения остальных элементов таблицы II применим правило треугольника.

Вычислим элементы таблицы II, стоящие в столбце Р 0 .

Первый элемент - находим три числа

1) число, стоящее в т. 1 на пересечении столбца Р0 и 1-ой строки (360);

2) число, стоящее в т. 1 на пересечении столбца Р3 и 1-ой строки (12);

3) число, стоящее в т. 2 на пересечении столбца Р0 и 2-ой строки (24).

360-12·24 = 72

Второй элемент был вычислен ранее (Θ 0 = 192/8 =24)

Третий элемент -

1) число, стоящее в т. 1 на пересечении столбца Р0 и 3-ой строки (180);

2) число, стоящее в т. 1 на пересечении столбца Р3 и 3-ой строки (3);

3) число, стоящее в т. 2 на пересечении столбца Р0 и 2-ой строки (24).

180-3·24 =108

Значение F 0 в 4-ой строке этого же столбца можно найти двумя спосо бами:

1) по формуле F 0 =(C,P 0) = 0·72+16·24+0·108 = 384;

2) по правилу треугольника:

Вычислим элементы вектора Р 1 т.2. Первые два числа берем из столб цов Р 1 и Р 3 т.1,

а третье число – из т.2 на пересечении 2-ой строки и столбца Р1.

18-12 (3/ 4) = 9; 5-3 (3/ 4)=11/ 4.

Число z 1 -c 1 в 4-й строке столбца вектора P 1 таблице 2

можно найти двумя способами:

1) по формуле z 1 -с 1 =(C,P 1)-c 1 имеем:

0·9+16·3/ 4+0·11/ 4-9 =3

2) по правилу треугольника получим:

-9-(-16) 3/ 4 = 3

Аналогично находим элементы столбца вектора P 2 .

Элементы столбца вектора Р 5 вычисляем по правилу треугольника.

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

При вычислении элемента 1-й строки указанного столбца получается треугольник, образованный числами 0;12 и 1/8. Следовательно, искомый элемент равен

0 – 12 (1/8) = -3/2.

Элемент, стоящий в 3-й строке данного столбца, равен

0 - 3 (1 /8) = -3/8.

По окончании расчета всех элементов таблица II в ней получены но вый опорный план и коэффициенты разложения векторов Р j через базисные векторы P 4 , P 3 , P 6 и значения F 0 " Δ j ".

Как видно из этой таблицы, новым опорным планом задачи является план X=(0; 0; 24; 72; 0; 108).

Найденный на II итерации план задачи не является оптимальным.

этой строки стоит отрицательное число – 2. Это видно и из 4-й строки таблицы 2, поскольку в столбце вектора P 2 .

Значит, в базис следует ввести вектор P 2 , т. е. в новом плане следует предусмотреть выпуск изделий В.

При определении возможного числа изготовления изделий В следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий В определяется min (b i "/a i 2") для a i2 ">0 т.е. находим Θ 0 = min(72/9; 24·2/1; 108·2/3) = 72/9=8.

Следовательно, исключению из базиса подлежит вектор Р4 иными словами, выпуск изделий В ограничен имеющимся в распоряжении предприятия сырьем I вида. С учетом имеющихся объемов этого сырья предприятию следует изготовить 8 изделий В. Число 9 является разрешающим элементом, а столбец вектора P2 и 1-я строка таблицы 2 являются направляющими.

Составим таблицу для III итерации.


В таблице III сначала заполняем элементы 1-й строки, которая представляет собой строку вновь вводимого в базис вектора Р2. Элементы этой строки получаем из элементов 1-й строки таблицы 2 делением последних на разрешающий элемент (т.е. на 9).

При этом в столбце С б данной строки записываем с 2 =10.

Затем заполняем элементы столбцов векторов базиса и по правилу треугольника вычисляем элементы остальных столбцов.

В результате в таблице III получаем новый опорный план X=(0; 8; 20; 0; 0; 96) и коэффициенты разложения векторов Р j через базисные векторы P 1 , P 2 и P 3 соответствующие значения F 0 "" и Δ j .

Проверяем, является ли данный опорный план оптимальным или нет. Для этого рассмотрим 4-ю строку, таблицы 3 . В этой строке среди чисел нет отрицательных. Это означает, что найденный опорный план является оптимальным и F max =400.

Следовательно, план выпуска продукции, включающий изготовление 8 изделий В и 20 изделий С, является оптимальным. При данном плане выпуска изделий полностью используется сырье I и II видов и остается неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 €.

Оптимальным планом производства продукции не предусматривается изготовление изделий А. Введение в план выпуска продукции изделий вида А привело бы к уменьшению указанной общей стоимости. Это видно из 4-й строки столбца вектора P1, где число 5 показывает, что при данном плане включение в него выпуска единицы изделия А приводит лишь к уменьшению общей величины стоимости на 5 €.

Пример 3.2

Заполнить первоначальную симплексную таблицу для следующей ЗЛП:


Решение:

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

-во вторую строку запишем неизвестные x 1 ,x 2 , …, x 5 ;

-в первой строке над ними – соответствующие коэффициенты 3, -2, 1,4,-1 из целевой функции;

-под неизвестными x 1 ,x 2 , …, x 5 , заполним столбцы, составленные из соответствующих коэффициентов левых частей уравнений исходной системы;

-в столбец запишем свободные члены уравнений 3,1,5;

-в первый столбец Б.п. поместим неизвестные x 2 ,x 3 , x 5 , так как под ними стоят единичные столбцы, и поэтому их будем считать базисными; базисные неизвестные располагаются в таком порядке, чтобы единицы в столбцах находились на пересечении одинаковых неизвестных;

-в столбец запишем коэффициенты -2,1,-1, из целевой функции при выбранных базисных неизвестных x 2 ,x 3 , x 5 ;

-заполним оценочную строку следующим образом: под столбцом B поместим число Δ 0 , вычисленное по формуле (3.5); под базисными неизвестными x 2 ,x 3 , x 5 - нули, которые можно получить и из равенства (3.9); под свободными переменными x 1 , x 4 - запишем значения, полученные из равенства (3.9).

Результаты выполнения этих действий запишем в следующую таблицу:


Выберем в качестве разрешающего столбец х 4 , как самый «плохой» (ему соответствует наибольшая по модулю отрицательная оценка). Далее введем разрешающую строку следующим образом: для положительных коэффициентов столбца х 4 вычислим отношения b i /a i4 запишем их в графу θ.

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

На пересечении разрешающей строки и разрешающего столбца выделим разрешающий элемент. Добьемся, чтобы разрешающий элемент равнялся единице, для чего всю первую строку разделим на два. Далее преобразуем таблицу методом Жордана-Гаусса.

Таким образом, уже в таблице второго шага критерий оптимальности выполнен. Мы получили оптимальный план Х(0;0;11/2;3/2;13/2), max L(X) =5.


ЗАДАЧА 1 . Симплексный метод решения задач линейного программирования
Для изготовления различных видов продукции 1, 2, 3 и 4 предприятие использует три вида сырья А, В и С. Нормы расхода сырья на производство единицы продукции каждого вида, цена одного изделия, а также запас каждого вида ресурса известны и приведены в таблице 1.1.
Составить такой план производства продукции, при котором предприятие получит максимальную прибыль.

Исходные данные задачи выбрать в таблицах 1.1, 1.2 в соответствии с вариантом.

Таблица 1.1 – Нормативы затрат ресурсов на единицу продукции каждого вида (общие для всех вариантов)

РЕСУРС ВИДЫ ПРОДУКЦИИ ЗАПАС
1 2 3 4
А 6 8 4 7 a 5
В 0,75 0,64 0,5 0,8 a 6
С 8 12 10 14 a 7
ЭКОНОМИЧЕСКИЙ a 3 a 4 МАХ

План решения задачи:

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

ЗАДАЧА 2
Решение открытой транспортной задачи методом потенциалов
На оптовых складах А 1 , А 2 , А 3 , А 4 имеются запасы некоторого продукта в известных количествах, который необходимо доставить в магазины В 1, В 2, В 3, В 4, В 5. Известны также тарифы на перевозку единицы продукта из каждого склада в каждый магазин.
Найти такой вариант прикрепления магазинов к складам, при котором сумма затрат на перевозку была бы минимальной.
Исходные данные задачи выбрать в таблицах 2.1, 2.2 в соответствии с вариантом.
Таблица 2.1 – Матрица тарифов (общая для всех вариантов)

Оптовые склады Магазины Запасы
В 1 В 2 В 3 В 4 В 5
А 1 5 4 10 7 8 a 6
А 2 7 6 7 10 6 a 7
А 3 2 9 5 3 4 a 8
А 4 6 11 4 12 5 a 9
Потребности a 3 a 4

План решения задачи:
  1. Проверить, является решаемая задача закрытой или открытой.
  2. Если задача открытая – выполнить действия, дающие возможность приступить к её решению.
  3. Вычертить матрицу транспортной задачи и записать в неё опорный план, пользуясь одним из известных вам способов построения опорного плана (способ северо-западного угла, наилучшего тарифа, двойного предпочтения).
  4. Проверить построенный опорный план на вырождение. Если надо, принять меры для преодоления вырождения опорного плана.
  5. Рассчитать значение целевой функции для опорного плана.
  6. По правилам метода потенциалов рассчитать потенциалы строк и столбцов.
  7. Используя найденные потенциалы, проверить построенный опорный план на оптимальность.
  8. Если решение оптимальное перейти к пункту 13.
  9. Если решение неоптимальное, его нужно улучшить. Для этого надо найти клетку матрицы транспортной задачи, подлежащую улучшению, построить для неё замкнутый цикл, определить объём ресурсов для перемещения по вершинам этого цикла.
  10. Выполнить перемещение ресурсов по вершинам цикла, не нарушая баланса по строкам и столбцам матрицы.
  11. Перейти к пункту 6.
  12. Выписать оптимальное решение и провести его экономический анализ.

ЗАДАЧА 3 . Оптимальное распределение ресурсов.
Совет директоров фирмы рассматривает предложение по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, принадлежащих фирме.
Для модернизации предприятий совет директоров инвестирует средства в объеме 250 млн. р. с дискретностью 50 млн. р. Прирост выпуска продукции зависит от выделенной суммы, его значения предоставлены предприятиями и содержатся в таблице.
Найти предложение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить только одну инвестицию.
Исходные данные задачи выбрать в таблицах 3.1, 3.2 в соответствии с вариантом.
Таблица 3.1 – Значения параметров задачи

Инвестиции, млн. руб. Прирост выпуска продукции, млн.руб.
Предприятие Предприятие Предприятие Предприятие
50 а 11 а 12 а 13 а 14
100 а 21 а 22 а 23 а 24
150 а 31 а 32 а 33 а 34
200 а 41 а 42 а 43 а 44
250 а 51 а 52 а 53 а 54

План решения задачи:
  1. Выбрать из таблиц исходные данные своего варианта.
  2. Разбить решение задачи на этапы по количеству предприятий, на которые предполагается осуществить инвестиции.
  3. Составить рекуррентные соотношения
  4. Провести первый этап расчета, когда инвестиции выделяются только первому предприятию
  5. Провести второй этап расчета, когда инвестиции выделяют первому и второму предприятиям
  6. Провести третий этап расчета, когда инвестиции выделяют 1-3-му предприятиям
  7. Провести четвертый этап расчета, когда инвестиции распределяются между четырь­мя предприятиями
  8. Выписать оптимальное решение и провести его экономический анализ.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

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

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

2. Графический метод основан на геометрической интерпретации за дачи линейного программирования

1. Графически могут решаться:

Задачи, заданные в стандартной форме, содержащие не более двух переменных;

Задачи, заданные в канонической форме с числом свободных переменных (r - ранг матрицы системы ограничений);

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

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

3. Методика решения задач ЛП графическим методом

I.В ограничениях задачи заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства. Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

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

IV. Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V. Построить вектор, который начинается в точке (0;0) и заканчивается в точке. Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

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

VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится.

4 . Как построить первоначальный опорный план задачи ЛП в симплексном методе и проверить его оптимальность

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

5 . Как определить переменную (вектор) для включения в базис и переменную (вектор) подлежащую исключению из базиса

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

Симплексное отношение (Q) = Элементы столбца свободных членов

Соответствующие элементы разрешающего столбца

Значения симплексного отношения заносятся в таблицу.

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

6 . Какой метод решения систем линейных уравнений лежит в основе симплекс-метода

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

7. Опишите алгоритм симплекс-метода

Схема решения задачи линейного программирования симплексным методом состоит из следующих основных этапов. 1. Математическая формализация задачи; 2. Приведение системы ограничений к каноническому виду; 3. Поиск опорного решения и нахождение базиса задачи; 4. Построение первой симплексной таблицы; 5. Проверка плана на оптимальность; 6. Последовательное улучшение плана до получения оптимального.

8. Опишите правила построения двойственной задачи ЛП

Правила построения двойственных задач:

Упорядочивается запись исходной задачи (если целевая функция максимизируется, то ограничения неравенства должны быть вида <= если минимизируется то >=), выполнение этих условий достигается умножением соответствующих ограничений на -1.Если прямая задача решается на максимум то двойственная на минимум, и на оборот. К каждому ограничению прямой задачи соответствует переменная двойственной задачи и наоборот. Матрица системы ограничений двойственной задачи получается из матрицы системы ограничений прямой задачи транспонированием.Свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной и наоборот Если на переменную прямой задачи наложено условие не отрицательности то соответствующее ограничение двойственной задачи записывается как ограничение неравенства, если же нет то как ограничение равенства. Если какое либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие не отрицательности не налагается.

9 . Какова экономическая интерпретация двойственных оценок

С экономической точки зрения двойственную задачу можно интерпретировать так:

какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов b i и величинах стоимости единицы продукции C j минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции x j (j =1,2,…, n) необходимо произвести, чтобы при заданных стоимостях C j (j =1,2,…, n) единицы продукции и размерах имеющихся ресурсов b i (i =1,2,…, n) максимизировать выпуск продукции в стоимостном выражении.

1 0 . Каким образом определяются двойственные оценки из последней симплексной таблицы

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

1 1 . Сформулируйте задачу оптимального планирования производства и запишите ее в виде модели ЛП

Некоторое предприятие производит n типов продукции, затрачивая при этом m типов ресурсов. Известны следующие параметры: aij - количество i-го ресурса, необходимое для производства единичного количества j-й продукции; aij0 (i=1,…,m; j=1,…,n);

bi-запас i-го ресурса на предприятии, bi>0;

cj-цена единичного количества j-й продукции, cj>0.

Предполагается, что затраты ресурсов растут прямо пропорционально объему производства. Пусть xj - планируемый объем производства j-й продукции. Тогда допустимым является только такой набор производимой продукции x=(x1,x2,…,xn), при котором суммарные затраты каждого вида i-го ресурса не превосходят его запаса:

Кроме того, имеем следующее ограничение: xj0; j=1,…,n. (2)

Стоимость набора продукции x выражается величиной: (3)

Задача планирования производства ставится следующим образом: среди всех векторов x, удовлетворяющим ограничениям (1), (2), найти такой, при котором величина (3) принимает наибольшее значение.

1 2 . Сформулируйте задачу оптимального состава смеси и запишите ее в виде модели ЛП

Пусть имеется m видов сырья, запасы которого составляют соответственно d1,…, dm. Из этого сырья необходимо составить смесь, содержащую n веществ, определяющих технические характеристики смеси. Известны величины aij (i =1,m; j =1, n) ,определяющие количество j-го вещества в единице i -го вида сырья, цена которого равна сi (i = 1,m), а также b j (j = 1,n) ?наименьшее допустимое количество j-го вещества в смеси.

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

Цель задачи (целевая функция) - минимизировать суммарные затраты на сырье.

Найти вектор X = (x 1 , x 2, …, x n), удовлетворяющий системе ограничений:

и доставляющий целевой функции минимальное значение.

1 3 . Сформулируйте транспортную задачу ЛП и запишите ее модель

Транспортная задача (transportation problem) - одна из наиболее распространенных задач математического программирования (обычно - линейного). В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям и наоборот. В простейшем виде, когда распределяется один вид продукта и потребителям все равно, от кого из поставщиков его получать, задача формулируется следующим образом.

Исходная информация:

Mi - количество единиц груза в i-м пункте отправления (i = 1, 2, …, k);

Nj - потребность в j-м пункте назначения (j = 1, 2, …, l) (в единицах груза);

aij - стоимость перевозки единицы груза из i-гo пункта в j-й.

Обозначим через xij планируемое количество единиц груза для перевозки из i-ro пункта в j-й.

В принятых обозначениях:

Общая (суммарная) стоимость перевозок;

Количество груза, вывозимого из i-ro пункта;

Количество груза, доставляемого в j-и пункт.

В простейшем случае должны выполняться следующие очевидные условия:

Таким образом, математической формулировкой транспортной задачи будет:

при условиях:

Эта задача носит название замкнутой (закрытой, сбалансированной) транспортной модели. Заметим, что условие является естественным условием разрешимости замкнутой транспортной задачи.Более общей транспортной задачей является так называемая открытая (несбалансированная) транспортная модель:

при условиях:

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

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

Если, в модель вводится фиктивный (m+1)-й поставщик, для которого запас груза равен разности между суммарным спросом потребителей и фактическим запасом поставщиков. Все тарифы на доставку груза от фиктивного поставщика считают равным 0: . В транспортную таблицу добавляется одна строка.

В модель вводится фиктивный (n+1)-й потребитель, для которого потребность равна разности между суммарным запасом поставщиков. Все тарифы на доставку груза с фиктивными потребностями считают равными 0: . В транспортную таблицу добавляется один столбец.

15 . Метод потенциалов

Широко распространенным методом решения транспортных задач является метод потенциалов. Если допустимое решение (i=1,2,…,m; j=1,2,…n) транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков (i=1,2,…,m)и потребителей (j=1,2,…,n). Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные. Алгоритм решения транспортных задач методом потенциалов:

а) проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок. b) построить начальное опорное решение (методом минимальной стоимости или каким-либо другим методом), проверить правильность его построения по количеству занятых клеток (их должно быть m+n-1) и убедиться в линейной независимости векторов условий (используется метод вычеркивания). c) построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений, которая имеет бесконечное множество решений. Для нахождения частного решения системы одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задают произвольно некоторое значение (чаще нуль). Остальные потенциалы однозначно определяются по формулам. d) проверить выполнения условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам и те из них, которые больше нуля, записываются в левые нижние углы клеток. Если для всех свободных клеток, то вычисляют значение целевой функции и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, опорное решение не является оптимальным.

e) перейти к опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка. Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину. Клетка со знаком «-», в которой достигается остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным. Далее перейти к пункту 3 данного алгоритма.

МОДЕЛИ СЕТЕВОГО ПЛАНИРОВАНИЯ

1. Каковы цели применения методов СПУ? Охарактеризуйте область применения сетевых методов в с фере экономики

Сетевое планирование - это комплекс графических и расчетных методов организационных мероприятий, обеспечивающих моделирование, анализ и динамическую перестройку плана выполнения сложных проектов и разработок, например, таких как: строительство и реконструкция каких-либо объектов; выполнение научно-исследовательских и конструкторских работ; подготовка производства к выпуску продукции; перевооружение армии. Характерной особенностью таких проектов является то, что они состоят из ряда отдельных, элементарных работ. Они обусловливают друг друга так, что выполнение некоторых работ не может быть начато раньше, чем завершены некоторые другие. Основная цель сетевого планирования и управления - сокращение до минимума продолжительности проекта. Задача сетевого планирования и управления состоит в том, чтобы графически, наглядно и системно отобразить и оптимизировать последовательность и взаимозависимость работ, действий или мероприятий, обеспечивающих своевременное и планомерное достижение конечных целей.

Система СПУ позволяет:

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

2. Что представляет собой сетевой график?

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

3. Что понимается под терминами работа и события, каки е разновидности работ Вы знаете ?

Сетевые модели состоят из трех следующих элементов:

Работа (или задача) Событие (вехи) Связь (зависимость)

Работа (Activity) - это процесс, который необходимо выполнить для получения определенного (заданного) результата, как правило, позволяющего приступить к последующим действиям. Термины "задача" (Task) и "работа" могут быть идентичны, однако в некоторых случаях задачами принято называть выполнение действий, выходящих за рамки непосредственного производства, например "Экспертиза проектной документации" или "Переговоры с заказчиком". Иногда понятие "задача" используют для отображения работ самого низкого уровня иерархии. Событие (Node) - момент изменения состояния системы, в частности, момент начала или окончания любой работы по своей сути является событием, а каждая работа обязательно имеет начальное и конечное события. Работа - это действие или процесс, которые должны произойти для перехода от начального события к конечному. Некоторые события являются общими для нескольких работ, в этом случае свершение события является моментом времени, соответствующим завершению последней из работ, непосредственно предшествующих данному событию. Веха (Milestone) - разновидность события, характеризующая достижение значимых промежуточных результатов (отдельных этапов проекта). Связь (Link) - это логическая зависимость между сроками выполнения отдельных работ и наступления событий. Если для начала выполнения какой-либо работы необходимо завершение другой работы, говорят, что эти работы соединены связью (связаны). Связи по своему существу могут определяться технологией работ, либо их организацией. Соответственно различают технологические и организационные виды связей. Связи могут называться также зависимостями (Relationship), или фиктивными работами (Dummy Activity). Связям не требуются исполнители и прямые затраты времени, однако они могут характеризоваться продолжительностью растяжения (положительным, отрицательным или нулевым).

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

При построении сетевого графика необходимо соблюдать ряд правил.

1. В сетевой модели не должно быть «тупиковых» событий, то есть событий, из которых не выходит ни одна работа, за исключением завершающего события. Здесь либо работа не нужна и её необходимо аннулировать, либо не замечена необходимость определённой работы, следующей за событием для свершения какого-либо последующего события. В таких случаях необходимо тщательное изучение взаимосвязей событий и работ для исправления возникшего недоразумения.

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

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

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

5. Как определяются временные оценки работ и событий?

Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для указания конкретной работы используют код работы Р i,j , состоящий из номеров начального (i-го) и конечного (j-го) событий (рис.1, а). На рис.1, б изображен пример кодирования работ и событий в принятых обозначениях: t ij - продолжительность работы Р i,j , t - ранний срок (ожидаемый момент) осуществления события, t * - поздний срок (предельный момент) осуществления события, n - номер события, n см - номер предшествующего (смежного) события.

Рис.1. Обозначение элементов сетевого графика: а - код работы; б - пример кодирования событий в принятых обозначениях; в - пример изображения события в принятых выше обозначениях.

На рис.1 в приведён пример изображения события в принятых выше обозначениях. Обозначим через множество работ, входящих в j-е событие, а через - множество работ, выходящих из i-го события. Ранний срок (ожидаемый момент) осуществления j-го события представляет собой момент времени, раньше которого событие произойти не может и рассчитывается по формуле

Поздний срок (предельный момент) осуществления i-го события показывает максимальную задержку во времени наступления данного события:

6. Раскройте содержание, метод определения и значение критического пути в моделях сетевого планирования

Критический путь - последовательность работ между начальными и конечными событиями сети, имеющих наибольшую продолжительность во времени. Минимальное время, необходимое для выполнения проекта, запланированного сетевым графиком, равно длине критического пути. Сетевой график может содержать не один, а несколько критических путей. Критическими называются также работы и события, расположенные на этом пути. Резервный интервал от t до t* для событий, лежащих на критическом пути, равен 0. Для завершающего события сетевого графика поздний срок свершения события должен равняться его раннему сроку, т. е. t п = t* п. Длина критического пути равна раннему сроку свершения завершающего события, т. е. t кр = t п = t* п.

ЗАДАЧИ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

1. Какие системы исследуются при помощи теории массового обслуживания?

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

2. Привидите примеры систем массового обслуживан ия в экономике, на производстве

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

3. Как классифицируются системы массового обслуживания?

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

По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы:

1) с неограниченным временем ожидания (с ожиданием),

2) с отказами;

3) смешанного типа.

4. Какими чертами обладает простейший поток?

Простейший поток обладает такими важными свойствами:

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

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

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

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

вероятность того, что в обслуживающую систему за время t поступит именноk требований:

где. - среднее число требований, поступивших на обслуживание в единицу времени.

5. Какое распределение обычно имеет время обслуживания?

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

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

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

При показательном законе распределения времени обслуживания вероятность события, что время обслуживания продлиться не более чем t, равна:

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

где- среднее время обслуживания одного требования одним обслуживающим устройством.

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

где n - количество обслуживающих устройств.

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

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

МОДЕЛИ МЕЖОТРАСЛЕВОГО БАЛАНСА

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

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

2. Что показывает и отражают балансовые модели?

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

3. Дайте характерис тику разделов балансовой модели

В схеме МОБ по методологии СНС, как и в известной открытой статистической модели, выделяются три основные части (квадранты): внутренний (или первый) квадрант (I); боковое (или правое) крыло (II квадрант); нижнее крыло (III квадрант). IV квадрант не разрабатывается. Общая схема МОБ имеет следующий вид:

Внутренний (или первый) квадрант (I) характеризует взаимосвязи отраслей, отражает промежуточное потребление; во II квадранте приводится структура конечного использования валового внутреннего продукта (ВВП); в III квадранте показывается структура валовой добавленной стоимости по элементам. В I квадранте («шахматная таблица») по строкам и колонкам записываются отрасли экономики. В колонках I квадранта по каждой отрасли представлены затраты на производство продукции, работ, услуг (стоимость сырья, материалов, топлива, энергии, услуг), а по строкам показывается, как распределяется продукция каждой отрасли между всеми отраслями. В правой части МОБ (// квадрант) строки соответствуют отраслям-потребителям. Колонки представляют собой категории конечного использования: конечное потребление (расходы на конечное потребление домашних хозяйств, государственного управления и некоммерческих организаций, обслуживающих домашние хозяйства), валовое накопление (валовое накопление основного капитала, изменение запасов материальных оборотных средств, чистое приобретение ценностей), сальдо экспорта-импорта товаров и услуг. В III квадранте представлена стоимостная структура ВВП. Колонки III квадранта соответствуют отраслям-производителям, а строки -- основным стоимостным компонентам валовой добавленной стоимости (оплата труда наемных работников, валовая прибыль, валовой смешанный доход, налоги и субсидии, связанные с производством) и налогам и субсидиям на продукты. Таким образом, если рассматривать данные МОБ по вертикали, то по колонкам показывается стоимостная структура выпуска продукции отдельных отраслей, который состоит из промежуточного потребления (I квадрант) и валовой добавленной стоимости (III квадрант), а по горизонтали -- по строкам -- натурально-вещественный состав продукции, которая расходуется на промежуточное потребление (I квадрант) и конечное использование (II квадрант). Для каждой отрасли экономики ресурсы продуктов равны их использованию.Четвертый раздел располагается под вторым. Он характеризует перераспределительные отношения в экономике, осуществляемые через финансово-кредитную систему. В плановых расчетах четвертый раздел, как правило, не используется, и поэтому в пределах нашего курса рассматриваться не будет.

4 . Дайте характеристику методов формирования коэффициентов прямых затрат в балансовых моделях. Как вычисляются эти коэффициенты?

Логические коэффициенты, или, как их еще называют, коэффициенты прямых внутрипроизводственных затрат аij показывают, какое количество продукта i-й отрасли надо затратить на производство единицы валового продукта j-й отрасли. Коэффициенты прямых затрат считаются постоянными величинами в статических межотраслевых моделях.Каким образом можно получить значения коэффициентов аij? Есть два основных пути.

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

где Xij и Xj взяты из отчетного баланса.

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

Определив коэффициенты аij, можно использовать систему (4) для решения сформулированных выше задач 1 - 3.

Технологические коэффициенты аij обладают следующими свойствами:

ИГРОВЫЕ МОДЕЛИ В ЭКОНОМИКЕ

1. Какие причины вызывают неопределенность результатов игры?

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

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

2. Как определить нижнюю и верхнюю цену матричной игры и какое соотношение существует между ними?

Рассмотрим игру m Ч n с матрицей и определим наилучшую среди стратегий A 1 , A 2 , …, А m . Выбирая стратегию А i игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий B j , для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А).Обозначим через б наименьший выигрыш игрока А при выборе им стратегии А; для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы).Назовем б нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,

Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию B j , он учитывает максимально возможный при этом выигрыш для А. Назовем В верхней ценой игры, или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следовательно, .

Стратегия, соответствующая минимаксу, называется минимаксной стратегией. Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.Если верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены игры б = в = н называется чистой ценой игры, или ценой игры.

3. Сформулируйте основн ую теорему теории матричных игр

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

Или Для матричной игры с любой матрицей А величины и равны между собой, т.е.

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

4.Какие существуют методы упрощения игр?

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

Если i-я строка поэлементно не меньше (?) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B. Аналогично, если i-й столбец поэлементно не меньше (?) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (?), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности. На цене игры это никак не скажется. Зато размер матрицы игры понизится. С этого и нужно начинать решение игры. Частный случай доминирования является дублирование стратегий . Если платёжная матрица игры содержит несколько одинаковых строк (столбцов), то из них оставляем только одну строку, а остальные строки (столбцы) отбрасываем. Отброшенным стратегиям припишем нулевые вероятности.Упрощение (уменьшение размерности) платёжных матриц за счёт исключения заведомо невыгодных чистых стратегий возможно в силу справедливости следующей Теоремы о доминирующих стратегиях :

Пусть I - игра, в матрице которой i -я стратегия первого игрока доминирует над i +1, а G - игра, матрица которой получена из матрицы I исключением i + 1 стратегии (строки). Тогда:

1. цена игры I равна цене игры G;

2. оптимальная смешенная стратегия Q * = (q 1 * ,q 2 * ,…,q n *) второго игрока в игре G является также его оптимальной смешанной стратегией в игре I;

3. если P * = (p 1 * ,p 2 * ,…,p i * , p* i+2 ,…, p m *) оптимальная смешенная стратегия первого игрока в игре G, то его смешенная стратегия P * = (p 1 * ,p 2 * ,…,p i * , p* i+2 ,…, p m *) является оптимальной в игре I.

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

5. Геометрические методы решения игр с матрицами 2_ _n и m 2 и их применение

Решение игры в смешанных стратегиях допускает наглядную геометрическую интерпретацию. Геометрический метод решения игры включает следующие этапы. 1. В декартовой системе координат по оси абсцисс откладывается отрезок А1А2, длина которого равна 1 (рис. 2.1.). Левый конец отрезка точка x = 0 соответствует стратегии A1, правый, где х = 1,0 -- стратегии А2. Все промежуточные точки этого отрезка соответствуют смешанным стратегиям S1 = (p1, p2). 2. По оси ординат от точки O откладываются выигрыши при стратегии А1. 3. На линии, параллельной оси ординат, от точки 1 откладываются выигрыши при стратегии А2 .Пусть имеется игра с платежной матрицей:

Если игрок II применяет стратегию В1, то выигрыш игрока I при использовании чистых стратегий А1 и А2 составляет соответственно a11 = 0,4 и a21 = 0,6. Соединим эти точки прямой В1В1 . Если игрок I при стратегии В1 применяет смешанную стратегию, то средний выигрыш, определяемый по формуле математического ожидания g1 = a11p1 + a21p2, изображается ординатой точки N на прямой B1B1. Прямая B1B1 называется стратегией В1. Ордината любой точки отрезка B1B1 равна величине выигрыша игрока I при применении им стратегии A1 и А2 с соответствующими вероятностями p1 и p2.Аналогично строим отрезок В2В2, соответствующий применению игроком II стратегии В2 .Ординаты точек отрезка определяют средний стратегий А1 и А2 с соответствующими вероятностями p1 и p2 и равных g2 = a12p1 + a22p2.

6. На чем основана связь матричной игры и задачи линейного программирования?

Первоначально развитие теории стратегических матричных игр осуществлялось параллельно и независимо от линейного программирования. Позже было установлено, что стратегическая матричная игра может быть сведена к паре двойственных задач линейного программирования. Решив одну из них, получаем оптимальные стратегии игрока 1; решив другую, получаем оптимальные стратегии игрока 2. Математическое соответствие между стратегическими матричными играми и линейным программированием было установлено Дж. Б. Данцигом, сформулировавшим и доказавшим в 1951 г. основную теорему теории игр.

Теорема. Каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях, т.е. существуют такое число v и такие стратегии U* и W* игроков 1 и 2 соответственно, что выполняются неравенства:

Поясним смысл доказываемых неравенств: если игрок 1 отклоняется от своей оптимальной стратегии, то его выигрыш не увеличивается по сравнению с ценой игры; если от своей оптимальной стратегии отклоняется игрок 2, то по сравнению с ценой игры его проигрыш не уменьшается.

7. В чем состоит отличие игры с природой?

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

8. Перечислите основные критерии решения игр с природой и каковы расчетные формулы для этих критериев.

Критерий Байеса .

По критерию Байеса за оптимальные принимается та стратегия (чистая) A i , при которой максимизируется средний выигрыш a или минимизируется средний риск r.

Считаем значения?(a ij p j)

Критерий Лапласа .

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

q 1 = q 2 = ... = q n = 1/n.

Критерий Вальда .

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

a = max(min a ij)

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

Критерий Севиджа .

a = min(max r ij)

Критерий Сэвиджа ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.

Критерий Гурвица .

Критерий Гурвица является критерием пессимизма - оптимизма. За (оптимальную принимается та стратегия, для которой выполняется соотношение:

где s i = y min(a ij) + (1-y)max(a ij)

При y = 1 получим критерий Вальде, при y = 0 получим - оптимистический критерий (максимакс).

Критерий Гурвица учитывает возможность как наихудшего, так и наилучшего для человека поведения природы. Как выбирается y? Чем хуже последствия ошибочных решений, тем больше желание застраховаться от ошибок, тем y ближе к 1.

Критерий максимакса .

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

Практические задания

Задание № 1

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

Определим максимальное значение целевой функции F(X) = 2x 1 + 5x 2 + 6x 3 при следующих условиях-ограничений.

7x 1 + 8x 2 + 3x 3 ?81

4x 1 + x 2 + 6x 3 ?68

5x 1 + x 2 + 7x 3 ?54

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

В 1-м неравенстве смысла (?) вводим базисную переменную x 4 . В 2-м неравенстве смысла (?) вводим базисную переменную x 5 . В 3-м неравенстве смысла (?) вводим базисную переменную x 6 .

7x 1 + 8x 2 + 3x 3 + 1x 4 + 0x 5 + 0x 6 = 81

4x 1 + 1x 2 + 6x 3 + 0x 4 + 1x 5 + 0x 6 = 68

5x 1 + 1x 2 + 7x 3 + 0x 4 + 0x 5 + 1x 6 = 54

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

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

Решим систему уравнений относительно базисных переменных: x 4 , x 5 , x 6

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,81,68,54)

Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

...

Подобные документы

    Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.

    курсовая работа , добавлен 05.10.2014

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

    контрольная работа , добавлен 09.04.2012

    Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.

    контрольная работа , добавлен 04.05.2014

    Симплекс-метод решения задач линейного программирования. Элементы теории игр. Системы массового обслуживания. Транспортная задача. Графоаналитический метод решения задач линейного программирования. Определение оптимальной стратегии по критерию Вальде.

    контрольная работа , добавлен 24.08.2010

    История создания средств цифровой вычислительной техники. Методы и модели линейного программирования. Экономическая постановка задачи. Выбор метода реализации задачи. Особенности выбора языка программирования. Решение задачи сетевым методом планирования.

    курсовая работа , добавлен 19.02.2015

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

    учебное пособие , добавлен 15.06.2015

    Моделирование экономических систем: основные понятия и определения. Математические модели и методы их расчета. Некоторые сведения из математики. Примеры задач линейного программирования. Методы решения задач линейного программирования.

    лекция , добавлен 15.06.2004

    Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.

    контрольная работа , добавлен 11.05.2014

    Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.

    курсовая работа , добавлен 02.10.2014

    Основные понятия моделирования. Общие понятия и определение модели. Постановка задач оптимизации. Методы линейного программирования. Общая и типовая задача в линейном программировании. Симплекс-метод решения задач линейного программирования.

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «ФИНАНСОВЫЙ УНИВЕРСИТЕТ

ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ» Кафедра прикладной математики

В. И. Соловьев

ОПТИМАЛЬНЫХ РЕШЕНИЙ

Учебное пособие

Ре ком е н д о в а н о

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

для подготовки бакалавров экономики и менеджмента

Москва 2012

УДК 519.2 (075.8) ББК 22.1я73

Рецензенты:

канд. техн. наук, проф. В. Н. Калинина (Государственный университет управления)

канд. физ.-мат. наук, доц.В. М. Гончаренко (Финансовый университет)

С60 Соловьев В. И. Методы оптимальных решений: Учебное пособие. М.: Финансовый университет, 2012. 364 с.

ISBN 978-5-7942-ХХХХ-Х

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

Пособие предназначено для подготовки бакалавров по направлениям «Экономика» и «Менеджмент». Может быть полезно студентам, обучающимся по направлению подготовки бакалавров «Прикладная математика и информатика», магистрантам, аспирантам, преподавателям и научным работникам.

УДК 519.2 (075.8) ББК 22.1я73

О ГЛАВЛЕНИЕ

Предисловие....................................

Введение

........................................

Оптимальные решения в задачах планирования производства......

Производственная функция................................................................................

Модель поведения производителя.....................................................................

Модели налогообложения..................................................................................

Модель управления запасами.............................................................................

.......................................................................

Элементы линейной алгебры и балансовые модели экономики.....

Векторы и матрицы.............................................................................................

Линейные пространства......................................................................................

Системы линейных алгебраических уравнений...............................................

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

Обратная матрица................................................................................................

Обращенный базис системы линейных алгебраических уравнений.............

Модель межотраслевого баланса.......................................................................

Контрольные вопросы и задания .......................................................................

Методы линейного программирования............................................

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

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

Метод искусственного базиса............................................................................

Теория двойственности в линейном программировании................................

Двойственный симплексный метод.................................................................

Задачи целочисленного программирования...................................................

Решение задач линейного программирования в пакете Microsoft Excel ....

Контрольные вопросы и задания .....................................................................

Оптимальные решения в линейных задачах

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

Линейная задача планирования производства...............................................

Задача о расшивке узких мест производства..................................................

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

Контрольные вопросы и задания .....................................................................

Методы нелинейного программирования.......................................

Постановка задачи выпуклого программирования........................................

Условия Каруша - Куна - Таккера..............................................................

Метод возможных направлений......................................................................

Метод условного градиента.............................................................................

Метод штрафных функций...............................................................................

Решение задач нелинейного программирования в пакете Microsoft Excel...

Контрольные вопросы и задания .....................................................................

Оптимальные решения

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

Бюджетное множество и функции полезности..............................................

Предпочтения потребителя и функция полезности.......................................

Модель поведения потребителя.......................................................................

Уравнение Слуцкого.........................................................................................

Модель рыночного равновесия........................................................................

Контрольные вопросы и задания .....................................................................

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

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

Задача оптимального распределения инвестиций.........................................

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

Дискретные модели ценообразования опционов...........................................

Контрольные вопросы и задания .....................................................................

Теория графов и ее экономические приложения............................

Графы..................................................................................................................

Задачи о кратчайшем и критическом пути.....................................................

Потоки в сетях...................................................................................................

Контрольные вопросы и задания .....................................................................

Задачи многокритериальной оптимизации в экономике...............

Постановка задачи многокритериальной оптимизации...............................

Оптимальность по Парето................................................................................

Субоптимизация................................................................................................

Лексикографическая оптимизация..................................................................

Свертка критериев.............................................................................................

Метод идеальной точки....................................................................................

Метод последовательных уступок...................................................................

Контрольные вопросы и задания .....................................................................

ГЛАВА 10.Теория игр и ее экономические приложения..................................

§ 10.1. Матричные игры................................................................................................

§ 10.2. Принятие решений в условиях неопределенности........................................

§ 10.3. Биматричные игры............................................................................................

§ 10.4. Непрерывные игры............................................................................................

§ 10.5. Позиционные игры............................................................................................

Контрольные вопросы и задания .....................................................................

ГЛАВА 11.Моделирование поведения фирм на конкурентных рынках.........

§ 11.1. Модель поведения двух производителей на рынке одного товара.............

§ 11.2. Стратегии поведения дуополистов..................................................................

§ 11.3. Модели несовершенной и совершенной конкуренции..................................

§ 11.4. Модели конкуренции на рынке информационных технологий....................

Контрольные вопросы и задания .....................................................................

ГЛАВА 12.Теория оптимального управления

и ее экономические приложения.....................................................

§ 12.1. Постановка задачи оптимального управления...............................................

§ 12.2. Принцип максимума Понтрягина....................................................................

§ 12.3. Моделирование оптимального экономического роста..................................

§ 12.4. Моделирование динамики взаимодействия разработчиков

коммерческого и некоммерческого программного обеспечения.................

Контрольные вопросы и задания .....................................................................

П РЕДИСЛОВИЕ

Учебное пособие подготовлено в соответствии с действующими Федеральными государственными образовательными стандартами высшего профессионального образования по направлениям подготовки бакалавров «Экономика» (дисциплина «Методы оптимальных решений») и «Менеджмент» (дисциплина «Методы принятия управленческих решений»). Также во внимание принимался Федеральный государственный образовательный стандарт высшего профессионального образования по направлению подготовки бакалавров «Прикладная математика и информатика».

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

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

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

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

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

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

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

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

Во-вторых, систематизирована система обозначений. Так, все оптимизационные задачи формулируются в виде задач на максимум, а если в задаче присутствуют ограничения - неравенства, то они имеют вид « »; оптимальные решения всех задач обозначаются верхним индексом «* »; двойственные оценки в линейном программировании, множители Лагранжа в нелинейном программировании, сопряженные переменные в оптимальном управлении обозначаются одной и той же буквойy , чтобы подчеркнуть их общую природу. Точно так же управления в задачах динамического программирования и оптимального управления обозначаются одной и той же буквойu .

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

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

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

В-шестых, в данном пособии динамическое программирование рассматривается только в применении к дискретным процессам, а в качестве ме-

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

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

Книга достаточно насыщена материалом, и преподаватель может по своему усмотрению выбирать необходимое для изучения подмножество. Это же обстоятельство позволяет использовать пособие в качестве математической поддержки дисциплин по выбору для студентов, обучающихся по направлениям подготовки «Экономика», «Менеджмент», «Прикладная математика и информатика», «Прикладная информатика», «Бизнес-информа- тика» и др. Кроме того, автор надеется, что часть материала, связанная с моделированием конкуренции на рынках интеллектуальных товаров, будет полезна при написании выпускных квалификационных работ, в том числе магистерских и кандидатских диссертаций.

адресу [email protected].

В ВЕДЕНИЕ

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

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

производства.

П РИМЕР В.1. Предприятие производит продукцию двух видов (A и Б), используя при изготовлении этой продукции ресурсы трех видов (первого, второго и третьего). Чтобы произвести одну единицу продукции A, нужно затратить по 1 единице первого и второго ресурсов и 2 единицы третьего ресурса. Для производства единицы продукции Б требуется 2 единицы первого ресурса и 1 единица второго ресурса. Запасы ресурсов у предприятия ограничены: на складах есть 90 единиц первого ресурса, 50 единиц второго и 80 единиц третьего ресурса.

Рыночная цена продукции A составляет 800 руб. а цена продукции Б равна 1000 руб. Сколько продукции следует произвести, чтобы получить наибольшую выручку?

Решение. Пусть предприятие планирует произвестиx 1 единиц продукции A иx 2 единиц продукции Б, тогда выручка предприятия будет, очевидно, равна

z = 800x 1 +1000x 2 .

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

Вычислим суммарный расход первого ресурса. На производство единицы продукции A тратится 1 единица первого ресурса, а всего про-

дукции A производится x 1 единиц, значит, на производство всей продукции A будет затрачено1 x 1 = x 1 единиц первого ресурса. Аналогично, на производство единицы продукции Б тратится 3 единицы первого ресурса, а всего продукции Б производитсяx 2 единиц, значит, на производство всей продукции Б будет затрачено3 x 2 единиц первого ресурса. Суммарный расход первого ресурса на производство всей продукции (и A, и Б) соста-

вит x 1 + 3 x 2 единиц. А в запасе есть всего 90 единиц этого ресурса. Значит, должно выполняться ограничение:x 1 + 3 x 2 90 . Добавляя аналогичные ограничения по второму и третьему ресурсам, приходим окончательно к следующей задаче.

Требуется найти такой п л а н

п р о и з в о д с т в а (т. е. числаx 1

и x 2 ) , чтобы выполнение

плана обеспечивало предприятию

наибольшую в ы р у ч к у

z = 800x 1 + 1000x 2 ® max

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

р е с у р с а м

x + 3 x

x 1+ x 250,

и о г р а н и ч е н и я х н е о т р и ц а т е л ь н о с т и

x 10,

x 20 .

Построим область точек на плоскости, где все пять ограничений

выполняются. Уравнение x 1 + 3 x 2 = 90

определяет множество точек плос-

кости, лежащих на некоторой прямой. Чтобы эту прямую построить, достаточно вспомнить, что любая прямая полностью определяется любыми своими двумя различными точками. Подставим в данное уравнение x 1 = 0,

что 0 + 3 x 2 = 90 , откудаx 2 = 30. Итак, получили первую точку:

A (x 1 = 0,

x 2 = 30). Если подставить в данное уравнениеx 2 = 0, то получим:

x 1 + 3 × 0 = 90 или простоx 1 = 90. Получили вторую точкуB (x 1 = 90,

x 2 = 0).

Построим эту прямую: на рис. В.1, а она обозначена римской цифрой I.

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

из полуплоскостей выполняется неравенство x 1 + 3 x 2 < 90 , а в другой -

венство x 1 + 3 x 2 > 90 . Проверим, какое из этих двух неравенств выполняется в

полуплоскости, которая лежит ниже и левее только что построенной прямой. Подставим в неравенство x 1 + 3 x 2 < 90 координаты точкиO (x 1 = 0,x 2 = 0):

0 + 3× 0< 90 - значит, и для всех остальных точек, которые лежат ниже и левее прямойx 1 + 3 x 2 = 90 , выполняется неравенствоx 1 + 3 x 2 < 90 .

Таким образом, ограничение x 1 + 3 x 2 90 выполняется во всех точ-

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

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

(рис. В.1, б ).

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

Таким образом, любой план производства, соответствующий некоторой точке из заштрихованного пятиугольника, можно выполнить, такие планы называются допустимыми и мы замечаем, что, вообще говоря, их очень много. Как из них выбрать оптимальный, т. е. приносящий наибольшую выручку z = 800 x 1 + 1000 x 2 ?

Оказывается, что если оптимальный план существует, то он обязательно будет лежать в одной из угловых точек множества допустимых планов, т. е. в одной из вершин OABCD . Координаты точкиA мы знаем. Найдем координаты других вершин, например, точкиС .

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

x + x

2x 1

Из уравнения 2 x 1 = 80 получаемx 1 = 40. Подставимx 1 = 40 в урав-

x 1 + x 2 = 50 и получим, чтоx 2 = 10. Таким образом точкаС имеет

координаты

С (x 1 = 40,x 2 = 10). Аналогично получаем координаты всех

оставшихся вершин пятиугольника OABCD .

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

O (x 1

0, x 2 = 0), в этой точке выручкаz = 800 x 1 + 1000 x 2 = 800 × 0 +

1000× 0= 0 ;

A (x 1

0, x 2 = 30), z = 800x 1 + 1000x 2 = 800× 0+ 1000× 30= 30 000;

B (x 1

30, x 2 = 20), z = 800x 1 + 1000x 2 = 800× 30+ 1000× 20= 44 000;

∙ C (x 1 = 40, x 2 = 10), z = 800x 1 + 1000x 2 = 800× 40+ 1000× 10= 42 000;

∙ D (x 1 = 40, x 2 = 0), z = 800x 1 + 1000x 2 = 800× 40+ 1000× 0= 32 000.

Видим, что наибольшую выручку (44 000 руб.) обеспечит план B (x 1 = 30,x 2 = 20), по которому нужно произвести 30 единиц продукции A

и 20 единиц продукции Б.

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

Оптимальное (математическое) программирование - раздел прикладной математики, изучающий задачи условной оптимизации. В экономике такие задачи возникают при практической реализации принципа оптимальности в планировании и управлении. В оптимальное (математическое) программирование входят:

  • а) линейное программирование,
  • б) нелинейное программирование,
  • в) динамическое программирование,
  • г) дискретное (целочисленное) программирование,
  • д) дробно-линейное программирование,
  • е) параметрическое программирование,
  • ж) сепарабельное программирование,
  • з) стохастическое программирование,
  • и) геометрическое программирование.

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

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

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

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

Модель экономической задачи оптимизации состоит из 3-х частей:

I. Целевая функция (критерий оптимальности). Здесь описывается конечная цель, преследуемая при решении задачи. В качестве такой цели может быть или максимум получения каких-либо показателей или минимум затрат.

II. Система ограничений.

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

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

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

Однако, следует иметь в виду, что решение не всех оптимизационных проблем сводится к построению математических моделей и соответствующим вычислениям. Это связано с тем, что могут появиться обстоятельства, являющиеся существенными для решения проблемы, но, тем не менее, не поддающиеся математической формализации и, следовательно, не учитываемые в математической модели. Одним из таких обстоятельств является человеческий фактор. В этой связи можно вспомнить о так называемой «проблеме лифта». Служащие одной из фирм жаловались на слишком долгое ожидание лифта. Была попытка решить эту проблему математическими методами. Решение в силу ряда причин оказалось неприемлемым, а дальнейшие исследования показали, что время ожидания лифта невелико. Тогда возникла идея поставить на каждом этаже рядом со входом в лифт большие зеркала. Как только это было сделано, жалобы прекратились. Теперь люди рассматривали себя в зеркале и забывали о долгом ожидании лифта. Этот пример показывает необходимость правильно оценивать возможности математического описания исследуемых процессов и помнить, что в сфере организационного управления не все и не всегда поддается математической формализации и может быть адекватно отражено в математической модели.