CОУТ. Задачи. Задача 3 15 Задача 5 18 Список использованных источников 22 Задание 1
 Скачать 76.67 Kb.
|
1 2 СодержаниеЗадание 1 2 Задание 2 7 Задача 3 15 Задача 5 18 Список использованных источников 22 Задание 1 Составить экономико-математические модели следующих задач. 11. Производственная мощность завода позволяет производить за месяц 200 электродвигателей типа А или 600 электродвигателей типа В. Определить, сколько электродвигателей каждого типа должен производить завод для достижения максимума товарной продукции, если спрос на электродвигатели типа В превышает спрос на электродвигатели типа А в два раза? Решение Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 200x1+1200x2 при следующих условиях-ограничений. x1≤200 x2≤600 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. x1+x3 = 200 x2+x4 = 600 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:  Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x3, x4 Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,200,600) Базисное решение называется допустимым, если оно неотрицательно.
Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (- , 600 : 1 ) = 600 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А∙В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:
Получаем новую симплекс-таблицу:
Итерация №1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (200 : 1 , - ) = 200 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x3 в план 2 войдет переменная x1. Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x3 плана 1 на разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули. Таким образом, в новом плане 2 заполнены строка x1 и столбец x1. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
Получаем новую симплекс-таблицу:
1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Оптимальный план можно записать так: x1 = 200, x2 = 600 F(X) = 200∙200 + 1200∙600 = 760000 Задание 2 Построить на плоскости область допустимых решений системы линейных неравенств, найти наибольшее и наименьшее значения линейной функции Z(X). Решение Необходимо найти минимальное значение целевой функции F = 200x1+4x2 → min, при системе ограничений: 2x1+x2≥9, (1) x1+2x2≤15, (2) x1+2x2≥9, (3) 2x1+x2≤15, (4) x1 ≥ 0, (5) x2 ≥ 0, (6) Шаг №1. Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом). Построим уравнение 2x1+x2 = 9 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 9. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 4.5. Соединяем точку (0;9) с (4.5;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:2 • 0 + 1 • 0 - 9 ≤ 0, т.е. 2x1+x2 - 9≥ 0 в полуплоскости выше прямой. Построим уравнение x1+2x2 = 15 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 7.5. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 15. Соединяем точку (0;7.5) с (15;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 + 2 • 0 - 15 ≤ 0, т.е. x1+2x2 - 15≤ 0 в полуплоскости ниже прямой. Построим уравнение x1+2x2 = 9 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 4.5. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 9. Соединяем точку (0;4.5) с (9;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:1 • 0 + 2 • 0 - 9 ≤ 0, т.е. x1+2x2 - 9≥ 0 в полуплоскости выше прямой. Построим уравнение 2x1+x2 = 15 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 15. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 7.5. Соединяем точку (0;15) с (7.5;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:2 • 0 + 1 • 0 - 15 ≤ 0, т.е. 2x1+x2 - 15≤ 0 в полуплоскости ниже прямой.  Шаг №2. Границы области допустимых решений. Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений.  Шаг №3. Рассмотрим целевую функцию задачи F = 200x1+4x2 → min. Построим прямую, отвечающую значению функции F = 200x1+4x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (200;4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.  Прямая 1 2 |