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

Научно-образовательный портал ТУСУР | Методы оптимальных решений. Часть 1. Линейное программирование: Курс лекций / Гендрина И. Ю. — 2018. 36 с.

1. Элементы линейной алгебры 3

1.1 Системы линейных уравнений 3

1.2 Метод Гаусса 5

1.3 Решение линейных неравенств 7

1.4 Решение систем линейных неравенств 8

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

2.1 Примеры задач, сводящихся к ЗЛП. Общая постановка ЗЛП 9

2.2 Графический метод решения ЗЛП 11

2.3 Свойства решений ЗЛП 13

2.4 Симплекс-метод решения ЗЛП 14

2.5 Симплекс-таблицы 14

2.6 Двойственные ЗЛП 15

2.7 Экономическая интерпретация взаимно-двойственных задач 17

2.8 Анализ устойчивости двойственных оценок 20

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

3.1 Постановка транспортной задачи 24

3.2 Способы построения первого опорного плана ТЗ 25

3.3 Метод потенциалов 27

3.4 Открытые транспортные задачи 28

4. Задачи для самостоятельного решения 30

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

4.2 Транспортные задачи 33

5. Литература 36

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

Понятие экономико-математической модели. Примеры.

Понятие статической задачи оптимизации.

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

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

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

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

Алгоритм симплексного метода.

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

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

Составление математических моделей двойственных задач.

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

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

Экономико-математическая модель транспортной задачи.

Нахождение опорного решения транспортной задачи: метод «северо-западного» угла.

Проверка опорного решения на оптимальность методом потенциалов.

Алгоритм решения транспортной задачи.

Транспортная задача с ограничениями на пропускную способность.

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

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

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

Метод ветвей и границ.

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

Основные понятия теории игр. Равновесная ситуация: нижняя и верхняя цена игры, седловая точка.

Игра в смешанных стратегиях. Аналитическое решение игры .

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

Графическое решение игры вида .

Графическое решение игры вида .

Постановка задачи игры «с природой».

Критерии принятия решения в играх «с природой».

Понятие позиционной игры.

Нормализация позиционной игры.

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

Способы задания графов .Задание графов с помощью матриц смежности и инциденций.

Упорядочивание дуг и вершин орграфа.

Алгоритм Дейкстры нахождения минимального пути.

Алгоритм Беллмана-Мура нахождения минимального пути.

Алгоритм нахождения максимального пути на графе.

Основные понятия элементов сетевого планирования. Работа, событие, критический срок, критические и некритические работы.

Использование линейных графиков в сетевом планировании. Вычисление резервов времени работ с помощью линейного графика.

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

Киселева Э.В., Соловьева С.И. Математическое программирование (линейное программирование): Учебное пособие. – Новосибирск: НГАСУ, 2002. – 146 с. [Электронный ресурс]. – Режим доступа:

http://window.edu.ru/resource/315/63315 (дата обращения 15.04.2013)

Лутманов С.В. Линейные задачи оптимизации: Учебное пособие. Ч.1. Линейное программирование. – Пермь: Перм. гос. ун-т, 2004. – 128 с. [Электронный ресурс]. – Режим доступа: http://window.edu.ru/resource/587/50587 (дата обращения 15.04.2013)

Лутманов С.В. Линейные задачи оптимизации: Учебное пособие. Ч.2. Оптимальное управление линейными динамическими объектами. – Пермь: Перм. гос. ун-т, 2005. – 195 с. [Электронный ресурс]. – Режим доступа:

http://window.edu.ru/resource/588/50588 (дата обращения 15.04.2013)

Рейзлин В.И. Численные методы оптимизации: учебное пособие / В.И. Рейзлин; Томский политехнический университет. – Томск: Изд-во ТПУ, 2011. – 105 с. [Электронный ресурс]. – Режим доступа: http://window.edu.ru/resource/650/75650 (дата обращения 15.04.2013)

Ромашова О.Ю. Методы оптимизации и расчеты на ЭВМ технико-экономических задач: учебное пособие. – Томск: Изд-во ТПУ, 2009. – 210 с. [Электронный ресурс]. – Режим доступа: http://window.edu.ru/resource/676/75676 (дата обращения 15.04.2013)

Методы оптимальных решений — презентация на Slide-Share.ru 🎓

1

Первый слайд презентации: Методы оптимальных решений

Основные темы дисциплины Оптимизация – постановка задачи Линейное программирование и задача оптимизации. Методы решения Двойственные задачи. Применение в экономических приложениях Транспортная задача

Изображение слайда

2

Слайд 2: Оптимизация. Постановка задачи

Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения – системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны. Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента с целью оптимизации организации производства и производственных процессов, например, процессов загрузки станков и раскройки листов материалов. После второй мировой войны аналогичными задачами занялись в США. В 1975 г. Т. Купманс (1910-1985, родился в Нидерландах, работал в основном в США) и академик АН СССР Л.В. Канторович были награждены Нобелевскими премиями по экономике.

Изображение слайда

3

Слайд 3: Линейное программирование

Наиболее часто используются оптимизационные модели принятия решений. Их общий вид таков: F ( X ) → max X Є A Здесь F – целевая функция; Х – управляющий параметр, который может иметь различную природу – число, вектор, множество и т.п. Цель менеджера – максимизировать целевую функцию  F ( X ), выбрав соответствующий Х, соответствующий множеству определения А, X Є A. Линейное программирование является одним из наиболее широко применяемых методов оптимизации.

Изображение слайда

4

Слайд 4: Линейное программирование – постановка задачи

Пример 1. Производственная задача. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола – 20 единиц. Стул требует 10 человеко- часов, стол – 15. Имеется 400 единиц материала и 450 человеко- часов. Прибыль при производстве стула – 45 денежных единиц, при производстве стола – 80 ден. ед. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль? Обозначим: Х 1 – число изготовленных стульев, Х 2 – число сделанных столов. Задача оптимизации (целевая функция) имеет вид: F(x 1,x 2 ) = 45 Х 1 + 80 Х 2  → max, Ограничения задачи, т.е. допустимое множество Х 5 Х 1 + 20 Х 2  ≤ 400 10 Х 1 + 15 Х 2  ≤ 450 Х 1   ≥ 0 Х 2  ≥ 0

Изображение слайда

5

Слайд 5: Графическое представление задачи линейного программирования

Условия производственной задачи можно изобразить на координатной плоскости, откладывая по оси абсцисс значения Х 1, а по вертикальной оси ординат – значения Х 2. Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения ( Х 1, Х 2 ) объемов выпуска в виде треугольника (рис.1). Рис. 1. Ограничения по материалу

Изображение слайда

6

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

ограничения по материалу изображаются в виде выпуклого Многоугольника ( треугольника). Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей ограничениям 5 Х 1 + 20 Х 2  ≤ 400 и Х 1   ≥ 0, Х 2  ≥ 0. При построении эти неравенства заменяются на равенства. Прямая пересекает ось Х 1, соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х 2, соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство, а это означает, что материал останется.

Изображение слайда

7

Слайд 7: Линейное программирование. Продолжение примера

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

Изображение слайда

8

Слайд 8: Линейное программирование. Продолжение примера

Из анализа результатов рис.1 и рис.2 мы видим, что очевидного решения нет – для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении? Чтобы ответить на этот вопрос, надо “совместить” рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).

Изображение слайда

9

Слайд 9: Линейное программирование. Продолжение примера

Изображение слайда

10

Слайд 10: Линейное программирование. Продолжение примера

Объединение ограничений рис. 1 и рис. 2 приводит к образованию совместной системы ограничений и формированию области допустимых решений. Графически эта область представляет выпуклый многоугольник рис.3. с соответствующими координатами вершин

Изображение слайда

11

Слайд 11: Линейное программирование. Продолжение примера

Максимальное (или минимальное ) значение целевой функции для данной простой задачи можно найти методом простого перебора, вычислив значение целевой функции F(x 1,x 2 ) = 45 Х 1 + 80 Х 2  в узлах выпуклого многоугольника. Решение задачи: максимум целевой функции достигается в точке (24, 14) и равен 2200 ден.ед.

Изображение слайда

12

Слайд 12: Двойственная задача

Двойственная задача. Каждой задаче линейного программирования соответствует двойственная задача. В ней по сравнению с исходной задачей строки переходят в столбцы, неравенства меняют знак, Вместо максимума ищется минимум (или, наоборот, вместо минимума –максимум). Задача, двойственная к двойственной – это сама исходная задача. Сравним исходную задачу (слева) и двойственную к ней (справа): Прямая задача Двойственная задача Целевая функция Целевая функция F = 45 Х 1 + 80 Х 2  → max, F= 400 W 1 + 450 W 2 → min, 5 Х 1 + 20 Х 2  ≤ 400,  5 W 1 + 10 W 2 ≥ 45, 10 Х 1 + 15 Х 2  ≤ 450,  20 W 1 + 15 W 2 ≥ 80, Х 1   ≥ 0,  Х 2  ≥ 0. W 1 ≥ 0, W 2 ≥ 0. Доказано, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной). оптимальные значения W 1 W 2 показывают стоимость материала и труда соответственно, если Их оценивать по вкладу в целевую функцию их принято называть “объективно обусловленными оценками” сырья и рабочей силы.

Изображение слайда

13

Слайд 13

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

Изображение слайда

14

Слайд 14: Симплекс метод

1.Один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования. 2. Был предложен американцем Г. Данцигом в 1951 г. 3. Основная его идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. Метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов. Алгоритмы симплекса-метода позволяют также установить, является ли задача ЛП разрешимой.

Изображение слайда

15

Слайд 15: Симплекс метод. Пример 2

Предприятие может выпускать автоматические кухни, кофеварки и самовары Данные о производственных мощностях (в штуках изделий) приведены в табл. 2. Штамповка и отделка проводятся на одном и том же оборудовании, а сборка проводится на отдельных участках Таблица 2 Кухни Кофеварки Самовары Штамповка 20000 30000 12000 Отделка 30000 10000 10000 Сборка 20000 12000 8000 Объем выпуска x 1 x 2 x 3 Удельная прибыль (на 1 изделие) 15 12 14

Изображение слайда

16

Слайд 16: Симплекс метод. Продолжение примера 2

Для удобства восприятия система ограничений дана в процентах и задача линейного программирования имеет вид Х 1   ≥ 0, Х 2  ≥ 0, Х 3   ≥ 0, (0) Х 1   / 200 + Х 2  / 300 + Х 3   / 120 ≤ 100, (1) Х 1   / 300 + Х 2  / 100 + Х 3   / 100 ≤ 100, (2) Х 1 / 200 ≤ 100, (3) (вытекает из 1, можно исключить) Х 2 / 120 ≤ 100, (4) (вытекает из 2, можно исключить) Х 3 / 80 ≤ 100, (5) F = 15 Х 1 + 12 Х 2  + 14 Х 3 → max. Кухни Кофеварки Самовары Штамповка 20000 30000 12000 Отделка 30000 10000 10000 Сборка 20000 12000 8000 Объем выпуска x 1 x 2 x 3 Удельная прибыль 15 12 14

Изображение слайда

17

Слайд 17: Симплекс метод. Продолжение примера 2

После исключения неравенств (3) и (4) задача линейного программирования в окончательном варианте примет вид F = 15 Х 1 + 12 Х 2  + 14 Х 3 → max. Х 1   / 200 + Х 2  / 300 + Х 3   / 120 ≤ 100 (1), Х 1   / 300 + Х 2  / 100 + Х 3   / 100 ≤ 100 (2), Х 3 / 80 ≤ 100 (5) В соответствии с симплекс методом, вводом новых переменных система неравенств приводится в систему равенств. В конкретной задаче вводятся 3 новых переменных. В полученной системе равенств 3 уравнения и 6 неизвестных. Система решается путем последовательного перебора базовых переменных которая приводит к росту целевой функции

Изображение слайда

18

Слайд 18: Симплекс метод. Продолжение примера 2

После ввода новых переменных система примет вид Х 1   / 200 + Х 2  / 300 + Х 3   / 120 + Х 4   = 100 Х 1   / 300 + Х 2  / 100 + Х 3   / 100 + Х 5   = 100 (*) Х 3 / 80  +  Х 6  = 100 15 Х 1 + 12 Х 2  + 14 Х 3   =  F Симплекс метод – первая итерация В данную систему переменные Х 4, Х 5  , Х 6 входят только в одно из уравнений с коэффициентом 1 и являются базисными. Свободные переменные Х 1  , Х 2,, Х 3 можно приравнять любой константе, в том числе – нулю. Тогда первое допустимое решение (0,0,0,100, 100, 100), значение целевой функции F =0. Дальнейшая система пересчетов сводится к переводу одной из свободных переменных в базис и с выводом одной из базисных переменных и переводом ее в свободные переменные.

Изображение слайда

19

Слайд 19: Симплекс метод. Продолжение примера 2

Х 1   / 200 + Х 2  / 300 + Х 3   / 120 + Х 4   = 100 Х 1   / 300 + Х 2  / 100 + Х 3   / 100 + Х 5   = 100 (**) Х 3 / 80  +  Х 6  = 100 15 Х 1 + 12 Х 2  + 14 Х 3   =  F Симплекс метод – вторая итерация 1. В качестве новой базисной переменной выбираем Х 1 – переменную с наибольшим положительным коэффициентом в F. 2. Сравниваем частные от деления свободных членов на коэффициенты при выбранной базисной переменной Х 1. Получаем 100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞. Выбираем в системе строку, которая соответствует этому. Это – первая строка. После ряда преобразований над системой (**) получаем новую систему (***)

Изображение слайда

20

Слайд 20: Симплекс метод. Продолжение примера 2

Х 1   + 2/3 Х 2   + 2/1,2 Х 3   + 200 Х 4   = 20000 7/900 Х 2   + 4/900 Х 3  – 2/3  Х 4 + Х 5   = 100/3, (***) Х 3 / 80 +   Х 6  = 100 2 Х 2  – 11 Х 3  – 3000 Х 4  =  F – 300000 В новой системе базисными являются Х 1, Х 5, Х 6, свободными – Х 2, Х 3, Х 4. Второе допустимое решение (20000,0,0,0,100/3, 100) Значение F = 300000. Симплекс метод – вторая итерация Так как наименьший положительный коэффициент в целевой функции – при Х 2, то выбираем Х 2 базисной переменной. Проводя аналогичные действия, образуем частные от деления свободных членов на коэффициенты при Х 2, получаем 20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞. В качестве разрешающей выбираем вторую строку и после ряда преобразований и пересчетов получаем систему (****) и целевую функцию

Изображение слайда

21

Слайд 21: Симплекс метод. Продолжение примера 2

Х 1   + 9/7 Х 3   + 1800/7 Х 4 – 600/7 Х 5   = 120000/7 Х 2   + 4/7 Х 3  – 600/7 Х 4  + 900/7 Х 5   = 30000/7 (****) Х 3 / 80  +  Х 6   = 100 – 85/7 Х 3  – 19800/7 Х 4  – 1800/7 Х 5  =  F – 308571 Из (****) следует, что базисными переменными являются Х 1 =120000/7, Х 2   = 30000/7, Х 6   = 100, F = 308571. Так как в строке – 85/7 Х 3  – 19800/7 Х 4  – 1800/7 Х 5  =  F – 308571 не осталось ни одного положительного коэффициента, то оптимальный план найден и производственная программа такая: Кухни – 120000/7 = 17143 Кофемолки – 30000/7 = 4286 Самовары – 0 Максимальная прибыль – 308571 усл. ден. ед. Все производственное оборудование будет задействовано за исключением линии по сборке самоваров

Изображение слайда

22

Слайд 22: Транспортная задача

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

Изображение слайда

23

Слайд 23: Транспортная задача. Пример 3

Исходные данные к транспортной задаче. Таблица 3. Потребители П1 П2 П3 П4 Запасы( a) Склады с1 2 5 5 5 60 с2 1 2 1 4 80 с3 3 1 5 2 60 Потребности ( b) 50 40 70 40 200

Изображение слайда

24

Слайд 24: Транспортная задача. Пример 3

Надо спланировать перевозки, т.е. выбрать объемы Х ij  поставок товара со склада i потребителю j, где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений: По запасам на складах: По ограничениям на потребление X 11  + Х 12  + Х 13  + Х 14  = 60, X 11  + Х 21 + Х 31   = 50 X 21  + Х 22  + Х 23  + Х 24  = 80, X 12  + Х 22 + Х 32  = 40, X 31  + Х 32  + Х 33  + Х 34  = 60. X 13  + Х 23 + Х 33   = 70, X 14  + Х 24 + Х 34   = 40 Всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны – еще 12 ограничений. Целевая функция – издержки по перевозке, которые необходимо минимизировать: F = 2 X 11  + 5 Х 12  + 4 Х 13  + 5 Х 14  + X 21  + 2 Х 22  + Х 23  + 4 Х 24  + 3 X 31  + Х 32  + 5 Х 33   + 2 Х 34  → min.

Изображение слайда

25

Последний слайд презентации: Методы оптимальных решений: Транспортная задача

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

Изображение слайда

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

Понятие «оптимальные решения» в экономике

Определение 1

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

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

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

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

• Статистика.
• Психология.
• Математика.
• Менеджмент.

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

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

Готовые работы на аналогичную тему

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

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

• Ограничения. Результат должен соответствовать заранее установленным ограничениям исследования.
• Функция. Целевая функция выражает числовое значение, которое подтвердит качество решения.

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

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

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

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

Особенности оптимальных решений в экономике

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

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

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

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

Онлайн-помощь Помощь на 📝 экзамене по мору (методы оптимальных решений)

1. Сколько стоит помощь?

Цена, как известно, зависит от объёма, сложности и срочности. Особенностью «Всё сдал!» является то, что все заказчики работают со экспертами напрямую (без посредников). Поэтому цены в 2-3 раза ниже.

2. Каковы сроки?

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

3. Выполняете ли вы срочные заказы?

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

4. Если потребуется доработка или дополнительная консультация, это бесплатно?

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

5. Я разместил заказ. Могу ли я не платить, если меня не устроит стоимость?

Да, конечно – оценка стоимости бесплатна и ни к чему вас не обязывает.

6. Каким способом можно произвести оплату?

Работу можно оплатить множеством способом: картой Visa / MasterCard, с баланса мобильного, в терминале, в салонах Евросеть / Связной, через Сбербанк и т.д.

7. Предоставляете ли вы гарантии на услуги?

На все виды услуг мы даем гарантию. Если эксперт не справится — мы вернём 100% суммы.

8. Какой у вас режим работы?

Мы принимаем заявки 7 дней в неделю, 24 часа в сутки.

Страница не найдена | MIT

Перейти к содержанию ↓

• Образование
• Исследовательская работа
• Инновации
• Прием + помощь
• Студенческая жизнь
• Новости
• Выпускников
• О MIT
• Подробнее ↓
  • Прием + помощь
  • Студенческая жизнь
  • Новости
  • Выпускников
  • О MIT

Меню ↓ Поиск Меню Ой, похоже, мы не смогли найти то, что вы искали!
Попробуйте поискать что-нибудь еще! Что вы ищете? Увидеть больше результатов

Предложения или отзывы?

Optimal Solution Set – обзор

43.3.4 Подход 2: Изучение эффективных параметров реконструкции с использованием многоцелевой оптимизации

Для OS-SIRT наилучшее качество и минимальное время – это две цели, которые по своей природе противоречат друг другу. По сути, не существует единого решения, удовлетворяющего все цели. Поиск оптимальных решений – это хороший компромисс или компромисс между целями. Следовательно, эта проблема обучения параметрам на самом деле является многоцелевой оптимизацией (MOO) [3,5]. Вообще говоря, существует два класса подходов к этой проблеме: объединение целевых функций в одну составную функцию или определение недоминируемого оптимального набора решений (так называемого оптимального набора по Парето).Ядро подхода 1, описанного ранее, принадлежит к первому классу многоцелевых задач оптимизации. Две цели взвешиваются вместе, чтобы сформировать единую целевую функцию путем выбора различных критериев маркировки. Однако, когда у пользователя нет конкретного требования к качеству или времени, но ему интересно узнать уровень потенциального прогресса в достижении каждой цели, когда реконструкция продолжается, недоминируемый оптимальный по Парето набор более полезен и разумен.

Для решения задач MOO хорошо подходят генетические алгоритмы (ГА).Генетические алгоритмы, вдохновленные эволюционной теорией происхождения видов, разрабатывались десятилетиями. Они имитируют процесс эволюции видов в природе: сильные виды имеют больше возможностей передавать свои гены следующим поколениям, и в то же время могут происходить случайные изменения, приносящие дополнительные преимущества. В результате естественного отбора слабые гены в конечном итоге будут устранены. GA действует аналогичным образом, эволюционируя из популяции с индивидуумами, представляющими начальные решения, с такими операторами, как отбор, кроссовер и мутация для создания нисходящих поколений.Функция приспособленности используется для оценки человека, определяющего вероятность его выживания для следующего поколения. Для MOO используется несколько фитнес-функций. Были описаны многочисленные методы ГА, такие как взвешенный генетический алгоритм (WBGA), генетический алгоритм с векторной оценкой (VEGA), многоцелевой генетический алгоритм (MOGA) и генетический алгоритм недоминируемой сортировки (NSGA) [3]. Подход 1 – это настраиваемое приложение комбинации фитнес-функций WBGA для удовлетворения наших особых требований.VEGA ограничен из-за «средней» проблемы, тогда как MOGA сильно зависит от правильного выбора коэффициента совместного использования. NSGA прогрессирует медленнее, чем MOGA, и его вычислительная эффективность оказывается неэффективной.

В нашей работе мы выбрали NSGA-II [1], который является улучшенной версией NSGA в качестве метода нахождения оптимального по Парето множества. Этот метод использует элитарность и перегруженный оператор сравнения, чтобы сохранить как наследование от хорошо работающих хромосом, так и разнообразие найденных оптимальных решений при сохранении вычислительной эффективности.Мы выполняем процесс обучения следующим образом: после генерации начальной популяции алгоритм реконструкции OS-SIRT и алгоритм поиска параметров NSGA-II запускаются поочередно до тех пор, пока не будет удовлетворен критерий остановки (например, после достаточного количества генераций) . Эта схема попадает в категорию модели «ведущий-ведомый» параллельных генетических алгоритмов [6]. В каждом поколении OS-SIRT выполняется как параллельный оценщик значений пригодности, в то время как NSGA-II объединяет эти значения, чтобы найти текущий набор решений с заданным пользователем размером набора.Время записывается как одна цель, а качество реконструкции оценивается с помощью метрики восприятия E-CC, представленной далее в этой главе. Чтобы превратить оптимизацию в задачу минимизации, мы модифицируем метрику качества на расстояние до единицы. Процесс останавливается до тех пор, пока решения в текущем наборе не будут недоминировать друг друга. Для операторов отбора, скрещивания и мутации мы используем бинарный турнирный отбор, реальный кодированный смешанный кроссовер и неоднородную мутацию. Хотя найденные нами параметры могут не быть существенно лучше для конкретного пользовательского спроса, они предоставляют пул кандидатов, которые являются компромиссом времени и качества.Что еще более важно, они получаются значительно быстрее, потому что требуется вычислять меньше реконструкций. При подходе 1 нам необходимо выполнить каждую комбинацию репрезентативных параметров, тогда как при подходе 2 вычислительная сложность – это количество поколений, умноженное на удвоенный размер (определяемый пользователем) оптимальных по Парето решений, которые обычно намного меньше.

(PDF) Новый метод оптимального решения транспортных задач в LPP

Journal of Mathematics Research; Vol.10, № 5; Октябрь 2018 г.

ISSN 1916-9795 E-ISSN 1916-9809

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

60

Новый метод оптимального решения транспортных проблем в LPP

Мухаммад Ханиф1 и Фарзана Султана Рафи2

1 Профессор кафедры прикладной математики Научно-технологического университета Ноакхали, Ноакхали 3814,

Бангладеш

2 Преподаватель математики, Департамент компьютерных наук и инженерии, Университет Южной Азии, Дакка 1213,

Бангладеш

Для переписки: Мухаммад Ханиф, профессор кафедры прикладной математики, Ноакхали, наука и технологии

Университет, Ноакхали 3814, Бангладеш.

Получено: 23 апреля 2018 г. Принято: 10 мая 2018 г. Интернет-публикация: 9 августа 2018 г.

doi: 10.5539 / jmr.v10n5p60 URL: https://doi.org/10.5539/jmr.v10n5p60

Abstract

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

. В этой статье мы рассмотрели все стандартные и существующие предложенные методы, а затем предложили новый метод

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

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

, которые дают ясное представление о методе. Программный код для этого метода

записан в Приложении к статье.

Ключевые слова: линейное программирование, транспортные задачи, различные методы оптимизации, кодирование в Matlab

Тема математической классификации (2010): 49Mxx, 65Kxx, 90Bxx, 90Cxx

1. Введение

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

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

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

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

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

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

, произведенный на разных фабриках или заводах (называемых источниками поставок), может быть доставлен на несколько складов или клиентов

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

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

известным американским математиком Альфредом Хичкоком (1899-1980) в 1941 году. Существует несколько алгоритмов удаления этой скобки

, таких как правило северо-западного угла, метод наименьшей стоимости, метод приближения Фогеля, метод минимума строки , Столбец

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

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

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

, таких как ASM Method, Best Candidates Method (BCM), Zero

Suffix Method, ATM Method для оптимизации затрат на транспортировку. Значение целевой функции, полученное таким предложенным методом

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

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

Транспортная проблема (TP) с примером (NW Corner Rule, метод наименьшей стоимости, VAM, сбалансированная TP, несбалансированная TP)

Фото Зейна Ли на Unsplash

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

Исследование оптимальной транспортировки и распределения ресурсов; теория транспорта или теория транспорта. Французский математик Гаспар Монж формализовал эту задачу в 1781 году.Крупные успехи в этой области были сделаны во время Второй мировой войны советским математиком и экономистом Леонидом Канторовичем, поэтому известная как транспортная задача Монжа – Канторовича .

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

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

ПРЕДПОСЫЛКИ

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

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

ДОПУЩЕНИЯ

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

• Общее количество, доступное во всех источниках, равно общему количеству, требуемому в пунктах назначения. Если они не совпадают, добавляются фиктивные источники или фиктивные назначения.
• Стоимость транспортировки единицы от одного пункта отправления до пункта назначения известна и достоверна.
• Стоимость единицы не зависит от количества перевезенных товаров.
• Цель состоит в том, чтобы минимизировать общие транспортные расходы.
• Хотя транспортные задачи могут быть сформулированы как LPP, для их решения разработаны другие более простые алгоритмы.

В основном есть 3 основных этапа

1. Формулировка транспортной модели в LPP

2.Найти базовое возможное решение (BFS)

3. Тест на оптимальность

Давайте подробно рассмотрим

1. ФОРМУЛИРОВАНИЕ МОДЕЛИ ТРАНСПОРТИРОВКИ в LPP

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

Давайте проверим пример ниже.

Пример транспортной задачи с источником = {A, B, C} с общим предложением = 70 и пунктами назначения = {1,2,3} с общим спросом = 70 [изображение автора]

Здесь

Source = { A, B, C}

Они представляют источники с производительностью 10,35,25 единиц товаров соответственно (выделены оранжевым цветом)

Следовательно, общее предложение = 10 + 35 + 25 = 70

Пункты назначения = {1,2 , 3}

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

Следовательно, общий спрос = 20 + 25 + 25 = 70

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

Например,

Затраты, понесенные при перемещении 1 единицы товара из источника A в место назначения 1 = ₹ 2 / –

Затраты, понесенные при перемещении 1 единицы товара из источника A в место назначения 1 = ₹ 2 / – (здесь мы смотрим на сечение источника A и пункта назначения 1 ) [изображение автора]

Аналогично,

Затраты, понесенные при перемещении одной единицы товара из источника B в пункт назначения 2 = ₹ 4 / –

и так далее.[Здесь мы смотрим на сечение источника и назначения]

ВИДЫ ПРОБЛЕМЫ ТРАНСПОРТИРОВКИ

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

В основном существует 2 типа транспортных проблем:

1. Проблема сбалансированного транспорта

2. Проблема несбалансированного транспорта

Классификация транспортных проблем на сбалансированные и несбалансированные на основе имеющегося предложения и необходимого спроса. [изображение автора]

Заглянем внутрь.

1. Задача сбалансированного транспорта

Общее доступное количество = общее требуемое количество

, т. Е. Общее предложение = Общий спрос

Давайте проверим приведенный ниже пример.

Пример сбалансированной транспортной задачи с источником = {A, B, C} с общим предложением = 75 и пунктами назначения = {1,2,3} с общим спросом = 75 [изображение автора]

Здесь

Общее предложение = 75

Общий спрос = 75

Следовательно, Общее предложение = Общий спрос

2.Проблема несбалансированного транспорта

общее доступное количество ≠ общее требуемое количество

то есть общее предложение ≠ общий спрос

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

Есть 2 ситуации, приводящие к этому неуравновешенному состоянию

(i).Общее предложение> Общий спрос

(ii). Общее предложение <Общий спрос

(i). Общее предложение> Общий спрос

То есть общее доступное количество> общее необходимое количество

Давайте проверим пример ниже.

Пример несбалансированной транспортной проблемы с источником = {A, B, C} с общим предложением = 65 и пунктами назначения = {1,2,3} с общим спросом = 60 [изображение автора]

Здесь

Общее предложение = 65

Общий спрос = 60

Следовательно, Общее предложение> Общий спрос

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

Пример несбалансированной транспортной проблемы с источником = {A, B, C} с общим предложением = 65 и пунктами назначения = {1,2,3} с фиктивным спросом = 5, что составляет общий спрос = 65 [изображение автора]

In в этом примере фиктивный спрос = 65–60 = 5

Таким образом, общее предложение = общий спрос

(ii). Общее предложение <Общий спрос

То есть общее доступное количество <общее требуемое количество

Давайте проверим пример ниже.

Пример несбалансированной транспортной проблемы с источником = {A, B, C} с общим предложением = 65 и пунктами назначения = {1,2,3} с общим спросом = 75 [изображение автора]

Здесь

Общее предложение = 65

Общий спрос = 75

Следовательно, Общее предложение <Общий спрос

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

Пример несбалансированной транспортной проблемы с источником = {A, B, C} с общим предложением = 65 и пунктами назначения = {1,2,3} с фиктивным предложением = 10, в результате чего общее предложение = 75 [изображение автора]

In в этом примере фиктивное предложение = 75–65 = 10.

Таким образом, общее предложение = общий спрос

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

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

2. ОСНОВНОЕ ВОЗМОЖНОЕ РЕШЕНИЕ (BFS)

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

(1). Северо-западное (С-З) угловое правило

(2). Метод наименьшей стоимости (или метод минимума матрицы)

(3). Метод аппроксимации Фогеля [VAM] (или штрафной метод)

Давайте углубимся в каждый метод.

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

Вопрос задается ниже.

[изображение автора]

Первый шаг – сделать это стандартной транспортной задачей.

Для этого проверьте, является ли проблема при транспортировке сбалансированной или несбалансированной.

[изображение автора]

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

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

(1). Правило северо-западного (С-З) угла

С-З направление [изображение автора]

Выберите ячейку Северо-западного угла. т.е. стоимость пересечения 1-й строки и 1-го столбца. [Здесь 5 (выделено синим цветом)]

Сравните спрос и предложение этой ячейки. [Здесь 65 и 70 (выделено красным)]

[изображение автора]

Выделите ячейку с наименьшим значением [Здесь 65 (выделено желтым цветом)]

Вычтите исключенную ячейку с наименьшим значением.то есть выделенная ячейка. [Здесь 70–65 = 5]

[изображение автора]

Удалите соответствующий столбец или строку, вычеркнув их. [Здесь столбец с пунктом назначения 1 (отмечен красной линией)]

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

[т.е. здесь 42 + 43 + 65 = 150 (общий спрос) и 5 ​​+ 30 + 50 + 65 = 150 (общий объем предложения)]

Теперь продолжите процесс с оставшимися ячейками.

Снова найдите ячейку Северо-Запад (С-З) и выполните те же действия, что и выше.

Давайте посмотрим на то же самое в этом примере.

[изображение автора] [изображение автора] [изображение автора] [изображение автора]

Здесь и спрос, и предложение будут одинаковыми, которые будут дополнительно распределены в оставшемся сингле клетка.[Здесь, 43] (Это еще один метод проверки правильности всех вышеперечисленных шагов.)

Методы проверки правильности процесса:

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

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

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

Итоговая таблица со всеми выделенными ячейками будет такой.

Это дает начальное возможное решение по методу N-W Corner.

[изображение автора]

Теперь давайте посчитаем стоимость, связанную с этим распределением.

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

т.е. Общая стоимость = (65×5) + (5×7) + (30×4) + (7×7) + (43×7)

= 325 + 35 + 120 + 49 + 301

= 830

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

830 – представляют собой общие затраты, связанные с перемещением товаров.

Путь, по которому идет след, представлен красными стрелками, как мы нашли с помощью метода N-W Corner.

[изображение автора]

Давайте представим то же самое в таблице

окончательное решение, таблица [изображение автора]

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

(2). Метод наименьшей стоимости (или метод минимума матрицы)

Давайте обсудим на том же примере.

[изображение автора] [изображение автора]

Выберите наименьшее значение среди всех затрат (выделено белым цветом). т.е. минимальная стоимость. [Здесь 4 (выделено синим цветом)]

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

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

[изображение автора]

Сравните спрос и предложение этой ячейки. [Здесь 30 и 65 (выделено красным)] Назначьте ячейку с наименьшим значением [Здесь 30 (выделено желтым)]

Вычтите исключенную ячейку с наименьшим значением. то есть выделенное значение ячейки. [Здесь 65–30 = 35]

Удалите соответствующий столбец или строку, удалив ее.[Здесь строка с источником B (отмечена красной линией)]

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

[т.е. здесь 35 + 42 + 43 + 30 = 150 (общий спрос) и 70 + 50 + 30 = 150 (общий объем предложения)]

Теперь продолжите процесс с оставшимися ячейками.

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

Давайте посмотрим на то же самое в этом примере.

[изображение автора] [изображение автора] [изображение автора] [изображение автора]

Здесь и спрос, и предложение будут одинаковыми, которые будут дополнительно распределены в оставшемся сингле клетка. [Здесь, 43] (Это еще один метод проверки правильности всех вышеперечисленных шагов.)

Методы проверки правильности процесса:

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

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

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

Итоговая таблица со всеми выделенными ячейками будет такой.

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

[изображение автора]

Теперь давайте посчитаем стоимость, связанную с этим распределением.

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

т.е. Общая стоимость = (35×5) + (30×4) + (35×7) + (7×7) + (43×7)

= 175 + 120 + 245 + 49 + 301

= 890

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

₹ 890 – представляют собой общие затраты, связанные с перемещением товаров.

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

[изображение автора]

Изобразим то же самое в таблице.

таблица окончательного решения [изображение автора]

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

( 3). Метод аппроксимации Фогеля [VAM] (или штрафной метод)

Давайте обсудим тот же пример.

[изображение автора]

Выбрать стоимостную ячейку для распределения в VAM не так просто, как если бы мы обсуждали метод N-W Corner и метод наименее затратной ячейки. (Успокойся, чувак, это не так уж сложно. «Но процесс немного длиннее, чем раньше».)

В VAM мы должны сначала определить разницу между двумя наименьшими затратами в каждой строке и столбце.Они известны как штрафов / дополнительных расходов.

Учитывается разница между двумя наименьшими значениями.

[изображение автора]

[Здесь Penalties = {2,0,1,1,3,1}]

Теперь найдите максимальное значение среди штрафов независимо от строки или столбца.

[Здесь max (штрафы) = 3 (выделено розовым цветом)]

Если есть ничья, выберите любого. (Какой из них выбрать – это выбор пользователя.)

[изображение автора]

Теперь просмотрите соответствующую строку или столбец.

[Здесь столбец (выделен розовым цветом)]

Выберите наименьшее значение среди всех затрат (выделено розовым цветом). т.е. минимальная стоимость. [Здесь 4 (выделено синим цветом на рисунке ниже)]

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

[изображение автора]

Сравните спрос и предложение этой ячейки [Здесь 30 и 42 (выделены красным)]

[изображение автора ]

Назначьте ячейку с наименьшим значением [Здесь 30 (выделено желтым цветом)]

Вычтите исключенную ячейку с наименьшим значением.то есть выделенная ячейка. [Здесь 42–30 = 12]

Удалите соответствующий столбец или строку, удалив ее. [Здесь столбец с источником B (отмечен красной линией)]

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

[т.е. здесь 65 + 12 + 43 + 30 = 150 (общий спрос) и 70 + 50 + 30 = 150 (общий объем предложения)]

Теперь продолжите процесс с оставшимися ячейками.

Снова найдите штраф и выполните те же действия, что и выше.

Давайте посмотрим на то же самое в этом примере.

[изображение автора] [изображение автора] [изображение автора] [изображение автора]

Здесь и спрос, и предложение будут одинаковыми, которые будут дополнительно распределены в оставшемся сингле клетка. [Здесь, 43] (Это еще один метод проверки правильности всех вышеперечисленных шагов.)

Методы проверки правильности процесса:

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

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

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

Итоговая таблица со всеми выделенными ячейками будет такой.

Это дает начальное возможное решение от VAM.

[изображение автора]

Теперь давайте посчитаем стоимость, связанную с этим распределением.

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

т.е. Общая стоимость = (65×5) + (5×7) + (30×4) + (7×7) + (43×7)

= 325 + 35 + 120 + 49 + 301

= 830

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

830 – представляют собой общие затраты, связанные с перемещением товаров.

Путь, по которому мы идем, обозначен красными стрелками, как мы нашли с помощью VAM.

[изображение автора]

Изобразим то же самое в таблице.

таблица окончательного решения [изображение автора]

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

3. Тест на ОПТИМАЛЬНОСТЬ

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

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

Посмотреть самую последнюю версию.

Архивный контент

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

Архивировано

Эта страница была помещена в архив в Интернете.

Сун Ун Ким, Стивен Г. Херинга и Питер В. Соленбергер

Аннотация

При рассмотрении образца стратификации по нескольким переменным, мы часто сталкиваемся со случаем, когда ожидаемое количество единиц выборки, которые должны быть отобраны в каждой страте, очень мало, и общее количество выбираемых единиц меньше, чем общее количество страты. Эти стратифицированные планы выборки конкретно представлены табличные массивы с действительными числами, называемые проблемами управляемого выбора, и вне досягаемости обычных методов распределения.Множество алгоритмов решения эти проблемы изучались более 60 лет, начиная с Гудмана и Киш (1950). Те, что были разработаны позже, особенно требовательны к компьютеру. и всегда нахожу решения. Однако до сих пор остается без ответа вопрос: В каком смысле решения задачи контролируемого отбора получается из тех алгоритмов оптимально? Введем общее понятие оптимальных решений и предложить новый алгоритм управляемого выбора на основе типичные функции расстояния для достижения решений.Этот алгоритм легко выполняется с помощью нового программного обеспечения на базе SAS. В этом исследовании основное внимание уделяется двустороннему стратификационные конструкции. Решения контролируемого отбора из новых алгоритм сравнивается с существующими алгоритмами с использованием нескольких Примеры. Новый алгоритм успешно находит робастные решения двусторонних задачи управляемого отбора, отвечающие критериям оптимальности.

Ключевые слова:

Ожидание ячейки; Вероятностная выборка; Функция расстояния; Оптимальный массив; Линейное программирование проблема; Симплексный метод.

Содержание

Банкноты

Произошла ошибка при настройке пользовательского файла cookie

Этот сайт использует файлы cookie для повышения производительности. Если ваш браузер не принимает файлы cookie, вы не можете просматривать этот сайт.

---

Настройка вашего браузера для приема файлов cookie

Существует множество причин, по которым cookie не может быть установлен правильно. Ниже приведены наиболее частые причины:

• В вашем браузере отключены файлы cookie.Вам необходимо сбросить настройки вашего браузера, чтобы он принимал файлы cookie, или чтобы спросить вас, хотите ли вы принимать файлы cookie.
• Ваш браузер спрашивает вас, хотите ли вы принимать файлы cookie, и вы отказались. Чтобы принять файлы cookie с этого сайта, используйте кнопку «Назад» и примите файлы cookie.
• Ваш браузер не поддерживает файлы cookie. Если вы подозреваете это, попробуйте другой браузер.
• Дата на вашем компьютере в прошлом. Если часы вашего компьютера показывают дату до 1 января 1970 г., браузер автоматически забудет файл cookie.Чтобы исправить это, установите правильное время и дату на своем компьютере.
• Вы установили приложение, которое отслеживает или блокирует установку файлов cookie. Вы должны отключить приложение при входе в систему или проконсультироваться с системным администратором.

---

Почему этому сайту требуются файлы cookie?

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

---

Что сохраняется в файле cookie?

Этот сайт не хранит ничего, кроме автоматически сгенерированного идентификатора сеанса в cookie; никакая другая информация не фиксируется.

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

3.3a. Решение стандартных задач максимизации с помощью симплекс-метода

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

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

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

Пример 1

С помощью симплексного метода можно решить следующую систему:

Цель Функция: P = 2 x + 3 y + z

При соблюдении ограничений:

3 x + 2 y ≤ 5

2 x + y – z ≤ 13

z ≤ 4

х, у, z≥0

Стандартная задача максимизации

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

• – целевая функция и
• одно или несколько ограничений формы a ₁ x ₁ + a ₂ x ₂ +… a n

  901 _В

  • Все числа a представляют собой действительные коэффициенты, а
  • x _число представляет соответствующие переменные.
  • V – неотрицательное (0 или большее) действительное число

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

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

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

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

Развернуть:

P = 7 x + 12 y

Субъект:

2 x + 3 y ≤ 6

3 x + 7 y ≤12

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

2 x + 3 y + s ₁ = 6

3 x + 7 y + s ₂ = 12

Например, предположим, что
x = 1, y = 1, тогда

2 + 3 + s ₁ = 6 или s ₁ = 1

3 + 7 + s ₂ = 12 или s ₂ = 2

Важно отметить, что эти две переменные, s ₁ и s ₂ , не обязательно одинаковы.Они просто действуют на неравенство, подбирая «слабину», которая не дает левой стороне выглядеть как правая. Следовательно, мы называем их резервными переменными . Это устраняет неравенство за нас. Поскольку расширенные матрицы содержат все переменные слева и константы справа, мы перепишем целевую функцию в соответствии с этим форматом:

–7 x – 12 y + P = 0

Теперь мы можем написать исходную систему уравнений :

2 x + 3 y + s 1 = 6

3 x + 7 y + s 2 = 12

–7 x – 12 y + P = 0

Для этого нам потребуется матрица, которая может обрабатывать x , y , s ₁ , s ₂ и P .Мы разместим это в таком порядке. Наконец, симплексный метод требует, чтобы целевая функция была указана в нижней строке матрицы, чтобы мы имели:

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

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

1. Выберите столбец поворота

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

Таким образом, наша точка поворота – это столбец y .

2. Выберите сводную строку

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

Сначала рассчитаем тестовые соотношения:

[латекс] \ displaystyle {\ left [\ matrix {{6 ÷ 3 = 2} \\ {12 ÷ 7≈1.7}} \ right]} [/ латекс]

Поскольку тестовое соотношение для строки 2 меньше, мы выбираем ее в качестве сводной строки. Штучное значение теперь называется нашей опорной точкой . Чтобы объяснить, почему мы это делаем, заметим, что 2 и 1.7 – это просто вертикальные пересечения двух неравенств. Мы выбираем меньшее, чтобы убедиться, что угловая точка находится в допустимой области:

3. Используя метод исключения Гаусса, удалите строки 1 и 3

Умножьте R2 на (1/7), чтобы преобразовать 7 в 1.

Затем используйте 1, чтобы удалить 3 в R1: -3R ₂ + R ₁ → R ₁

И используйте 1, чтобы устранить -12 в R3: 12R ₂ + R ₃ → R ₃

Получаем следующую матрицу (возможно, дроби)

Что мы сделали? Во-первых, мы максимально увеличили вклад 2-2 входного коэффициента
y -значение в целевую функцию. Оптимизировали ли мы функцию? Не совсем так, поскольку мы все еще видим, что в первом столбце есть отрицательное значение.Это говорит нам о том, что все еще может вносить вклад в целевую функцию. Чтобы устранить это, мы сначала находим сводную строку, получая тестовые отношения:

[латекс] \ displaystyle {\ left [\ matrix {{5/7} & {0} & {1} & {- 3/7} & {0} & {|} {6/7} \\ {3 / 7} & {1} & {0} & {1/7} & {0} & {|} {12/7} \\ {- 13/7} & {0} & {0} & {12 / 7} & {1} & {|} {144/7}} \ right]} [/ latex]

[латекс] \ displaystyle {\ left [\ matrix {{(6/7) ÷ (5/7) ≈1.2} \\ {12 ÷ 3≈4}} \ right]} [/ латекс]

Начиная с 1.2 <4, R1 - наша новая сводная строка.

Интересно, что это тестовое соотношение соответствует входному значению пересечения двух линий!

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

Умножьте R1 на (1 / 0,71), чтобы преобразовать 0,71 в 1.

Затем используйте 1, чтобы удалить 3 в R3: -3R ₁ + R ₂ → R ₂

И используйте 1, чтобы устранить -12 в R3: 1.86R ₁ + R ₃ → R ₃

Получаем следующую матрицу

[латекс] \ displaystyle {\ left [\ matrix {{1} & {0} & {7/5} & {- 3/5} & {0} & {|} {6/5} \\ {0 } & {1} & {- 3/5} & {2/5} & {0} & {|} {6/5} \\ {0} & {0} & {13/5} & {3 / 5} & {1} & {|} {114/5}} \ right]} [/ latex]

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

[латекс] \ displaystyle {\ left [\ matrix {{1} & {0} & {7/5} & {- 3/5} & {0} & {|} {6/5} \\ {0 } & {1} & {- 3/5} & {2/5} & {0} & {|} {6/5} \\ {0} & {0} & {13/5} & {3 / 5} & {1} & {|} {114/5}} \ right]} [/ latex]

Таким образом, мы готовы прочитать решения.

4. Определите набор решений

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

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

[латекс] \ displaystyle {\ left [\ matrix {{1} & {0} & {7/5} & {- 3/5} & {0} & {|} {6/5} \\ {0 } & {1} & {- 3/5} & {2/5} & {0} & {|} {6/5} \\ {0} & {0} & {13/5} & {3 / 5} & {1} & {|} {114/5}} \ right]} [/ latex]

Установка переменных резервирования на 0 дает:

x ≈ 1.2

y ≈ 1,2

P = 22,8

Таким образом, x = 1,2, y = 1,2, P = 22,8 – это решение задачи линейного программирования. То есть, входные данные x = 1,2 и y = 1,2 дадут максимальное значение целевой функции 22,8

.

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

.

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

• Pivot,
• Pivot1 и
• Симплекс

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

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

Пример 2

Новая авиакомпания решила выйти на рынок. Он рассматривает возможность предложения рейсов из Феникса, штат Аризона, и изначально хотел бы отправиться в три разных места: Сан-Диего, Сан-Франциско и Лас-Вегас. Расстояния каждого рейса туда и обратно, вылетающего из Феникса, составляют (приблизительно): 720 миль, 1500 миль и 1140 миль соответственно. Компания хотела бы использовать слоган: «Средняя цена за рейс никогда не превышает 200 долларов». Что касается затрат, ожидается, что полеты в Сан-Диего будут составлять около 10% от стоимости авиабилетов.Точно так же на Сан-Франциско будет приходиться 12%, а на Лас-Вегас – 14% авиаперевозок. Компания хочет, чтобы общая средняя стоимость не превышала 10% от заработанных авиабилетов. Недавнее исследование рынка позволяет компании сделать вывод, что она могла бы продать около 1900 билетов в Сан-Диего, 700 билетов в Сан-Франциско и 1000 билетов в Лас-Вегас. В этих условиях и при условии, что все проданные билеты являются рейсами в оба конца, какую сумму компания должна взимать за билет, чтобы максимизировать свой общий доход?

Решение

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

x = цена билета в оба конца до Сан-Диего

y = цена билета в оба конца до Сан-Франциско

z = цена за билет в оба конца до Лас-Вегаса

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

R = 1900 x + 700 y + 1000 z

При соблюдении ограничений:

• Средняя цена за рейс не превышает 200 долларов США
• Средняя стоимость авиабилетов не более 10% от общей суммы

Математически,

• Добавьте цены и разделите на 3
  [latex] \ displaystyle \ frac {{{x} + {y} + {z}}} {{3}} \ le {200} [/ latex]
• Или x + y + z ≤ 600
• Общий доход от билетов в Сан-Диего составит 10% от этой суммы.То есть Стоимость = 0,10 (1900 x ) = 190 x . Точно так же имеем 0,12 (700 y ) = 84 y и 0,14 (1000 z ) = 140 z . Мы хотим, чтобы сумма этих затрат была меньше или равной 10% от общего дохода, что составляет 0,10 (1900 x + 700 y + 1000 z ) = 190 x + 70 y + 100 z .
• 190 x + 84 y + 140 z ≤ 190 x + 70 y + 100 z
• или 14 y + 40 z ≤ 0

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

Переписанная целевая функция:

–1900 x – 700 y – 1000 z + R = 0

И упрощенные ограничения:

x + y + z ≤ 600 (умножить обе стороны на 3)

14 ярдов + 40 ярдов ≤ 0

х, y≥0

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

x + y + z + s ₁ = 600

14 y + 40 z + s ₂ = 0

У нас будут следующие переменные столбцы:
x , y , z, s ₁ , s ₂ , R и постоянный столбец, всего 7 столбцы.Всего у нас есть два ограничения и одна целевая функция для трех строк. Теперь напишем исходную симплексную таблицу:

[латекс] \ displaystyle {\ left [\ matrix {{1} & {1} & {1} & {1} & {0} & {0} & {|} {600} \\ {0} & { 14} & {40} & {0} & {1} & {0} & {|} {0} \\ {- 1900} & {- 700} & {- 1000} & {0} & {0} & {1} & {|} {0}} \ right]} [/ latex]

Теперь таблица готова к решению с использованием Simplex.

Поворот по 1-му столбцу и 1-й строке. (Вы не можете делить на 0, чтобы получить сводную строку)

[латекс] \ displaystyle {\ left [\ matrix {{1} & {1} & {1} & {1} & {0} & {0} & {|} {600} \\ {0} & { 14} & {40} & {0} & {1} & {0} & {|} {0} \\ {0} & {1200} & {900} & {1900} & {0} & {1} & {|} {1140000}} \ right]} [/ латекс]

Поскольку базовым будет только столбец x , мы можем видеть, что x = 600 является решением.Поскольку y и z не являются базовыми переменными, мы устанавливаем y = z = 0. То есть они не способствуют максимизации дохода. Кроме того, R является активной переменной, поэтому мы видим, что R = 1 140 000 долларов США – это максимальный доход, который компания может получить с учетом ограничений. Им следует продавать билеты в Сан-Диего за 600 долларов и не продавать рейсы в другие города. Как нетрудно догадаться, компания, вероятно, немного ошеломлена. Мы рассмотрим это в следующем примере.

Интересно, что поездки в Сан-Диего сами по себе приносят наибольший доход, исходя из данных ограничений. Почему это? Если мы посмотрим на ограничения, мы увидим, что компания вполне уверена, что сможет продать 1900 рейсов в Сан-Диего. Компания также несколько озадачена тем, что предполагается продавать билеты по 600 долларов за штуку. На этом этапе он может решить добавить к модели некоторые дополнительные ограничения.

Пример 3

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

Решение

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

x ≤ 150

Добавляя третью переменную slack, получаем

x + с ₃ = 150

Это добавляет один столбец и одну строку в нашу таблицу:

[латекс] \ displaystyle {\ left [\ matrix {{1} & {1} & {1} & {1} & {0} & {0} & {0} & {|} {600} \\ { 0} & {14} & {40} & {0} & {1} & {0} & {0} & {|} {0} \\ {1} & {0} & {0} & {0} & {0} & {1} & {0} & {|} {150} \\ {- 1900} & {- 700} & {- 1000} & {0} & {0} & {0} & {1 } & {|} {0}} \ right]} [/ латекс]

Решение этой проблемы с помощью Simplex дает

[латекс] \ displaystyle {\ left [\ matrix {{0} & {0} & {- 13/7} & {1} & {- 1/14} & {- 1} & {0} & {| } {450} \\ {0} & {1} & {20/7} & {0} & {1/14} & {0} & {0} & {|} {0} \\ {1} & {0} & {0} & {0} & {0} & {1} & {0} & {|} {150} \\ {0} & {0} & {1000} & {0} & {50 } & {1900} & {1} & {|} {285000}} \ right]} [/ латекс]

Решение: x = 150, y = 0, z = 450 и R = 285000

Пример 4

Кейтеринговая компания готовит обед к деловой встрече.Здесь подают бутерброды с ветчиной, легкие бутерброды с ветчиной и вегетарианские бутерброды. Сэндвич с ветчиной состоит из 1 порции овощей, 4 ломтиков ветчины, 1 ломтика сыра и 2 ломтиков хлеба. Легкий бутерброд с ветчиной состоит из 2 порций овощей, 2 ломтиков ветчины, 1 ломтика сыра и 2 ломтиков хлеба. Вегетарианский бутерброд состоит из 3 порций овощей, 2 ломтиков сыра и 2 ломтиков хлеба. Всего доступно 10 пакетов ветчины, в каждой по 40 ломтиков; Доступно 18 буханок хлеба, каждая по 14 ломтиков; Доступно 200 порций овощей и 15 пакетов сыра, по 60 ломтиков в каждом.Учитывая ресурсы, сколько бутербродов можно произвести, если цель состоит в том, чтобы максимально увеличить количество бутербродов?

Решение

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

x = количество бутербродов с ветчиной

y = Количество легких бутербродов с ветчиной

z = количество вегетарианских бутербродов

Общее количество бутербродов равно

.

S = x + y + z

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

Всего у компании
: 10 (40) = 400 ломтиков ветчины, 18 (14) = 252 ломтика хлеба, 200 порций овощей и 15 (60) = 900 ломтиков сыра. Максимум, компания может использовать вышеуказанные суммы.

Есть два бутерброда с ветчиной: для первого требуется 4 ломтика ветчины, а для второго – только 2 на бутерброд. То есть 4 x + 2 y ≤ 400

То есть общее количество ломтиков ветчины не может превышать 400.

Для каждого бутерброда требуется 2 ломтика хлеба, поэтому 2 x + 2 y + 2 z ≤ 252

В бутербродах с ветчиной 1 и 2 порции овощей соответственно, а в вегетарианском бутерброде 3 порции овощей. Итак, 1 x + 2 y + 3 z ≤ 200

Для обоих бутербродов с ветчиной требуется один ломтик сыра, а для вегетарианского бутерброда – два ломтика сыра, поэтому 1 x + 1 y + 2 z ≤ 900 Ниже приведена законченная модель линейного программирования для этого примера.

Развернуть: S = x + y + z

Субъект Кому: 4 x + 2 y ≤ 400

2 x + 2 y + 2 z ≤ 252

x + 2 y + 3 z ≤ 200

1 x + 1 y + 2 z ≤ 900

x, y, z≥0

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

Включая резервные переменные, получаем:

4 x + 2 y + 0 z + s ₁ = 400

2 x + 2 y + 2 z + s ₂ = 252

x + 2 y + 3 z + s ₃ = 200

x + y + 2 z + s ₄ = 900

– x – y – z + S = 0

Исходная симплексная таблица:

[латекс] \ displaystyle {\ left [\ matrix {{4} & {2} & {0} & {1} & {0} & {0} & {0} & {0} {|} & {400 } \\ {2} & {2} & {2} & {0} & {1} & {0} & {0} & {0} {|} & {252} \\ {1} & {2} & {3} & {0} & {0} & {1} & {0} & {0} {|} & {200} \\ {1} & {1} & {2} & {0} & { 0} & {0} & {1} & {0} {|} & {900} \\ {- 1} & {- 1} & {- 1} & {0} & {0} & {0} & {0} & {1} {|} & {0}} \ right]} [/ latex]

Поскольку самое отрицательное число в нижней строке одинаково для трех столбцов, мы можем использовать любой столбец.Можно также использовать первый столбец. Наименьшее частное получается путем деления 4 на 400, так что строка 1 является сводным столбцом. Разворот на «4» в R1C1 дает доход.

[латекс] \ displaystyle {\ left [\ matrix {{1} & {1/2} & {0} & {1/4} & {0} & {0} & {0} & {0} {| } & {100} \\ {0} & {1} & {2} & {- 1/2} & {1} & {0} & {0} & {0} {|} & {52} \\ {0} & {3/2} & {3} & {- 1/4} & {0} & {1} & {0} & {0} {|} & {100} \\ {0} & { 1/2} & {2} & {- 1/4} & {0} & {0} & {1} & {0} {|} & {800} \\ {0} & {- 1/2} & {- 1} & {1/4} & {0} & {0} & {0} & {1} {|} & {100}} \ right]} [/ latex]

Примечание: мы увеличили S с 0 до 200, но у нас все еще есть отрицательный знак в нижней строке.Поскольку «-1» более отрицательное значение, чем «-1/2», мы переместимся на столбец 3. После деления положительных чисел выше «-1» на константы мы получим наименьшее частное в строке 2. Поворачиваясь на «2» ”В выходах R2C3.

[латекс] \ displaystyle {\ left [\ matrix {{x} & {y} & {z} & {s1} & {s2} & {s3} & {s4} & {S} \\ {1} & {1/2} & {0} & {1/4} & {0} & {0} & {0} & {0} {|} & {100} \\ {0} & {1/2} & {1} & {- 1/4} & {1/2} & {0} & {0} & {0} {|} & {26} \\ {0} & {0} & {0} & { 1/2} & {- 3/2} & {1} & {0} & {0} {|} & {22} \\ {0} & {- 1/2} & {0} & {1 / 4} & {- 1} & {0} & {1} & {0} {|} & {748} \\ {0} & {0} & {0} & {1/2} & {0} & {0} & {0} & {1} {|} & {126}} \ right]} [/ latex]

Теперь у нас есть оптимальное решение

• x = 100 (базовая переменная в строке 1)
• y = 0 (небазовая переменная)
• z = 26 (основная переменная строка 2)
• s1 = 0 (небазовая переменная)
• s2 = 0 (небазовая переменная)
• s3 = 22 (строка базовой переменной 3)
• s4 = 748 (строка базовой переменной 4)
• S = 126 (строка базовой переменной 5)

Конечно, нас действительно интересуют: x = 100, y = 0, z = 26, S = 126

Мы обнаружили, что необходимо приготовить 100 бутербродов с ветчиной, 26 вегетарианских бутербродов и 0 легких бутербродов с ветчиной, чтобы максимально увеличить общее количество приготовленных бутербродов.