Дисциплина: МЕТОДЫ ОПТИМИЗАЦИИ

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

Автор: Коднянко В.А.
 

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

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

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

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

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

     Имеются переменные х = (х₁ , х₂ , … х_n ) и функция этих переменных f(x) = f (х₁ , х₂ , … х_n ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G.

     В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д.

     Линейное программирование характеризуется тем, что
а) функция f(x) является линейной функцией переменных х₁ , х₂ , … х_n
б) область G определяется системой линейных равенств или неравенств.

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

     Математическая модель любой задачи линейного программирования включает в себя:

• максимум или минимум целевой функции (критерий оптимальности);
• систему ограничений в форме линейных уравнений и неравенств;
• требование неотрицательности переменных.

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

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

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

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

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

     Математическая модель. Пусть x1 – неизвестное количество полок вида A, x2 – количество полок вида B, изготавливаемых в неделю. Прибыль от продажи полок составляет 3x1+4x2. Условиями являются ограничения по реализации полок x1 + x2 ≤ 550, по затратам материала 2x1 +3x2 ≤ 1200, по затратам машинного времени 12x1 +30x2 ≤ 9600.

     Постановка задачи. Имеем задачу линейного программирования F(X) = 3x1 + 4x2 → max при вышеперечисленных ограничениях и дополнительных очевидных условиях x1 ≥ 0, x2 ≥ 0.

     Решение задачи в среде MathCAD представлено на нижеследующем рисунке (рис. 1).

Рис.1. Решение задачи графическим методом

.    Сначала разрешаем уравнения x1 + x2 = 550, 2x1 + 3x2 = 1200, 12x1 + 30x2 = 9600 при помощи функции solve относительно переменной x1. При этом функцией будет переменная x2. Можно было бы сделать это проще, сразу записав функцию f1(x1) = 550 - x1, а также f2(x1) = 400 - 2 x1/3, f3(x1) = 320 -2 x1/5, без труда выразив x2 через x1.

     Далее построим графики этих функций, как показано на рисунке. Красная прямая соответствует функции f1(x1), синяя -  f2, зеленая -  f3.

     Каждая из этих прямых делит плоскость на две полуплоскости. При этом только одна полуплоскость отвечает своему условию. Например, условие x1 + x2 ≤ 550, определяет полуплоскость, которая лежит ниже красной прямой, включая и точки, которые на ней находятся. Проверить это легко - для этого достаточно подставить в неравенство точку (0, 0), которая ему удовлетворяет, а следовательно удовлетворяют и все точки этой полуплоскости. Аналогично проверяются полуплоскости, представленные двумя другими условиями 2x1 +3x2 ≤ 1200 и 12x1 +30x2 ≤ 9600. Этим трем полуплоскостостям одновременно удовлетворяют только те точки, которые лежат ниже ломаной, образованной точками BCDE. Если принять во внимание, что еще есть условия x1 ≥ 0, x2 ≥ 0, то всем этим пяти полуплоскостям принадлежат только точки, которые заключены в многоугольник ABCDE.

     Поскольку известно, что экстремальные значения целевой функции 3x1+4x2 лежат в угловых точках области, то осталось лишь проверить в какой из пяти угловых точек A, B, C, D, E данная функция примет наибольшее значение. 

     Используя оператор Given и функцию Find найдем сначала точку D пересечения прямых  f1 и f2 (точка пересечения красной и синей прямых). Видно, что она равна D = (450, 100). Аналогично найдем точку C пересечения пересечения прямых  f2 и f3 (точка пересечения синей и зеленой прямых). Видно, что она равна C = (300, 200).. Точка B найдется из условия пересечения прямой 12x1 + 30x2 = 9600 с вертикальной осью x2 (прямой x1 = 0), при этом получим B = (0, 320). Аналогично найдем точку E = (550, 0) как точку пересечения красной прямой x1 + x2 = 550 с прямой x2 = 0.

     Осталось лишь вычислить значения целевой функции в этих точках и выбрать ту из них, где функция примет наибольшее значение. Как видно из расчетов, это точка D = (450, 100), в которой целевая функция F1 = F(450, 100) = 3x1 + 4x2 = 3* 450 + 4*100 = 1350 + 400 = 1750.  

     Таким образом, наибольшая прибыль в сумме 1750 ден. ед.  обеспечивается в том случае, когда компания в неделю производит 450 полок размера А и 100 полок размера В.

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

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

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

     Суть метода рассмотрим на задаче, которая ранее решена нами графическим методом.

     Итак, имеем задачу  при ограничениях

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

     Здесь – так называемые базисные переменные.

     Применим к решению задачи симплекс-метод. В качестве опорного плана возьмем набор X = (0, 0, 550, 1200, 9600). Для него L(X) = 0.

     Составим симплекс-таблицу, т. е. запишем задачу в матричной форме.

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

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

     В последней строке имеется отрицательный элемент. Следовательно, можно сделать шаг метода. Выберем в ней наименьший отрицательный элемент. Он равен –4. Значит, столбец x2 будем делать новой базисной переменной, то есть вводить ее в базис. Найдем переменную, которую взамен будем выводить из базиса. Для этого вычислим оценки, поделив плановые значения на столбец x2 и занесем их в столбец "Оценка". Выберем в столбце оценок наименьшую оценку, она равна 320. Ей соответствует разрешающая строка базисной переменной x5. Значит, из базиса выводим x5, а вводим x2. На их пересечении находится разрешающий элемент 30.

     Поделим разрешающую строку на разрешающий элемент (кроме ячеек столбца Оценка).

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

     Например, чтобы привести к такому виду строку, которая находится под разрешающей строкой, нужно ее элементы складывать с элементами разрешающей строки, предварительно умножив их на 4. Тогда вместо числа –3 будет –3+4*0.4 = –1.4, вместо –4 будет –4+4*1=0, далее 0 + 4*0 = 0, 0 + 4*0 = 0, 0 + 4*0 = 0 + 4*0,0333 = 0.133, 0 + 4*320 = 1280. Во второй строке при сложении нужно умножать на –3, в первой на –1. В результате таких преобразований получим новую таблицу

     Обновим оценки, разделив столбец План на столбец x1

     Как видим, в базисе появилась переменная x2, которая равна x2 = 320, а отсутствующий пока x1 = 0. В этом случае, как это видно из таблицы, L(X) = 3x1 + 4x2 = 1280, т. е. не выпуская полок размера А, а выпустив лишь полки размера В, можно уже получить прибыль равную 1280 ден. ед. Причем эту прибыль можно увеличить. Действительно, как видно из таблицы, в последней строке имеются отрицательные элементы, а значит, существует лучший план выпуска продукции, который можно найти, совершив еще один шаг симплекс-метода.

     Наименьшей оценкой теперь будет 383,3, а наименьшим числом в последней строке -1,4, откуда становится видно, что в базис следует ввести x4, а вывести из него x1.

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

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

     Получили лучший план, для которого x1 = 300, x2 = 200, L(X) = 3x1 + 4x2 = 1700. Однако и его можно улучшить, поскольку в последней строке есть отрицательный элемент. Найдем оценки для положительных элементов столбца x5.

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

     Продолжим процесс.

     Видно, что в последней строке нет отрицательных элементов. Это значит, что последний план x1 = 450, x2 = 100, L(X) = 3x1 + 4x2 = 1750 ден. ед. является оптимальным. Это означает, что максимальная прибыль имеет место в том случае, когда предприятие в неделю произведет 450 полок вида A и 100 полок вида B. При этом прибыль составит 1750 ден. ед. Будет изготовлено максимальное число полок в количестве 550 штук, израсходован весь материал, поскольку его остатки x4 = 1200 – 2*450 – 3*100 = 0 и останется неиспользованным x5 = 9600 – 12*450 – 30*100 = 1200 час. машинного времени.
 

3.3. Решение задачи линейного программирования с помощью MathCAD

     Решим эту задачу с помощью MathCAD.

     Добавим начальные условия и целевую функцию.

     Поставим ограничения на неизвестные величины

     Решим задачу при помощи функции maximize:

     Как видим, три метода решения задачи дают один результат.

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

     Дальнейшие расчеты выполним с помощью программы MathCAD.

     Задаем начальные значения вектора x с помощью цикла, где индекс i пробегает значения от 1 до 9 (значок двоеточия набирается русской буквой "Ж", индекс набирается с помощью символа "левая квадратная скобка"):

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

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

     Задаем условия суммы единиц продукции по строкам:

:

     Задаем условия суммы единиц продукции по столбцам:

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

     Используя встроенную функцию Mimimize, находим минимальные значения x1...x9:

     Таким образом оптимальными являются набор x1 = 0; x2 = 100; x4 = 80; x5 = 10; x7 = 120; x8 = 0. Фиктивные x3, x6, x9 не принимаем во внимание.

     При этом минимальная (оптимальная) стоимость перевозок составит:

F(X) = 4*0+2*100+0*0+7*80+5*10+0*150+3*120+7*0+0*0 = 200+560+50+360 = 1170.

     Результаты заносим в транспортную таблицу:

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

    Специальной переменной ORIGIN присваиваем значение 1. Значением ORIGIN является номер первого элемента строки или столбца в матрице. По умолчанию ORIGIN = 0. Введем исходные данные число поставщиков n и число потребителей m.    

     Добавим матрицу стоимостей перевозок c. Для этого используем компоненты панели матриц. Введем также вектор a произведенной продукции поставщиками и вектор b потребляемой продукции. Кроме того добавим единичный вектор g, который будет играть вспомогательную роль. С помощью циклов по переменным i, j обнулим матрицу x.

     Запишем целевую функцию:

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

     Далее проводим решение задачи с использованием функции Minimize:

     Получим следующее решение:

     Это решение совпадает с решением, которое получено ранее.

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

     Имеются n рабочих и n видов работ. Стоимость cij выполнения і-ым работником j-й работы приведена в таблице, где рабочему соответствует строка, а работе – столбец. Необходимо распределить каждого рабочего на отдельный вид работ так, чтобы суммарная стоимость выполнения всех работ была минимальной.

     Пусть n = 4 и матрица стоимости имеет вид:

     Перейдем в Mathcad и введем начальные данные:

     В нашем случае число рабочих и число видов работ = 4.

     С помощью цикла добавим на главную диагональ искомой матрицы X единицы. Кроме того введем два единичных вектора t и a:

     Выведем матрицу и векторы для визуального контроля:

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

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

    Следующим шагом является ввод целевой функции суммарной стоимости работ:

     Теперь введем ограничения:

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

     Теперь обратимся к функции минимизации и поместим результат в матрицу X:

     Получим следующий результат:

     Это означает, что наилучшим способом распределения является способ, когда 1-й рабочий будет назначен на 3-й вид работ, 2-й на 2-й, 3-й на 1-й, 4-й на 4-й (единичные элементы матрицы). При этом наименьшая стоимость работ составит 73 единицы.

3.7. Задача о составлении рациона (задача о диете, задача о смесях)

     Задача. Имеется два вида продукции П₁ и П₂, содержащие питательные вещества S₁, S₂, S₃, S₄ (жиры, белки, углеводы, витамины). Содержание числа единиц питательных веществ в единице каждого вида продукции и необходимый минимум питательных веществ приведены в таблице:

     Решение. Обозначим через х₁ и х₂ – количество продукции П₁ и П₂, входящей в дневной рацион. Тогда общая стоимость рациона составит (д.е.)

F(x) = 3x₁ + 4x₂.

     С учетом необходимого минимума питательных веществ составим систему ограничений. Рацион включает x₁ + 2x₂ единиц питательного вещества S₁, 3x₁ + 2x₂ единиц питательного вещества S2, (2x1 + x2) единиц питательного вещества S3 и (2x1 + 2x2) единиц питательного вещества S4. Так как содержание питательных веществ S1, S2, S3, S4 в рационе должно быть не менее 10, 8, 9, 11 единиц, соответственно, то получим систему ограничений неравенств:

x₁ + 4x₂ ≥ 10,
3x₁ + 2x₂ ≥ 8,
2x₁ + x₂ ≥ 9,
2x₁ + 2x₂ ≥ 11. 

     Необходимо найти такие x₁, x₂, чтобы целевая функция стоимости приняла минимальное значение F(x) = 3x₁ + 4x₂ -> min.

     Решим задачу при помощи Mathcad:

     Таким образом в дневной рацион должно входить x₁ = 4 и x₂ = 1.5 единиц продукции. При этом стоимость рациона окажется минимальной и равной 18 д. е.

     Ниже приведен матричный метод решения этой задачи:

     Разберите и этот способ решения задачи.

3.8. Индивидуальные задания для решения общей задачи линейного программирования

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

     Вариант 1. Предприятие располагает двумя видами сырья S1 и S2 в количествах 15 и 13 условных единиц и изготавливает из него изделия двух видов П1 и П2. Изготовление единицы изделия П1 требует расхода сырья S1 в 1 усл.ед., S2 в 3 усл.ед., а для производства единицы изделия П2 необходимо сырья S1 – 3 усл.ед., сырья S2 - 1 усл.ед. Известна прибыль от реализации одной единицы продукции каждого вида. Для вида П1 она составляет 2 ден.ед, для вида П2 – 3 ден.ед. Требуется найти оптимальный план производства продукции, реализация которого обеспечит предприятию максимальную прибыль.

     Вариант 2. На имеющихся у фермера 400 га земли он планирует посеять кукурузу и сою. Сев и уборка кукурузы требует на каждый гектар 18 тыс. руб. затрат, а сои – 14 тыс. руб. На покрытие расходов, связанных с севом и уборкой, фермер получил ссуду в 6000 тыс. руб. Каждый гектар, засеянный кукурузой, приносит 80 центнеров урожая, а каждый гектар, засеянный соей, – 40 центнеров. Фермер заключил договор на продажу, по которому каждый центнер кукурузы принесет ему 6 тыс. руб., а каждый центнер сои – 2 тыс. руб. Согласно этому договору, фермер обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого равна 22 тыс. центнеров. Фермеру хотелось бы знать, сколько га нужно засеять каждой из этих культур, с тем, чтобы получить максимальную прибыль.

     Вариант 3. На заводе используется сталь трех марок: А, В, С, запасы которых равны соответственно 10, 16 и 12 ед. Завод выпускает два вида изделий. Для изделия 1 требуется по одной единице стали всех марок. Для изделия 2 требуется 2 единицы стали марки В, одна – марки С и не требуется сталь марки А. От реализации единицы изделия вида 1 завод получает 400 руб. прибыли, а вида 2 – 250 руб. Составить план выпуска продукции, дающий наибольшую прибыль.

      Вариант 4. Производитель безалкогольных напитков располагает двумя разливочными машинами А и В по 4 шт. каждой. Машина А спроектирована для пол-литровых бутылок, а машина В – для литровых. Машина А может выпускать до 50 пол-литровых бутылок в 1 мин, а машина В – до 30 литровых бутылок в 1 мин. Каждая из машин работает ежедневно по 6 час, при пятидневной рабочей неделе. Прибыль от продажи одной пол-литровой бутылки составляет 4 цента, а одной литровой бутылки – 10 центов. Недельная продукция не может превосходить 259200 л; рынок за неделю принимает не более 288000 пол-литровых бутылок и не более 180000 литровых бутылок. Сколько бутылок пол-литровых и литровых должна выпускать каждая машина А и В за 1 мин., чтобы максимизировать недельную прибыль производителя от продажи безалкогольных напитков, при имеющихся средствах и условиях.

      Вариант 5. На фабрике планируется выпустить продукцию двух артикулов: № 1 и № 2 из одинаковой пряжи на одинаковых станках. Планируемый суммарный выпуск 80000 тыс. м. Известно, что фабрика может выделить не более 8400 т основной пряжи и 4500 т дополнительной. Требуется составить такую производственную программу, при которой был бы перевыполнен запланированный выпуск ткани и суммарный выпуск ткани оказался бы максимальным (данные по расходам приведены в таблице).

      Вариант 6. На предприятии, выпускающем изделия двух типов, производственная мощность цеха сборки составляет 100 изделий первого и 300 изделий второго типа в сутки. Прибыль от продажи изделия первого типа составляет 2540 руб., а второго - 1804 руб. Отдел технического контроля в состоянии проверить не более 178 изделий любого типа в сутки. Складское помещение способно вмещать 260 мест изделий, при этом изделие первого типа занимает 2 места, а изделие второго типа одно место. Предприятию поставлен план выпустить продукцию на 350 тыс. руб. в сутки. Можно ли выполнить такой план? Можно ли превысить его и, если можно, то на сколько руб.? Сколько изделий при этом следует выпускать в сутки?

      Вариант 7. Завод выпускает 2 вида мороженого: сливочное и шоколадное. Для их изготовления используются 2 исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы исходных продуктов даны в таблице:

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное мороженое не более чем на 116 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 382 кг в сутки. Отпускная цена 1 кг сливочного мороженого 110 ден.ед., шоколадного – 145 ден.ед. Определить количество мороженого каждого вида, которое должна производить фирма, чтобы доход от реализации продукции был максимальным.

      Вариант 8. Чулочно-носочная фирма производит и продает два вида товаров: мужские носки и женские чулки. Фирма получает прибыль в размере 10 руб. от производства и продажи одной пары чулок и в размере 4 руб. от производства и продажи одной пары носков. Производство каждого изделия осуществляется на трех участках. Затраты труда (в часах) на производство одной пары указаны в следующей табл. 2 для каждого участка:

     Рассчитано, что в следующем месяце фирма ежедневно будет располагать следующими ресурсами рабочего времени на каждом из участков: 60 ч на участке 1; 70 ч на участке 2 и 100 ч на участке 3. Сколько пар носков и чулок следует производить ежедневно, если фирма имела максимальную прибыль?

      Вариант 9. Фабрика производит два вида красок: первый – для наружных, а второй – для внутренних работ. Для производства красок используются два ингредиента: А и В. Максимально возможные суточные запасы этих ингредиентов составляют 6 и 8 т соответственно. Известны расходы А и В на 1 т соответствующих красок (см. табл.).

     Изучение рынка сбыта показало, что суточный спрос на краску 2-го вида никогда не превышает спроса на краску 1-го вида более, чем на 1,5 т. Кроме того, установлено, что спрос на краску 2-го вида никогда не превышает 1,9 т в сутки. Цены одной тонны красок равны: 3500 руб. для краски 1-го вида; 2100 руб. для краски 2-го вида. Какое количество краски каждого вида надо производить, чтобы доход от реализации продукции был максимальным ? Какова будет выручка от продажи такой продукции?

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

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

     Вариант 11. На приобретение оборудования для нового производственного участка выделено 300 000 тыс. ден. единиц. Его предполагается разместить на площади 45 м². Участок может быть оснащен оборудованием трех видов: 1) машинами стоимостью 6 тыс. ед. (здесь и далее все показатели приводятся на единицу оборудования), размещающимися на площади 9 м², производительностью 8 тыс. ед. продукции за смену; 2) машинами стоимостью 3 тыс. ед., занимающими площадь 4 м², производительностью 4 тыс. ед. продукции за смену; 3) машинами стоимостью 2 тыс. ед., занимающими площадь 3 м², производительностью 3 тыс. ед. продукции. Построить модель, на основе которой можно решить задачу определения плана оборудования, обеспечивающего наибольшую производительность всего участка.

     Вариант 12. Фирма производит два безалкогольных широко популярных напитка "Колокольчик" и "Буратино". Для производства 1 л. "Колокольчика" требуется 0,02 ч. работы оборудования, а для "Буратино" – 0,04 ч., а расход специального ингредиента на них составляет 0,01 кг. и 0,04 кг. на 1 л. соответственно. Ежедневно в распоряжении фирмы 16 кг. специального ингредиента и 24 ч. работы оборудования. Доход от продажи 1 л. "Колокольчика" составляет 4 руб., а "Буратино" – 9 руб.
Определите ежедневный план производства напитков каждого вида, обеспечивающий максимальный доход от продажи.

     Вариант 13. Фирма производит и продает столы и шкафы из древесины хвойных и лиственных пород. Расход каждого вида в кубометрах на каждое изделие задан в таблице. 

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

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

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

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

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

     Вариант 16. Фирма производит одежду для охотников, туристов и охранных структур. Дополнительно фирма решила изготавливать шапки и подстежки из натурального меха. Затраты на производство этих изделий и запасы сырья представлены в таблице. Спрос на шапки составляет не более 600 шт. в месяц, а подстежек – не более 400 шт. в месяц. 

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

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

.     Вариант 18. Фабрика выпускает два вида каш для завтрака "Малютка" и  "Малыш". Используемые для производства обоих продуктов ингредиенты в основном одинаковы и, как правило, не являются дефицитными. Основным ограничением, накладываемым на объём выпуска, является наличие фонда рабочего времени в каждом из трёх цехов фабрики. Управляющему производством необходимо разработать план производства в месяц. В приведённой ниже таблице указаны общий фонд рабочего времени и число человеко-часов, требуемое для производства 1 т. продукта. 

     Доход от производства 1т каши "Малютка" составляет 1900 руб., а от производства "Малыш" - 1200 руб. На настоящий момент нет никаких ограничений на возможные объёмы продаж. Имеется возможность продать всю произведённую продукцию. Требуется определить объёмы производства этих каш, максимизирующие общий доход фабрики за месяц.

.     Вариант 19. Лесничество имеет 25 га свободной земли под паром и заинтересовано извлечь из нее доход. Оно может выращивать саженцы быстрорастущего гибрида новогодней ели, которые достигают спелости за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1,5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 ч. в год на свое побочное производство. Практика показывает, что требуется 20 ч. для культивации, подрезания, вырубки и пакетирования одной партии деревьев. Для ухода за одним бычком также требуется 20 ч. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб. и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам, одна новогодняя ель принесет чистый доход в 2,5 руб., один бычок – 5 тыс. руб. Сколько следует вырастить саженцев и вырастить бычков чтоб доход был максимальным?

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

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

     Вариант 21. Фирма изготовляет два вида красок для наружных и внутренних работ. Для их производства используют исходные продукты: пигмент и олифу. Расходы исходных продуктов и максимальные суточные запасы указаны в следующей таблице

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

     Вариант 22. Небольшое предприятие производит два вида продукции: столы и стулья. Для изготовления одного стула требуется 3 метра древесины, а для изготовления одного стола – 7 метров. На изготовление одного стула уходит 2 часа рабочего времени, а на изготовление стола – 8 часов. Каждый стул приносит 100 руб. прибыли, а каждый стол – 400 руб. Сколько стульев и сколько столов должно изготовить предприятие, если оно располагает 420 метрами древесины и 400 часами рабочего времени и желает получить максимальную прибыль от реализации своей продукции?

     Вариант 23. Пошивочное предприятие намечает выпуск двух видов костюмов – мужских и женских. На женский костюм требуется 1 м шерсти, 2м лавсана и 1чел/день трудозатрат. На мужской костюм требуется 3,5 м шерсти, 0,5 м лавсана и 1чел/день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 чел/день трудозатрат. Определить сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 1000 денежных единиц, от мужского – 2000 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

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

3.9. Индивидуальные задания для для транспортной задачи

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

Возврат к меню