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

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

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

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

Нижегородский государственный архитектурно-строительный университет

Кафедра: Прикладной информатики и статистики

Курсовая работа по «Исследованию операций»

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

Выполнила: Масленникова Ю.А.

Студентка 4 курса группы: ПИм17.15

Проверила: Прокопенко Н.Ю.

Доцент, кандидат физико-математических наук

Нижний Новгород

2018



Введение

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

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

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

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

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

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

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

Следовательно, передо мной ставятсятакие задачи как:

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

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



1. Основные направления совершенствования транспортных перевозок

1.1 Совершенствование организационных структур

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

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

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

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

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

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

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

Если маршруты созданы, определены и соблюдаются сроки поставки, то производственные запасы потребителей могут сокращаться в 1,5-2 раза, снижая тем самым затраты на складирование.

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

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

1.2 Совершенствование транспортной инфраструктуры (дороги и др.)

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

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

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

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

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

1.3 Рационализация маршрутов транспортных перевозок

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

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

Однако наибольшее распространение получило решение следующих основных задач:

* закрепление получателей груза за отправителями (потребителей за поставщиками) с целью сокращения транспортной работы в тонно-километрах;

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

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

* планирование оптимальных сборно-развозочных маршрутов на перевозках мелкопартионных грузов с целью сокращения общего пробега; 

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

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

1.4 Теория графов

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

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

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

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

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

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

* анализ объемов перевозок по дорогам республики, выстраивая по интенсивности движения, моделирование перевозок; 

* анализ географического расположения транспортных артерий - места пересечений, технические возможности, ограничения и интенсивность использования; 

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

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

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



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

2.1 Пример решения задачи о назначениях

Задача о назначениях является частным случаем транспортной задачи, в которой исполнители тождественны пунктам отправления, а работы -- пунктам назначения. При этом все величины спроса и предложения равны 1, а стоимость «транспортировки» исполнителя i на работу j соответствует cij. Указанные условия позволяют решать задачу о назначениях теми же методами, что и транспортную.

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

Шаг 1. В исходной матрице стоимостей определим в каждой строке минимальную стоимость и отнимем ее от других элементов строки. 

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

Шаг 3. За оптимальные назначения примем те, которым соответствуют нулевые элементы, полученные на предыдущем шаге. Если допустимое решение не получено, выполняются последующие шаги. 

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

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

Шаг 6. Возвращение к шагу 3. 

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

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

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

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

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

Таблица 2
	Исполнители работы
	1	2	3	4
1	0	5	4	4
2	3	0	0	2
3	0	0	3	1
4	7	3	0	0

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

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

Вначале и при последующих возвращениях к первому шагу алгоритма множество А пусто, а множество A' содержит все столбцы. Далее реализуются следующие шаги решения (рис. 2)

Рис. 2. Блок-схема алгоритма решения задачи о назначениях

Пример задачи о выборе работников

В конкурсе на занятие пяти вакансий транспортных работников (V1, V2, V3, V4, V5) участвуют семь претендентов (P1, P2, P3, P4, P5, P6, P7). Результаты тестирования каждого претендента, на соответствующие вакансии, даны в виде матрицы - С (тестирование производилось по десятибалльной системе).

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

		V1	V2	V3	V4	V5
	P1	7	5	7	6	7
	P2	6	4	8	4	9
С=	P3	8	6	4	3	8
	P4	7	7	8	5	7
	P5	5	9	7	9	5
	P6	6	8	6	4	7
	P7	7	7	8	6	4

2.2. Решение задачи о назначениях при помощи преобразования матрицы (С)

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

Задача нахождения минимального значения функции Z эквивалентна задаче нахождения минимума для функции , матрица (-С) имеет вид:

-

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

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

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

	`1	4	1	3	2	0	0
	2	5	0	5	0	0	0
C1=	0	3	4	6	1	0	0
	1	2	0	4	2	0	0
	3	0	1	0	4	0	0
	1	1	2	5	2	0	0
	2	2	0	3	5	0	0

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

a) минимальным количеством горизонтальных и вертикальных прямых вычеркиваем все нули.

b) среди не вычеркнутых элементов находим минимальный элемент;

c) вычитаем минимальный элемент из всех вычеркнутых элементов;

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

Среди множества получаемых нулевых элементов определяем допустимое решение. Если допустимое решение найти нельзя, повторяем шаги a, b, c, d снова.

Процедура вычеркивания элементов и ее результат показаны на рис.1. Минимальный среди не вычеркнутых элементов равен единице. На рис.2 показан результат после вычитания единицы из не вычеркнутых элементов и прибавления единицы к элементам, стоящим на пересечении прямых. Допустимое решение соответствует отмеченным элементам.



1	4	1	3	2	0	0
2	5	0	5	0	0	0
0	3	4	6	1	0	0
1	2	0	4	2	0	0
3	0	1	0	4	0	0
1	1	2	5	2	0	0
2	2	0	3	5	0	0

Рис.1

1	3	1	2	1	0	0
3	5	1	5	0	1	1
0	2	4	5	0	0
1	1	0	3	1	0	0
4	0	2	0	4	1	1
1	0	2	4	1	0	0
2	1	0	2	4	0	0

Рис.2

Перенеся полученное решение на исходную матрицу (С): 

7	5	7	6	7	0	0
6	4	8	4	9	0	0
8	6	4	3	8	0	0
7	7	8	5	7	0	0
5	9	7	9	5	0	0
6	8	6	4	7	0	0
7	7	8	6	4	0	0

Получим, что претенденты Р1 и Р7 попадают на фиктивные вакансии и не принимаются на работу. Р2 принимается на пятую вакансию, Р3 - на первую, Р4 - на третью, Р5 - на четвертую, Р6 - на вторую. Сумма баллов, полученная при данном решении равна: 9+8+8+9+8=42.



Методы решения задач исследования операций (решение задач).

Вариант-3

Задание 1. Определение оптимального плана выпуска продукции и анализ оптимального решения с использованием двойственных оценок.

Пусть в производстве 4-х видов продукции участвуют 4 вида ресурсов. Известны нормы расхода ресурсов на производство единицы продукции (матрица А), цены ее реализации (матрица С) и запасы ресурсов (матрица В).

, 30, =90, 120

Рeшение:

1. Cимплекс-метод (системами линейных уравнений).

2.

F(x)=3x1+3x2+4x3+5x4>max

x1(0;0;0;0;550;350;650;520)- допустимое базисное решение

F(x)=0

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

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

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

Основные	Неосновные
y1,y2,y3,y4	x1,x2,x3,x4
Основные	Неосновные
х4,у1,у2,у4	х1,х2,х3,у3

y3 = 650 5x22x36x4

6x4 = 650 5x22x3 y3¦: 6

x2(0;0;0;108,33;333,3;241,67;0;303,3)- допустимое базисное решение

F(x) = 3x1+3x2+4x3+5) =541,65+3х1

Критерий не выполнен, так как

коэффициенты3 и больше нуля.

Основные	Неосновные
х4,у1,у2,у4	х1,х2,х3,у3
Основные	Неосновные
х1,х4,у1,у2	х2,х3,у3,у4

4х1 =

x3(75,83;0;0;108,33;30;14,17;0;0)- допустимое базисное решение

F(x) = 541,65+3 = 769,14

Критерий не выполнен, так как коэффициентбольше нуля.

Основные	Неосновные
х1,х4,у1,у2	х2,х3,у3,у4
Основные	Неосновные
х1,х4,x3,у2	х2,y1,у3,у4

= 30 ? x2 ? 2x3 + y4

x3(67,08;0;15;103,33;0;0,42;0;0)- допустимое базисное решение

F(x) = 769,14 = 777,89

Критерий выполнен, т.е. все коэффициенты меньше нуля.

Базисное решение найдено.

Ответ:x*(67,08;0;15;103,33;0;0,42;0;0);Fmax = 769,14.

2.2 Симплекс-метод в табличной форме.

F(x)=3x1+3x2+4x3+5x4>max

№1	х1	х2	х3	х4	b	Qx4
у1	4	2	5	2	550	275
у2	3	0	3	1	350	350
у3	0	5	2	6	650	108,33
у4	4	1	3	2	520	260
F	-3	-3	-4	-5	0

x1(0;0;0;0;550;350;650;520)- допустимое базисное решение

F(x)=0

№2	х1	х2	х3	y3	b	Qx1
у1	4	2/6	26/6	- 2/6	333,3	83,33
у2	3	- 5/6	16/6	- 1/6	241,7	80,56
x4	0	5/6	2/6	1/6	108,3	?
у4	4	- 4/6	14/6	- 2/6	303,3	75,83
F	-3	7/6	-14/6	5/6	541,7

x2(0;0;0;108,3;333,3;241,7;0;303,3)- допустимое базисное решение

F(x) = 541,7

№3	у4	х2	х3	y3	b	Qx3
у1	-1	1	2	0	30	15
у2	- 3/4	- 2/6	11/12	1/12	14,17	15,5
x4	0	5/6	2/6	1/6	108,3	325
х1	1/4	- 1/6	7/12	-1/12	75,83	130
F	3/4	4/6	- 7/12	7/12	769,17



x3(75,83;0;0;108,33;30;14,17;0;0)- допустимое базисное решение

F(x) = 769,14

№4	у4	х2	y1	y3	b
x3	- 1/2	1/2	1/2	0	15
у2	- 7/24	- 19/24	- 11/24	1/12	0,42
x4	2/12	8/12	- 2/12	1/6	103,33
х1	13/24	- 11/24	- 7/24	-1/12	67,08
F	11/24	23/24	7/24	7/12	777,92

x3 (67,08;0;15;103,33;0;0,42;0;0) - допустимое базисное решение

F(x) = 777,92

Базисное решение найдено.

Ответ:x*(67,08;0;15;103,33;0;0,42;0;0);Fmax = 777,92.



3. Определить план производства продукции в Excel, максимизирующий выручку от реализации продукции

Составим исходную таблицу с известными нам данными.

х - продукция, которую мы производим;

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

запасы - сколько ресурсов у нас на складе;

израсходовано - сколько ресурсов было израсходовано при производстве, в Excel по формуле:

=СУММПРОИЗВ(B3:E3;$B$9:$E$9)

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

целевая функция - максимизированная выручка.

Целевая функция находятся в Excel по формуле:

=СУММПРОИЗВ(B9:E9;B10:E10)

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

В результате:

4. Используя Отчеты в «Поиске Решения», нужно ответить на следующие вопросы:

Отчеты

Отчет об результатах:

Отчет о устойчивости:

Отчет о переделах

1) Ценность каждого ресурса и его приоритет при решении задачи увеличения запаса ресурсов.

По отчету о результатах ресурсы такие как у1, у3, у4 с привязкой, то это говорит о том, что эти ресурсы были полностью использованы, т.е. являются дефицитными. А ресурс у2 - без привязки, т.е. недефицитный.

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

Таким образом, при решении задачи об увеличении запасов ресурсов в первую очередь надо увеличивать запасы ресурса у3, во вторую очередь у4, в третью очередь - у1. Запас ресурса у2 увеличивать не стоит, так как он является недефицитным.

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

При рассмотрении отчета об устойчивости мы можем сказать, что:

Максимальный интервал изменения запасов для ресурса у1: (520;550,9)

Максимальный интервал изменения запасов для ресурса у2: (349,58;?)

Максимальный интервал изменения запасов для ресурса у3: (645;1455)

Максимальный интервал изменения запасов для ресурса у4: (396,15;521,43)

3) На сколько можно снизить запас каждого из ресурсов, чтобы это не привело к уменьшению прибыли?

Запасы у1, у3 и у4 снизить нельзя, они используются в плане полностью. Запас у2 ресурса можно уменьшить на 0,42 у.е. При этом план и прибыль останутся прежними (не уменьшатся).

4) На сколько нужно изменить затраты каждого вида сырья на единицу продукции, чтобы сделать производство нерентабельного изделия рентабельным?

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

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

Интервал изменения цен для продукции х2: (0;3,96)

Изменим цену с 3 у.е. на 3,96 у.е.

Получаем результат:

Продукция х2 стала рентабельной, при этом прибыль увеличилась на 0,05 .

5) Выпуск какой продукции нерентабелен?

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

6) На сколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?

При выпуске единицы нерентабельной продукции х2 максимальный доход уменьшится на 0,96 у.е. и составит 776,96 у.е.

7) Интервалы изменения цен на каждый вид продукции, при которых сохраняется структура оптимального плана.

Интервал изменения цен для продукции х1: (2,15;4)

Интервал изменения цен для продукции х2: (0;3,96)

Интервал изменения цен для продукции х3: (3,42;4,92)

Интервал изменения цен для продукции х4: (3,56;6,75)

8) Как изменится общая стоимость продукции и план ее выпуска при увеличении запасов сырья I и II видов на и ед. соответственно и уменьшении на ед. сырья III вида?

Общая стоимость продукции снизиться на 61,25 у.е. и будет равна 716,67 у.е. План выпуска продукции тоже потерпит изменения:

Продукция х1увеличится на 1,25 у.е. и будет равна 68,33 у.е.

Продукция х2 не изменится, т. е. также останется нерентабельной.

Продукция х3 увеличится на 15 у.е. и будет равна 30у.е.

Продукция х4 уменьшится на 25 у.е. и будет равна 78,33 у.е.

9) Оценить целесообразность введения в план еще одного изделия, ценой 10 ед., на изготовление которого расходуется по 2 ед. каждого вида сырья?

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



?j=?aijyi - cj

если ?j ? 0 - выгодно

если ?j>0 - невыгодно.

?j- затраты

aij- затраты на изготовление

yi- теневая цена

cj- стоимость х5

?х5=2*0,29+2*0+2*0,58+2*0,46-10=2,66-10=-7,34<0

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

Проиллюстрируем на практике в Excel:

Исходя из результата нового поиска решений, можно сделать выводы о том, что прибыль увеличилась на 1152,08 у.е. и стала составлять 1930 у.е., следовательно, делаем вывод, что производство продукции х5 выгодно.

Задание 2. Решить транспортную задачу

Дано:

Решение:

Шаг:1

Проверка на сбалансированность

Общее число запасов на складах :950;

Общая потребность :950

Задача является сбалансированной (закрытой).

Шаг:2

Отыскание начального решения.

а) Метод минимальной стоимости

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4	5	7	4 70	3 200
а2	230	9	8 30	10 200	6	4
а3	250	3 170	4 80	5	7	7
а4	200	8	7 100	8	5 100	4

8=8

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

Pнач=4*70+3*200+8*30+10*200+3*170+4*80+7*100+5*100



Pнач=	5150

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

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 170	5 100	7	4	3 0
а2	230	9	8 110	10 120	6	4
а3	250	3	4	5 80	7 170	7
а4	200	8	7	8	5	4 200

8=8

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

Pнач= 4*170+5*100+8*110+10*120+5*80+7*170+4*200+3*0

Pнач=	5650

Шаг:3

Оптимизация

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

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

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

а) Метод минимальной стоимости

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 +	5	7	4 - 70	3 200
а2	230	9	8 30	10 200	6	4
а3	250	3 - 170	4 + 80	5	7	7
а4	200	8	7 - 100	8	5 + 100	4

V4+U1+4 = 0 V4 = -4

V5+U1+3 = 0 V5 = -3

V4+U4+5= 0U4 = -1

V2+U4+7 = 0V2 = -6

V2+U3+4 = 0 U3 = 2

V2+U2+8 = 0 U2 = -2

V3+U2+10= 0 V3 = -8

V1+U3+3 = 0 V1 = -5

Матрица оценки

-1 -1 -1 0 0

2 0 00 -1

0 0 -1 5 6

2 0 -1 0 0

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

Отметим в транспортной таблице ячейку а1,b1 знаком + . Строим цикл, где поочередно будут меняться знаки + и -.

Затем мы определим минимум из всех элементов, помеченных знаком -, т.е. min 70;100;170 = 70

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 + 70	5	7	4	3 - 200
а2	230	9	8 - 30	10 200	6	4 +
а3	250	3 - 100	4 + 150	5	7	7
а4	200	8	7 30	8	5 170	4

V5+U1+3 = 0 V5 = -3

V1+U1+4 = 0 V1 = -4

V1+U3+3= 0 U3 = 1

V2+U3+4 = 0 V2 = -5

V2+U4+7 = 0 U4 = -2

V2+U2+8 = 0 U2 = -3

V3+U2+10= 0 V3 = -7

V4+U4+5 = 0 V4 = -3

Матрица оценки

0 0 00 0

2 0 00 -2

0 0 -1 5 5

2 0 -1 0 -1

min 30;100;200 = 30

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 + 100	5	7	4	3- 170
а2	230	9	8	10 - 200	6	4+ 30
а3	250	3- 70	4 180	5+	7	7
а4	200	8	7 30	8	5 170	4

V5+U1+3 = 0 V5 = -3

V1+U1+4 = 0 V1 = -4

V5+U2+4= 0 U2 = -1

V3+U2+10 = 0 V3 = -9

V1+U3+3 = 0 U3 = 1

V2+U3+4 = 0 V2 = -5

V2+U4+7= 0 U4 = -2

V4+U4+5 = 0 V4 = -3

Матрица оценки

0 0 -21 0

4 202 0

0 0-3 5 5

2 0 -3 0 -1

min 70;170;200 = 70



		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 170	5 +	7	4	3- 100
а2	230	9	8	10- 130	6	4+ 100
а3	250	3	4- 180	5+ 70	7	7
а4	200	8	7 30	8	5 170	4

V5+U1+3 = 0 V5 = -3

V1+U1+4 = 0 V1 = -4

V5+U2+4= 0 U2 = -1

V3+U2+10 = 0 V3 = -9

V3+U3+5 = 0 U3 = 4

V2+U3+4 = 0 V2 = -8

V2+U4+7= 0 U4 = 1

V4+U4+5 = 0 V4 = -6

Матрица оценки

0-3 -2-2 0

4 -10-1 0

3 00 5 8

5 0 0 0 2

min 100;130;180= 100



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

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

	b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 170	5 100	7	4	3
а2	230	9	8+	10 - 30	6	4 200
а3	250	3	4- 80	5 + 170	7	7
а4	200	8	7 30	8	5 170	4

V1+U1+4 = 0 V1 = -4

V2+U1+5= 0 V2 = -5

V2+U3+4= 0 U3 = 1

V2+U4+7 = 0 U4 = -2

V3+U3+5 = 0 V3 = -6

V3+U2+10 = 0 U2 = -4

V5+U2+4= 0 V5 = 0

V4+U4+5 = 0 V4 = -3

Матрица оценки

00 11 3

1-10 -1 0

0 0 0 5 8

2 0 0 0 2



min 30;80 = 30Размещено на http://www.allbest.ru//

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

	b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 170	5 100	7	4	3
а2	230	9	8 30	10	6	4 200
а3	250	3	4 50	5 200	7	7
а4	200	8	7 30	8	5 170	4

V1+U1+4 = 0 V1 = -4

V2+U1+5= 0 V2 = -5

V2+U2+8= 0 U2 = -3

V2+U3+4 = 0 U3 = 1

V2+U4+7 = 0 U4 = -2

V3+U3+5 = 0 V3 = -6

V5+U2+4= 0 V5 = -1

V4+U4+5 = 0 V4 = -3

Матрица оценки

0 0 11 2

201 0 0

0 0 0 5 7

2 0 0 0 1



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

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 170	5 100	7	4	3
а2	230	9	8 30	10	6	4 200
а3	250	3	4 50	5 200	7	7
а4	200	8	7 30	8	5 170	4

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

Pопт= 4*170+5*100+8*30+4*50+7*30+5*200+5*170+4*200

Pопт=	4480

Граф имеет вид:

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

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 170	5 100	7	4	3 0
а2	230	9	8 110	10 - 120	6 +	4
а3	250	3	4	5+ 80	7 - 170	7
а4	200	8	7	8	5	4 200

V1+U1+4 = 0 V1 = -4

V2+U1+5 = 0 V2 = -5

V2+U2+8= 0 U2 = -3

V3+U2+10= 0 V3 = -7

V3+U3+5 = 0 U3 = 2

V4+U3+7 = 0 V4 = -9

V5+U4+4= 0 U4 = -1

V5+U1+3 = 0 V5 = -3

Матрица оценки

0 0 0 -5 0

2 0 0 -6 -2

1 1 0 0 6

3 1 0 -5 0

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

Отметим в транспортной таблице ячейку а2,b4 знаком + . Строим цикл, где поочередно будут меняться знаки + и -.Затем мы определим минимум из всех элементов, помеченных знаком -, т.е.min 120;170 = 120

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 - 170	5 + 100	7	4	3 0
а2	230	9	8 - 110	10	6+ 120	4
а3	250	3 +	4	5 200	7- 50	7
а4	200	8	7	8	5	4 200

V1+U1+4 = 0 V1 = -4

V2+U1+5 = 0 V2 = -5

V2+U2+8= 0 U2 = -3

V4+U2+6 = 0V4 = -3

V4+U3+7 = 0U3 = -4

V3+U3+5 = 0 V3 = -1

V5+U4+4= 0 U4 = -1

V5+U1+3 = 0 V5 = -3

Матрица оценки

0 0 6 1 0

2 0 60 -2

-5-5 0 0 0

3 1 6 1 0

min 170;110;50 = 50

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 120	5 150	7 +	4	3 - 0
а2	230	9	8 60	10-	6 170	4 +
а3	250	3 50	4	5 200	7	7
а4	200	8	7	8	5	4 200

V1+U1+4 = 0 V1 = -4

V2+U1+5 = 0 V2 = -5

V2+U2+8= 0 U2 = -3

V4+U2+6 = 0 V4 = -3

V1+U3+3 = 0 U3 = 1

V3+U3+5 = 0 V3 = -6

V5+U4+4= 0 U4 = -1

V5+U1+3 = 0 V5 = -3

Матрица оценки

0 0 1 1 0

2 0 1 0 -2

0 0 0 5 5

3 1 1 1 0

min=0

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 120	5 150	7	4	3
а2	230	9	8 - 60	10	6 170	4 + 0
а3	250	3 50	4	5 200	7	7
а4	200	8	7 +	8	5	4 - 200

V1+U1+4 = 0 V1 = -4

V2+U1+5 = 0 V2 = -5

V2+U2+8= 0 U2 = -3

V4+U2+6 = 0 V4 = -3

V1+U3+3 = 0 U3 = 1

V3+U3+5 = 0 V3 = -6

V5+U4+4= 0 U4 = -3

V5+U2+4 = 0 V5 = -1

Матрица оценки

0 0 1 1 2

2 0 100

0 0 057

1-1-1 -10

min 200;60 = 60

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 120	5 150	7	4	3
а2	230	9	8	10	6- 170	4 + 60
а3	250	3 50	4	5 200	7	7
а4	200	8	7 60	8	5 +	4 - 140

V1+U1+4 = 0 V1 = -4

V2+U1+5 = 0 V2 = -5

V2+U4+7 = 0 U4 = -2

V1+U3+3 = 0 U3 = 1

V3+U3+5 = 0 V3 = -6

V4+U2+6 = 0 V4 = -4

V5+U4+4= 0 V5 = -2

V5+U2+4 = 0 U2 = -2

Матрица оценки

0 0 1 0 1

3 1 2 0 0

0 0 0 46

200-1 0

min 170;140 = 140

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 120	5 150	7	4	3
а2	230	9	8	10	6 30	4 200
а3	250	3 50	4	5 200	7	7
а4	200	8	7 60	8	5 140	4

V1+U1+4 = 0 V1 = -4

V2+U1+5 = 0 V2 = -5

V2+U4+7 = 0 U4 = -2

V1+U3+3 = 0 U3 = 1

V3+U3+5 = 0 V3 = -6

V4+U4+5 = 0 V4 = -3

V4+U2+6= 0 U2 = -3

V5+U2+4= 0 V5 = -1

Матрица оценки

0 0 1 1 2

2 0 1 0 0

0 0 0 57

200 0 1

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

		b1	b2	b3	b4	b5
		170	210	200	170	200
а1	270	4 120	5 150	7	4	3
а2	230	9	8	10	6 30	4 200
а3	250	3 50	4	5 200	7	7
а4	200	8	7 60	8	5 140	4

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

Pопт= 4*120+5*150+6*30+4*200+3*50+5*200+7*60+5*140

Pопт=	4480

Граф имеет вид:

Задание 3 по теме «Теория игр»

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

План продажи	Величина дохода, ден. ед.
	К1	К2	К3
П1	a11	a12	a13
П2	a21	a22	a23
П3	a31	a32	a33

Определить оптимальный план продажи товаров.

Решение:

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

План продажи	Величина дохода, ден. ед.
	К1	К2	К3
П1	3	5	1
П2	4	2	3
П3	4	5	4

Мы имеем две стратегии План продаж, обозначим его как П, а также Величину продаж, обозначим ее как К.

SП (П1, П2, П3) и SК (К1, К2, К3)

Определим нижнюю цену игры - б

б = maxmin(aij) = 4, т.е. для того чтобы гарантировать себе максимальный план продажи не хуже, чем 4 мы должны придерживаться стратегии A3.

Определим верхнюю цену игры - в

в = minmax(aij) = 4, т.е. для того чтобы гарантировать себе величину продаж не хуже, чем 4 мы должны придерживаться одной из стратегий B1, B3

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

В данной игреприсутствуют 2 седловые точки, которые определяют соответственно 2 решения (пар оптимальных стратегий). Причем все эти решения приводят нас к одной цене игры (v = 4).

Ответ:

Нижняя цена игры, верхняя цена игры и чистая цена игры: б = в = v = 4;

Оптимальные стратегии (2 пары): A3B1; A3B3.



Заключение

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

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

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



Список использованной литературы

перевозка обслуживание матрица

Анисимова, Н. П., Ванина, Е. А. Линейное программирование [Текст]: учеб.-метод. пособие / Н. П. Анисимова, Е. А. Ванина ; Санкт-Петербургский филиал Нац. исслед. ун-та «Высшая школа экономики». -- СПб.: НИУ ВШЭ -- Санкт-Петербург, 2012. -- 70 с.

Исследование операций в экономике: Учеб. пособие для вузов/Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2005. - 407 с.

Невежин В. П., Кружилов С. И., Невежин Ю. В. Исследование операций и принятие решений в экономике; Форум - Москва, 2012. - 400 c.

Размещено на Allbest.ru