Некоторые понятия линейного программирования. Математическое программирование

Название	Некоторые понятия линейного программирования. Математическое программирование
Дата	11.12.2022
Размер	0.99 Mb.
Формат файла
Имя файла	13_3.Osnovnye_ponyatiya_lineinogo_-68358.doc
Тип	Документы #839152
страница	1 из 2

1 2

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

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

    Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода).

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

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

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

(1)

где X = (x₁, x₂ , ... , x_n); W – область допустимых значений переменных x₁, x₂ , ... , x_n ;f(Х) – целевая функция.

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

такое, что

при любом

.

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

    Методы решения оптимизационных задач зависят как от вида целевой функции f(Х), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

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

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

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

(2)

(3)

(4)

        (5)

    При этом система линейных уравнений (3) и неравенств (4), (5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности.

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

    Допустимое решение – это совокупность чисел (план) X = (x₁, x₂, ... , x_n), удовлетворяющих ограничениям задачи. Оптимальное решение – это план, при котором целевая функция принимает свое максимальное (минимальное) значение.

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

    Компания "Русские краски" производит краску для внутренних и наружных работ из сырья двух типов: Ml и М2. Следующая таблица представляет основные данные для задачи.

Таблица 1. Основные данные
	Расход сырья на тонну краски		Максимально возможный ежедневный расход сырья
	Для наружных работ	Для внутренних работ	Максимально возможный ежедневный расход сырья
Сырье М1	6	4	24
Сырье М2	1	2	6
Доход, руб. на тонну	5	4	-

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

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

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

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

   В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ. Обозначим эти объемы как переменные модели: x₁ — ежедневный объем производства краски для наружных работ; х₂ — ежедневный объем производства краски для внутренних работ.

    Используя эти переменные, далее строим целевую функцию. Логично предположить, что целевая функция, как суммарный ежедневный доход, должна возрастать при увеличении ежедневных объемов производства красок. Обозначим эту функцию через z (она измеряется в тысячах руб) и положим, что Z = 5x₁ + 4x₂.

    В соответствии с целями компании получаем задачу: Максимизировать Z = 5x₁ + 4x₂.

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

    Из таблицы с данными имеем следующее.

    Используемый объем сырья Ml = 6x₁ + 4х₂ (т)

    Используемый объем сырья М2 = 1x₁ + 2х₂ (т)

    Так как ежедневный расход сырья Ml и М2 ограничен соответственно 24 и 6 тоннами, получаем следующие ограничения. 6x₁ + 4х₂ ≤ 24 (сырье Ml) x₁ + 2x₂ ≤ 6 (сырье М2)

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

    Второе можно сформулировать так: разность между ежедневными объемами производства красок для внутренних и наружных работ не должна превышать одной тонны, т.е. х₂ – x₁ ≤ 1.

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

    Окончательно задача будет записана следующим образом:
Максимизировать z = 5х₁ + 4х₂ при выполнении ограничений
6х₁ + 4х₂ ≤ 24,
x₁ + 2х₂ ≤ 6,
-x₁ + 2x₂ ≤1
х₂ ≤ 2,
х₁ ≥ 0, х₂ ≥ 0.

    Любое решение, удовлетворяющее ограничениям модели, является допустимым. Например, решение x₁ = 3 и х₂ = 1 будет допустимым, так как не нарушает ни одного ограничения, включая условие неотрицательности. Значение целевой функции при этом решении будет равно z = 19 (тысяч руб.).

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

    На следующем шаге мы приведем решение этой задачи с помощью программы Tora.

рассмотрим реализацию задачи линейного программирования в программе Tora.

    1. Запустите программу Tora.exe. В результате будет отображено окно (рис. 1). Нажмите любую клавишу для входа в программу.

Рис. 1. Окно прграмы TORA

2. Будет отображено окно с меню (рис. 2). Для решения задач линейного программирования выберите (Linear programming).

Рис. 2. Окно меню

3. В результате будет открыто подменю (рис. 3):

Рис. 3. Окно подменю

    1) Прочитать созданный файл данных задачи (необходимо ввести полный путь к файлу *.or)

    2) Ввести новую задачу

    Выберите второй вариант.

    4. На экране будет отображено окно с формой для ввода данных задачи (рис. 4):

Рис. 4. Окно формы

    В верхней строке рабочего окна укажите имя задачи (Problem Title); это произвольный идентификатор (но русские буквы программа не понимает). Вторая строка — число переменных (Nbr of Variables); после выхода из ячейки программа сообщает, что по умолчанию присвоила переменным имена x_i, где i — номер переменной. Третья строка — число ограничений (Nbr of constraints). Следующие четыре строки запрашивают, желает ли пользователь дать переменным оригинальные имена (User-Defined Vars Names), задать ненулевые нижние границы (Nonzero Lower Bounds) и верхние границы (Finite Upper Bounds) изменения переменных, ввести неограниченные по знаку переменные (Unrestricted Variables). Во всех случаях по умолчанию принято "нет", поэтому при входе в ячейку в ней появляется буква n; нужно либо ввести y ("да"), либо уйти из ячейки. Если хотя бы в одной из этих строк принятое по умолчанию значение было изменено, то на одном из последующих шагов программа запросит необходимую дополнительную информацию.

    В поля формы последовательно введите следующие значения:
1) Имя проблемы - Reddy Mikks
2) Количество переменных – 2 (x₁ — ежедневный объем производства краски для наружных работ; х₂ — ежедневный объем производства краски для внутренних работ)
3) Количество ограничений – 4 (не учитывать указание неотрицательности переменных)
4) Оригинальные имена – да
5) Задать ненулевые нижние границы - нет
6) Задать верхние границы – нет
7) Ввести неограниченные по знаку переменные – нет

    В результате получим следующую форму (рис. 5):

Рис. 5. Окно формы

Нажмите клавишу Enter. Появится строка для ввода имен переменных рис. 6 (под х₁ введите – Int (для наружных работ); под х₂ введите – Ext (для внутренних работ)). Нажмите Enter.

→

Рис. 6. Строка для ввода имен переменных

Появится строка для ввода коэффициентов целевой функции (рис. 7):

→

Рис. 7. Строка для ввода коэффициентов функции

Выберите одно из значений (max – максимизировать (по умолчанию), min – минимизировать (для изменения введите m)). Введите в поле (под х₁) значение 5. Нажмите Enter. В поле под х₂ введите 4. Нажмите Enter.

На следующих шагах нужно внести ограничения (Constraint 1 - 4) рис. 8. Введем первое ограничение:
1) х₁ – 6
2) х₂ – 4
3) символ ≤ оставим без изменения (для изменения символа нужно ввести нужный с клавиатуры)
4) свободный член (RHS) – 24

→

Рис. 8. Ввод ограничений

Аналогично введите остальные три ограничения. После ввода Constraint 4 нажмите F8. Последует сообщение о сохранении файла данных (нажмите y) и введите путь и имя файла с расширением or. (рис. 9).

Рис. 9. Сохранение файла данных

Нажмите Enter.

5. В результате будет отображено меню решения/ модификации задачи (рис. 10).

Рис. 10. Окно меню решения и модификации задачи

    1) Solve Problem – решить задачу

    2) Modify data – изменить данные задачи

    3) View data – просмотреть данные задачи

    4) Print data – вывести на печать (или в файл)

    Выберите - решить задачу. В результате будет открыто подменю предлагающее произвести решение автоматически (Automated procedure) или под управлением пользователя (User-guided procedure). В этом меню стоит выбрать автоматическое решение.

Рис. 11. Окно подменю

Затем в появившемся меню выбрать (View solution / sensitivity summery) – просмотреть результат и провести анализ чувствительности.

Рис. 12. Окно выбора действий

6. В результате проделанных действий должен получиться следующий результат (рис. 13):

Рис. 13. Результат решения задачи

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

    2) Следует раздел Optimum solution summary – итоговая сводка оптимального решения, который предоставляет следующую информацию:

    а. Obj value – значение целевой функции при найденном оптимальном решении (доход - 21.0000)

    б. Variable – имена переменных

    в. Value – оптимальные значения переменных

    г. Obj Coeff – коэффициент целевой функции

    д. Obj Val Contrib – произведение оптимального значения на значение коэффициента целевой функции

    Далее следует сообщение о том, что для перехода к новому разделу (или для продолжения просмотра текущего) следует нажать кнопку PgDn, а для возврата к предыдущему – PgUp. Перейдите к следующей таблице раздела Optimum solution summery, в которой предоставлена информация об ограничениях (Constraint) рис. 14.

Рис. 14. Информация об ограничениях

В столбце Slack(-)/Surplus(+) указаны значения дополнительных переменных (остаточных (-) и избыточных (+)). В задаче все дополнительные переменные являются остаточными. Значения дополнительных переменных для первых двух неравенств равны нулю, следовательно, сырье М1 и М2 будут использованы полностью, в третьем и четвертом ограничении остаточные переменные отличны от нуля, следовательно, неравенства этих ограничений выполняются строго. Для перехода к новому разделу нажмите PgDn.

7. В результате будет открыт раздел Sensitivity analysis (анализ чувствительности). В таблице приводится результаты анализа чувствительности при изменении по отдельности (single changes) коэффициентов целевой функции (таблица Obj Coeffs). Например, текущее оптимальное решение сохраняется до тех пор, пока доход на тонну краски для внешних работ составляет от 2 тыс. до 6 тыс.

Рис. 15. Раздел анализа чувствительности

Столбец Reduced Cost (Приведенная цена). С точки зрения экономиста переменные в модели ЛП можно рассматривать как числовые характеристики интенсивности определенных видов деятельности (или процессов), в результате которых потребляются ресурсы ("вход" модели) в целях получения прибыли ("выход" модели). Из этой интерпретации вытекает следующее определение.

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

8. На новой странице представлены данные таблицы значений правых частей неравенств ограничений (Righthand side) рис. 16.

Рис. 16. Таблица значений

    Например, текущее оптимальное решение будет сохранено, если ежедневные поступления сырья М1 (ограничение 1) будет находиться в пределах от 20 до 36 тонн. В столбце Dual Price (Двойственная цена) указана стоимость единицы материала. Теперь рассмотрим определение двойственной цены. Двойственная цена — это просто еще одно название стоимости единицы ресурсов. Она равна вкладу, который привносит в значение целевой функции изменение на одну единицу лимита, определяющего доступность ресурса. Термин "двойственная цена" произошел от названия "проблема двойственности" из теории линейного программирования. Хотя название "стоимость единицы ресурсов" лучше отображает смысл, вкладываемый в это понятие, мы все же будем использовать термин "двойственная цена" (dual price), так как он применяется во всех коммерческих программах решения задач ЛП.

    Двойственные цены для сырья M1 и М2 равны соответственно 0.75 и 0.5 (т.е. $750 и $500) за тонну (здесь через M1 и М2 обозначено количество материалов М1 и М2 соответственно). Отсюда следует, что если, например, доступное количество сырья Ml возрастет от текущего уровня в 24 т до 28, тогда оптимальное значение целевой функции увеличится на $750 х (28 - 24) = $3000.

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

    9. В таблице Objective Coefficients (рис. 17) приведены результаты анализа влияния на оптимальное решение одновременного изменения (Simultaneous changes) всех коэффициентов целевой функции.

    Чтобы отследить результат одновременного изменения коэффициентов целевой функции, в данной модели представим эту функцию как z = (5 + d₁)x₁ + (4 + d₂)x₂. Тогда условие неотрицательности, накладываемое на дополнительные переменные sx₃ и sx₄ первого и второго ограничений, будет записано в виде следующих неравенств:

0.75 + 0.25d₁ - 0.125d₂ ≥ 0
0.05 - 0.50d₁ + 0.750d₂ ≥ 0

Рис. 17. Результаты анализа при изменении коэффициентов целевой функции

    Эти неравенства эквивалентны системе неравенств 1/2 ≤ c₁/c₂ ≤ 6/4. Для того чтобы убедиться в эквивалентности этих неравенств, подставьте в последние из них выражения с₁ = 5+ d₁ и с₂ = 4 + d₂ и выполните необходимые действия (проверьте!).

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

    10. В результате будет отображена последняя таблица хода решения проблемы Right-hand side ranging (результаты анализа влияния на оптимальное решение одновременного изменения значений правых частей всех неравенств) рис. 18.

Рис. 18. Результат анализа при изменении значений
правых частей всех неравенств

    В данной модели представим правые части неравенств как 24 + D₁, 6 + D₂, 1 + D₃ и 2 + D₄. Тогда оптимальные значения переменных можно выразить через новые переменные D₁, D₂, D₃ и D₄ (соответствующие формулы показаны в таблице Right-hand Side Ranging — Simultaneous Changes на рис. 18). Для того чтобы решение было осуществимым, необходимо выполнение условия неотрицательности для значений переменных в оптимальном решении — тем самым накладываются ограничения на новые переменные D₁, D₂, D₃ и D₄.

   Например, положим D₁ = 5, D₂ = -1, D₃ = 1 и D₄ = 2. Тогда
x₁ = 3 + 0.25 * 5 - 0.5 * (-1) = 4.75
x₂ = 1.5 - 0.125 * 5 + 0.75 * (-1) = 0.125
sx₅ = 2,5 + 0.375 * 5 – 1,25 * (-1) + 1 * 1 = 6.625
sx₆ = 0.5 + 0.125 * 5 - 0.75 * (-1) + 1 * 2 = 3.875

    Здесь значения всех переменных положительные. Следовательно, имеем оптимальное решение x₁ = 4.75 т, х₂ = 0.125 т и z = 5 * 4.75 + 4 * 0.125= 24.25 (т.е. 24 250). Полученное значение z больше текущего оптимального на величину z = 24 250 - 21 000 = 3 250. Эту разность можно подсчитать также по формуле z = D₁y₁ + D₂y₂ + D₃y₃+ D₄y₄, где у₁, у₂, у₃ и у₄ — двойственные цены соответствующих ресурсов. На основании последней формулы получаем z = 5 * 750 + (-1) * 500 + 1 * 0 + 2 * 0 = 3250.

    Этот способ вычислений применим только тогда, когда изменения D_i, i = 1, 2, 3, 4, приводят к допустимому решению. Если в результате изменений правых частей ограничений значение какой-нибудь переменной будет отрицательным, то это означает, что необходимо искать новую точку оптимального решения.

    Файл с задачей можно взять здесь.

    На следующем шаге мы рассмотрим решение этой же задачи с помощью Microsoft Excel.

1. Осуществляем ввод данных в таблицу Excel (рис. 1).

Рис. 1. Заполнение листа для решения задачи

Для переменных задачи x₁ и x₂ отведены ячейки B3 (имя ячейки - int) и C3 (имя ячейки - ext). Эти ячейки называются рабочими или изменяемыми ячейками. В изменяемые ячейки значения не заносятся и в результате решения задачи в этих ячейках будет отражено оптимальное значение переменной.

В ячейку D4 (имя ячейки - sum) вводится формула для вычисления целевой функции задачи (дохода) z = 5x₁ + 4x₂. Чтобы сделать это надо выполнить следующие действия:

поместить курсор в D4;
вызвать Мастер функций;
в появившемся окне выбрать "Математические" и "СУММПРОИЗВ" (рис. 2).

Рис. 2. Мастер функций, Шаг 1

В окне мастера функций нажать OK, в появившемся окне (рис. 3) в поле "массив 1" ввести (протаскивая курсор мыши по ячейкам) адреса изменяемых ячеек B3:C3. В поле "массив 2" вводятся адреса ячеек содержащих цены на краски B4:C4, после нажать OK.

Рис. 3. Мастер функций, Шаг 2

В ячейку D8 вводится формула для вычисления израсходованного количества сырья M1: 6x₁ + 4x₂, а в ячейку D9 вводится формула для израсходованного количества сырья M2: x₁ + 2x₂. В ячейку D10 вводится формула для вычисления спроса на краску: -1x₁ + 4x₂, а в ячейку D11 вводится формула ограничения на краску для внутренних работ: x₂. Эти формулы вводятся аналогично целевой функции.

В результате страница примет вид:

Рис. 4. Вид страницы после добавления формул

2. В меню "Сервис" выбираем процедуру "Поиск решения". В появившемся окне (рис. 5) нужно установить адрес целевой ячейки D4, значение целевой ячейки: максимальное, адреса изменяемых ячеек B3:C3.

Рис. 5. Поиск решения

3. Чтобы ввести ограничения задачи, нажать кнопку "Добавить". В появившемся диалоговом окне слева ввести адрес D8 (израсходованное количество сырья M1), затем выбрать знак ≤ и в правой части количество сырья M2, равное 24 (или адрес ячейки E8). После ввода нажать кнопку "Добавить" и аналогично ввести второе ограничение.

Рис. 6. Добавление ограничения

4. После ввода ограничений получим следующий вид окна поиска решения:

Рис. 7. Результат добавления ограничений

5. В окне "Поиск решения" нажать "Параметры" в появившемся окне (рис. 8) установить флажок в пункте "Линейная модель". В этом случае при решении задачи будет использоваться симплекс - метод. Остальные значения можно оставить без изменения. После нажать кнопку ОК.

Рис. 8. Окно Параметры

6. Для решения задачи в окне "Поиск решения" нажать кнопку "Выполнить". Если решение найдено появляется окно (рис. 9).

Рис. 9. Результаты поиска решения

7. Для просмотра результатов выбираем тип отчета: "Результаты" и нажимаем кнопку ОК. "Отчет по результатам" состоит из трех таблиц (рис. 10):

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

Рис. 10. Отчет Результаты

Из этих таблиц видно, что в оптимальном решении:
производство краски для наружных работ B3 = 3 ;
производство краски для внутренних работ С3 = 1.5 ;
при этом доход D4 = 21 ;
расход сырья М1 D8 = 24 ;
расход сырья М2 D9 = 6 ;
таким образом, оба ресурса дефицитные (соответствующие ограничения называются связанными).

Первоначальная таблица EXCEL заполняется результатами, полученными при решении (рис. 11).

Рис. 11. Результат поиска решения

   Файл с решением этой задачи можно взять здесь.

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

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

    Задача 1. В некотором машинном центре производятся два изделия, причем на производство одной единицы первого изделия затрачивается 10 минут рабочего времени, а на единицу второго изделия — 12 минут. Рабочее время машинного центра ограничено величиной в 2500 минут в день (некоторые операции центр может выполнять параллельно). В рабочий день допустимо производить от 150 до 200 единиц первого изделия, но не более 45 единиц второго изделия. Предполагая, что доход от единицы первого изделия составляет 6.00, а второго — 7.50, постройте модель и найдите оптимальное соотношение между объемами производства изделий, максимизирующее общий доход.

    Файл с моделью к задаче, а также реализацию задачи в программе Tora и в таблицах Excel можно взять здесь.

    Задача 2. Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. Данные об организации перевозок следующие:

Таблица 1. Данные об организации перевозок
	Количество вагонов в поезде
	багажный	почтовый	плацкарт	купе	СВ
скорый	1	1	5	6	3
пассажирский	1	-	8	4	1
число пассажиров	-	-	58	40	32
парк вагонов	12	8	81	70	26

Сколько должно быть сформировано скорых и пассажирских поездов, чтобы перевезти наибольшее количество пассажиров?

    Файл с моделью к задаче, а также реализацию задачи в программе Tora и в таблицах Excel можно взять здесь.

    Задача 3. Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров – не менее 70 и витаминов – не менее 10 усл. ед. Содержание их в каждой единице продуктов П1 и П2 равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед. Стоимость 1 ед. продукта П1 – 2 руб., П2 –3 руб. Постройте математическую модель задачи, позволяющую так организовать питание, чтобы его стоимость была минимальной, а организм получил необходимое количество питательных веществ.

    Файл с моделью к задаче, а также реализацию задачи в программе Tora и в таблицах Excel можно взять в приложениях 13_3

1 2