XXIV Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

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

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Енборисова Т.Д. 1Максимов В.С. 1

---

1МБОУ "СОШ №6" г. Реутов

Амельченко А.М. 1

---

1МБОУ "СОШ №6" г. Реутов

Работа в формате PDF

1.3 MB

Автор работы награжден дипломом победителя I степени

Диплом школьникаСвидетельство руководителя

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

• разобрать алгоритмы решения задач данного вида;

• рассмотреть примеры решения задач с применением данных методов;

• составить тренировочные задания.

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

Методы исследования:

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

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

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

ГЛАВА 1. История возникновения линейного программирования

К первым задачам линейного программирования можно отнести задачи поиска экстремума функций при наличии ограничений типа неравенств. В 1820г. Фурье и затем в 1947г. Данциг предложили метод направленного перебора смежных вершин в направлении возрастания целевой функции – симплекс-метод, ставший основным при решении задач линейного программирования.

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

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

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

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

ГЛАВА 2. Знакомство с задачами линейного программирования и их классификация 2.1. Общая задача линейного программирования

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

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

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

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

Целевая функция имеет вид:

(2.1)

В сокращенном виде функция (1.1) выглядит следующим образом:

(2.2)

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

(2.3)

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

В сокращенном виде система (2.3) имеет вид:

(2.4)

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

2.2. Обзор методов решения задач линейного программирования

2.2.1. Графический метод

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

Алгоритм графического метода:

1. Изобразить в декартовой системе координат (ось абсцисс – х₁, ось ординат – х₂) область определения целевой функции (совокупность точек, удовлетворяющих системе ограничений).

2. Изобразить прямую определения целевой функции.

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

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

Задача 1. Найти оптимальный план следующей оптимизационной задачи:

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

Строим прямые (по двум точкам каждую):

, точки (0;14) и (4;2)

, точки (0;6) и (6;0)

, точки (1;4) и (9;0)

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

Рис. 2.2.1. Решение задачи 1

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

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

Видно, что выход из области (максимум целевой функции) произойдет в точке D пересечения прямых (I) и (II), она имеет координаты (4;2), таким образом максимум целевой функции .

Ответ: .

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

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

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

Таблица 2.2.1. Симплекс-таблица

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

Алгоритм симплекс-метода:

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

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

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

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

Задача 2. Найти оптимальный план следующей задачи:

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

Переменная x₄ входит с единичным коэффициентом только в первое уравнение, переменная x₅ – только во второе уравнение. Именно они и составляют базис задачи. Целевая функция выражена лишь через небазисные переменные x₁, x₂, x₃. Таким образом, имеем каноническую форму представления.

Таблица 2.2.2. Симплекс-таблица решения задачи 2

По сравнению с табл. 2.2.1 в табл. 2.2.2 добавлен еще столбец для симплекс отношений, о чем речь пойдет ниже. В последней строке записаны коэффициенты целевой функции, взятые с противоположными знаками, так как F→max.

Данной симплекс-таблице, согласно вышеприведенному правилу, соответствует опорный план (вершина) вида .

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

Таблица 2.2.3. Вторая итерация симплекс-метода решения задачи 2

Шаги решения задачи 2

1. В последней строке исходной симплекс-таблицы выбираем наименьший отрицательный элемент. Он отмечен знаком *. Столбец, соответствующий этому элементу, называется ведущим. Он определяет переменную, которая будет введена в базис на данном этапе. Это – переменная х₃.

2. Вычисляют отношения свободных членов к элементам ведущего столбца (симплекс-отношение): Q₁=12/2=6, Q₂=18/2=9. Находят наименьшее неотрицательное из этих симплекс-отношений. Оно соответствует ведущей строке, которая определяет переменную, выводимую из базиса. Это – переменная х₄.

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

4. На пересечении ведущей строки и ведущего столбца находится ведущий элемент.

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

6. После нахождения ведущего элемента переходят к следующей таблице (табл.2.2.3). Для этого вначале заполняем первый столбец, записывая новые базисные элементы: х₃ и х₅.

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

8. Остальные элементы ведущего столбца делаем равными нулю.

9. Оставшиеся элементы симплекс-таблицы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 2.2.2, одна вершина которого совпадает с разрешающим элементом, а другая – с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из табл. 2.2.3 будет равен соответствующему элементу табл. 2.2.2 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе – произведение элементов из двух неиспользованных вершин прямоугольника.

Например, элемент, стоящий на пересечении строки х₃ и столбца x₁ находим так: 7 – 2⋅2/2 = 5; свободный член в строке х₅: 18 – 2⋅12/2 = 6; первый элемент последней строки: –3 – 2⋅(–6)/2 = 3 и т.д.

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

11. Вычисляем оптимальное значение целевой функции .

Ответ: .

ГЛАВА 3. Практическое применение методов линейного программирования

3.1. Решение ЗЛП “вручную” графическим методом

Задача 1. Для сохранения здоровья и работоспособности человек должен потреблять в сутки питательных веществ В1 не менее 4 единиц, В2 – не менее 6 единиц, В3 – не менее 9 единиц, В4 – не менее 4 единиц. Имеются два вида пищи: I и II. В 1 кг пищи I содержится питательных веществ: В1 – 2, В2 – 0, В3 – 1, В4 – 3. В 1 кг пищи II содержится питательных веществ: В1 – 1, В2 – 3, В3 – 3, В4 – 2 единицы.

1 кг пищи I стоит 300 рублей, 1 кг пищи II стоит II 200 рублей. Требуется так организовать питание, чтобы стоимость его была наименьшей, а организм получал бы суточную норму указанную выше.

Решение.

Обозначим через х₁ массу (кг) суточного потребления пищи I вида, х₂ – массу (кг) суточного потребления пищи II вида.

Получим систему линейных неравенств:

Обозначим через F стоимость затрат на питание: .

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

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

Видно, что вход в область (минимум целевой функции) произойдет в точке А пересечения прямых и , она имеет координаты (0,6;2,8), таким образом минимум целевой функции .

Ответ: организм будет получать суточную норму питательных веществ при потреблении 0,6 кг пищи I вида и 2,8 кг пищи II вида при этом затраты будут минимальными и составят 740 рублей.

3.2. Решение ЗЛП “вручную” симплекс-методом

Задача 2. Требуется составить смесь, содержащую три химических вещества А, В, С. Известно, что составленная смесь должна содержать вещества А не менее 6 единиц, вещества В не менее 8 единиц, Вещества С не менее 12 единиц. Вещества А, В, С содержатся в трех видах продуктов I, II, III в концентрации, указанной в таблице 3.2.1.

Таблица 3.2.1. Таблица исходных данных

Стоимость единицы продуктов I, II, III различна: единица продукта I стоит 20 рублей, единица II – 30 рублей, единица III – 25 рублей. Смесь нужно составить так, чтобы стоимость используемых продуктов была наименьшей.

Решение. Обозначим через х₁ необходимое количество единиц продукта I, х₂ – количество единиц продукта II, х₃ – количество единиц продукта III.

Получим систему ограничений:

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

Умножим каждое неравенство системы ограничений на –1, получим:

Введем новые неотрицательные переменные x₄, x₅ и x₆. Таким образом, получим каноническую форму представления системы ограничений:

Система является системой с базисом, в которой x₄, x₅, x₆ – базисные, а x_1, x₂ и x₃ свободные переменные (табл.3.2.2). – её базисное решение.

Таблица 3.2.2. Начальная симплекс-таблица: Итерация 0

х₂ – разрешающий столбец, т.к. это наибольший коэффициент по модулю.

х₆ – разрешающая строка, т.к. min(6, 4, 3) = 3.

Таблица 3.2.3. Начальная симплекс-таблица: Итерация 1

Новое базисное решение .

x₃ – разрешающий столбец, т.к. содержит единственный отрицательный коэффициент.

x₄ – разрешающая строка, т.к. min(1,2, 4, 6) = 1,2.

Таблица 3.2.4. Начальная симплекс-таблица: Итерация 2

Новое базисное решение .

x₆ – разрешающий столбец, т.к. содержит единственный отрицательный коэффициент.

x₅ – разрешающая строка, т.к. min(12, 28/9, –) = 28/9.

Таблица 3.2.5. Начальная симплекс-таблица: Итерация 3

На этот раз условие оптимальности выполнено: в последней строке все элементы неположительные. Значит найденный опорный план оптимален.

Оптимальное значение целевой функции:

Ответ: наиболее дешевая смесь будет включать в себя ед. продукта II, ед. продукта III. Стоимость такой смеси составит при этом рублей.

3.3. Решение ЗЛП с помощью Excel

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

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

1. Открываем меню “Файл”, кликнув по соответствующему названию.

2. Кликаем по разделу “Параметры”, который находится внизу вертикального перечня с левой стороны.

3. Далее щелкаем по подразделу “Надстройки”. Здесь отображаются все надстройки программы, а внизу будет надпись “Управление”. Справа от нее представлено выпадающее меню, в котором должны быть выбраны “Надстройки Excel”, обычно уже установленные по умолчанию. Нажимаем кнопку “Перейти”.

4. Все готово. Требуемая функция появится на ленте в правой части вкладки “Данные”.

5. На экране появится новое вспомогательное окно “Надстройки”. Устанавливаем флажок напротив опции “Поиск решения” и нажимаем ОК.

Решим задачу 2 из п.3.2 с помощью данной функции в Excel.

(ссылка на файл решения задачи 2 с помощь Excel)

Решение. Имеем целевую функцию и систему ограничений:

Запишем данные и формулы в окне Excel, как показано на рисунке 3.3.1.

Рис. 3.3.1

На вкладке “Данные” переходим в “Поиск решения”.

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

Рис. 3.3.2

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

Рис. 3.3.2

Таким образом

Ответ: наиболее дешевая смесь будет включать в себя ед. продукта II, ед. продукта III. Стоимость такой смеси составит при этом рублей.

Задача 3. В МБОУ “СОШ №6” г. Реутов уборкой на втором этаже занимаются четыре уборщицы.Каждая из них по своим физическим возможностям и состоянию здоровья может выполнять указанные виды работ с определенной производительностью. Площадь каждой из работ известна. Данные приведены в таблице 3.3.1. Требуется назначить на каждый вид работы одного сотрудника, при этом нужно добиться того, чтобы общее время, затраченное на выполнение работ сотрудниками, было минимальным.

Таблица 3.3.1. Таблица исходных данных

(ссылка на файл решения задачи 3 с помощь Excel)

Решение. Экономико-математическая модель задачи.

Целевая функция – суммарное время, необходимое для завершения всех видов работ, которое необходимо минимизировать:

Функциональные ограничения:

• по работам

• по работникам

Вид расчетной таблицы в MS Excel показан на рис. 3.3.3.

Рис. 3.3.3

Вид таблицы c формулами в MS Excel показан на рис. 3.3.4.

Рис. 3.3.4

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

Литература:

1. Акулич И. Л. Математическое программирование в примерах и задачах: учебное пособие. – М.: Высш. шк., 2008.– 319 с.

2. Горбацевич В.В. Современное линейное программирование [Электронный ресурс]. – Москва: МАТИ – РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К.Э. Циолковского. 1999.-33 с.:

https://rstu.ru/metods/books/gorblinprog1999.pdf.

3. Леонова Н.Л. Задачи линейного программирования и методы их решения: учебно-методическое пособие. – Санкт-Петербург.: СПбГУПТД, 2017. – 77 с.

4. Майкл А., Куслейка Р. Excel 2019. Библия пользователя.: Пер. с англ. – СПб. : ООО "Диалектика", 2019. — 1136 с.

ПРИЛОЖЕНИЕ

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

1. Найти максимум и минимум целевой функции , все переменные неотрицательные, если:

2. Имеются два вида сырья А и В для производства двух видов продукции I и II. Продукт I состоит из 2 единиц сырья А и из 5 единиц сырья В. Продукт II состоит из 3 единиц сырья А и из 3 единиц сырья В. Доход от производства одной единицы продукта I составляет 40 рублей, а от одной единицы продукта II – 50 рублей. Сколько единиц каждого продукта нужно произвести, чтобы максимизировать прибыль, если в распоряжении находится не более 500 единиц сырья А и не более 750 единиц сырья В?

3. На предприятии имеется 6 автомобилей разных моделей. Необходимо в разные районы области перевести 5 грузов. Затраты по перевозке каждого груза каждым автомобилем различны и приведены таблице:

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

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

Пловец	Время (сек.)
	Вольный стиль	Брасс	Баттерфляй	На спине
Гореликов	54	54	51	53
Клочко	51	57	52	52
Шевчук	50	53	54	56
Бурмель	56	54	55	53

Определите команду пловцов (критерий оптимальности − минимальное командное время на дистанции 400 м).

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

Курьер	Заказ 1	Заказ 2	Заказ 3	Заказ 4
К1	15	28	34	32
К2	18	33	39	33
К3	18	32	36	33
К4	16	24	30	29

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