183746 (629921), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Найдя число = 63, => 2-я строка (Х4) является разрешающей. Следовательно, в базис введем Х1 вместо Х4.

Запишем все расчёты в таблицу

Таблица (2.2)

На пересечении разрешающего столбца и строки находится разрешающий элемент - это число 23/7. Производим пересчет всех коэффициентов таблицы, таким образом , чтоб на месте разрешающего элемента получить 1, а в разрешающем столбце все элементы = 0.

Для этого: 1) Третью строку разделим на и запишем получившееся в эту же строку.

2) Из первой строки вычтем вторую, умноженную на и записываем в первую строку.

3) Из третьей строки вычтем вторую умноженную на , результат запишем в третью строку.

4) К строке F прибавим вторую строку умноженную на 23 и запишем в строку F.

Таблица (2.3)

Ответ: из изложенного выше экономического содержания данных таблицы (2.3) следует, что на втором шаге план задачи является оптимальным. Х1* = 63; Х2* = 111. Fmаx= 7329, это значит, что общая стоимость всей произведенной продукции, а она равна 7329 рублей, является максимальной

Решение задачи двойственным методом

Под двойственной задачей понимается вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных.

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

5 Х1+2Х2 ≤ 750 Y1

4

(1.1)

Х1+5 Х2 ≤ 807 Y2

Х1+7Х2 ≤ 840 Y3

F = 30Х₁ +49Х₂ => max

Целевая функция исходной задачи задаётся на максимум, а целевая функция двойственной – на минимум.

С оставим матрицу для исходной задачи:

А =

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

А Т =

Число переменных в двойственной задаче равно числу соотношений в системе (1.1) исходной задачи, т.е. равно трем.

Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений, т .е 750,807,840.

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

Z(Y) = 750Y1 + 807Y2 + 840Y3 => min.

5 Y1 + 4Y2 + Y3 ≥ 30

2Y1 + 5Y2 + 7Y3 ≥ 49

Y1 = 0

Y2 = 7

Y3 = 2

Z(Y) = 750·0 + 807·7+ 840·2 = 7329

Ответ: Z(Y) = F(Х) = 7329, Y1* = 0, Y2* = 7, Y3* = 2.

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

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Задача №2

Формулировка транспортной задачи

На три базы: А₁, А₂, А₃ поступил однородный груз в количествах: а₁, а₂, а₃, соответственно. Груз требуется перевезти в пять пунктов: b₁ в пункт В₁, b₂ в пункт В₂, b₃ в пункт В₃, b₄ в пункт В₄, b₅ в пункт В₅.

Спланировать перевозки так, чтобы общая их стоимость была минимальной. Матрица тарифов сij перевозок между пунктами отправления и пунктами назначения, а также запасы и потребности представлены ниже:

Исходные данные транспортной задачи обычно записываются в таблице:

Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения. Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и запросы потребителей: 400 + 370 + 380 = 1150, 250 + 200 + 290 + 260 + 150 = 1150. => задача с правильным балансом. Составляем начальное опорное решение:

Таблица (1;1)

Т.к. n + m – 1 = 3 + 5 – 1 = 7, а в нашей задаче заполненных клеток всего 6, введём дополнительное число - нуль, на пересечении U1 и V2.

П олучаем решение:

X 1 = - опорное решение №1.

Характеристики

Список файлов курсовой работы