Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
Краткое сожержание материала:

Размещено на

6

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ПСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Контрольная работа

"Методы принятия управленческих решений"

Студентка: Соколова Е.В.

Преподаватель: Дятлов Ю.Н.

• Псков 2013
• Задание 1
• симплексный программирование производство транспортный

Для производства трех видов продукции (А, В и С) предприятие использует два вида сырья, удельный расход которого представлен в таблице 1.

Таблица 1. Расход сырья и прибыль от реализации 1 т продукции

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

Решение.

Экономико-математическая модель задачи имеет следующий вид:

Переменные:

х₁ - объем реализации продукции А, ед.

х₂ - объем реализации продукции В, ед.

х₃ - объем реализации продукции С, ед.

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

Максимум прибыли от реализации продукции, тыс. д.е.

f(х) = 26х₁+34х₂+16х₃mах

Ограничения:

По использованию сырья 1 вида, т/сут.

16х₁+36х₂+34х₃12600

По использованию сырья 1 вида, т/сут.

34х₁+16х₂+26х₃15400

Условие не отрицательности переменных х₁0, х₂0, х₃0.

Алгоритм симплексного метода включает следующие этапы:

1.Составление первого опорного плана

Система ограничений задачи, решаемой симплексным методом задана в виде неравенств смысла " " , правые части которых в_i0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных х₄; х₅. Они образуют базис, называются базисными переменными и определяют объемы неиспользованных ресурсов:

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

Решим систему уравнений относительно базисных переменных:

Функцию цели запишем в виде уравнения f(х) = 0 - (-26х₁ - 34х₂ - 16х₃). Полагая что основные переменные х₁=0 х₂=0 х₃=0, получим первый опорный план, х₄=в₁; х₅=в₂ f(x) =0; который заносим в симплексную таблицу 2. Она состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположным знаком:

Таблица 2. Первый план симплексной таблицы

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

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

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

Первый опорный план, представленный в первой симплексной таблице неоптимальный, т.к. в индексной строке находятся отрицательные коэффициенты: -26; -34; -16.

Полагая что основные переменные х₁=0; х₂=0; х₃=0, а дополнительные переменные х₄=12600; х₅=15400; f(x)=0. Следовательно, продукция не продается, а сырье не используется, доход равен нулю. В этом случае переходим к следующему этапу алгоритма.

3. Определение ведущих столбца и строки

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

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

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

За ведущий столбец выберем столбец, соответствующий переменной х_1, т.к. сравнивания по модулю [-34] >[-26]; [-16].

Вычислим значения _iпо строкам и выберем наименование 12600/36 = 350 (min); 15400/16=962,5; следовательно, строка х₄ является ведущей.

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

4. Построение нового плана.

Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса. Сначала заменим переменные в базисе, т.е. вместо (х_i) (х₄) в базис войдет переменная (х_j) (х₂) соответствующая ведущему столбцу. Разделим все элементы ведущей строки предыдущей симплексной таблицы на разрешающий элемент и результаты деления занесем в начальную строку следующей симплексной таблицы. Все остальные других строк определяются по формуле: Новый элемент = соответствует коэффициент предыдущего плана - (коэффициент ведущего столбца предыдущей таблицы * коэффициент начальной строки нового плана). Выполняя последовательно все этапы алгоритма, составляем второй план (таблица 3).

Таблица 3. Второй план симплексной таблицы

Анализ второго плана:

План не оптимальный т.к. в индексной строке имеется отрицательный коэффициент (-10,904). Максимальный доход в размере 12600 тыс.д.е. торговое предприятие получит от продажи продукции В в количестве 350 ед. (х₂). На третьей итерации получаем план 3 (таблица 4), который является оптимальным т.к. все коэффициенты в индексной строке 0.

Таблица 4. Третий план симплексной таблицы

Анализ третьего плана:

Необходимо продавать продукцию А в количестве 364 ед., а продукцию В в количестве 188 ед. При этом торговое предприятие получает максимальный доход в размере 15856 тыс.д.е. Продукции группы С не реализуются. Ответ: х₁=364 ед., х₂=188 ед., х₃=0 ед., f(x)=15856 тыс. д.е.

Задание 2

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

Таблица 5. Исходные параметры транспортной задачи

Определить опорный план перевозок с помощью метода северо-западного угла или минимального элемента. Рассчитать оптимальный план перевозок, имеющий минимальную стоимость с использованием метода потенциалов.

Таблица 6. Исходные параметры транспортной задачи

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

Решение.

1. Экономико-математическая модель задачи имеет следующий вид:

Переменные:

X₁₁ - объем груза, перевозимого c I склада в магазин № 1, т;

Х₁₂ - объем груза, перевозимого cо I склада в магазин № 2, т;

Х₁₃ - объем груза, перевозимого c I склада в магазин № 3, т;

Х₁₄ - объем груза, перевозимого c I склада в магазин № 4, т;

Х₂₁ - объем груза, перевозимого cо II склада в магазин № 1, т;

Х₂₂ - объем груза, перевозимого cо II склада в магазин № 2, т;

Х₂₃ - объем груза, перевозимого cо II склада в магазин № 3, т.

Х₂₄ - объем груза, перевозимого cо II склада в магазин № 4, т.

Х₃₁ - объем груза, перевозимого cо III склада в магазин № 1, т;

Х₃₂ - объем груза, перевозимого cо III склада в магазин № 2, т;

Х₃₃ - объем груза, перевозимого cо III склада в магазин № 3, т.

Х₃₄ - объем груза, перевозимого cо III склада в магазин № 4, т.

Ограничения:

1) по возможности I склада, т х₁₁ + х₁₂ + х₁₃+ х₁₄ = 44

2) по возможности II склада, т х₂₁ + х₂₂ + х₂₃ + х₂₄ = 26

3) по возможности II склада, т х₃₁ + х₃₂ + х₃₃ + х₃₄ = 30

4) по потребности магазина № 1, т х₁₁ + х₂₁ +х_...