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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПЕРМСКИЙ ИНСТИТУТ (ФИЛИАЛ)

федерального государственного бюджетного образовательного учреждения высшего профессионального образования

РОССИЙСКИЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ имени Г.В. ПЛЕХАНОВА

Кафедра информационных технологий и математики

К.т.н., Погудин Андрей Леонидович

Контрольная работа по дисциплине

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

Вариант № 19

Пермь 2015г.

Оглавление

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

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

3. Задача управления запасами. 9

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

Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В и С. Потребность a_ij i -го вида сырья для производства каждой единицы j -го вида продукции, запас b_i соответствующего вида сырья и прибыль c_j от реализации единицы j -го вида продукции заданы таблицей:

• Для производства двух видов продукции I и II с планом x ₁ и x ₂ единиц составить математическую модель, т.е. целевую функцию прибыли F и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n единиц обоих видов продукции.

• Найти оптимальный план X * = (x ₁, x ₂) производства продукции, обеспечивающий максимальную прибыль F_max. Определить остатки каждого вида сырья. Задачу решить симплекс-методом.

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

• Составить математическую модель двойственной задачи (систему ограничений по единичной прибыли и целевую функцию общих издержек на сырье Z); найти оптимальный набор цен на сырьё Y *=(y ₁, y ₂, y ₃), обеспечивающий минимум общих затрат на сырье Z_min.

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

• Решить задачу оптимизации в MS Excel в режиме «поиск решения». Провести исследование полученного решения, используя отчеты по результатам, по устойчивости, по пределам; сделать выводы. Ответы, полученные в результате решений «вручную» и с помощью Excel, должны совпадать.

Решение

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

Определим максимальное значение целевой функции F(X) = 4x1 + 4x2 при следующих условиях-ограничений.

2x1 + 2x2≤14

x1 + x2≤7

2x1 + 3x2≤18

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

В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.

2x1 + 2x2 + 1x3 + 0x4 + 0x5 = 14

1x1 + 1x2 + 0x3 + 1x4 + 0x5 = 7

2x1 + 3x2 + 0x3 + 0x4 + 1x5 = 18

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

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

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

X1 = (0,0,14,7,18)

Базисное решение называется допустимым, если оно неотрицательно.

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2
и из них выберем наименьшее:

min (14: 2, 7: 1, 18: 3) = 6

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

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₅ в план 1 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 1, получена в результате деления всех элементов строки x₅ плана 0 на разрешающий элемент РЭ=3

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₂ плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x₂ и столбец x₂.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и

РЭ.

Представим расчет каждого элемента в виде таблицы:

Итерация №1.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1
и из них выберем наименьшее:

min (2: ²/₃, 1: ¹/₃, 6: ²/₃) = 3Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (²/₃) и находится на пересечении ведущего столбца и ведущей строки.

Поскольку в последнем столбце присутствует несколько минимальных элементов 3, то номер строки выбираем по правилу Креко.
Метод Креко заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения min=3, делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам.
4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₃ в план 2 войдет переменная x₁.
Строка, соответствующая переменной x₁ в плане 2, получена в результате деления всех элементов строки x₃ плана 1 на разрешающий элемент РЭ=²/₃
На месте разрешающего элемента в плане 2 получаем 1.

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

Представим расчет каждого элемента в виде таблицы:

Не нашли, что искали? Воспользуйтесь поиском: