Для связи в whatsapp +905441085890

Курсовая работа по линейному программированию

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

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

Если что-то непонятно — вы всегда можете написать мне в WhatsApp и я вам помогу!

Линейное программирование

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

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

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

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

Курсовая работа по линейному программированию с решением

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

Решение:

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

Для производства изделий Курсовая работа по линейному программированию с решением и Курсовая работа по линейному программированию с решением:

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

На изготовление всех изделий предприятие может использовать оборудование первого типа не более, чем 32 часа, второго типа — не более, чем 60 часов, третьего типа не более, чем 80 часов. Эти ограничения запишем в виде системы неравенств:

Курсовая работа по линейному программированию с решением

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

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

Возможно эта страница вам будет полезна:

Предмет математическое программирование

1-й способ решения (графический метод)

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

Неравенство Курсовая работа по линейному программированию с решением задаёт полуплоскость, ограниченную сверху прямой Курсовая работа по линейному программированию с решением. Прямая Курсовая работа по линейному программированию с решением проходит через точки (0; 16) и (32;0). Неравенство Курсовая работа по линейному программированию с решением задаёт полуплоскость, ограниченную сверху прямой Курсовая работа по линейному программированию с решением, то есть прямой Курсовая работа по линейному программированию с решением. Прямая Курсовая работа по линейному программированию с решением проходит через точки (0;20) и (20;0). ). Неравенство Курсовая работа по линейному программированию с решением задаёт полуплоскость, ограниченную сверху прямой Курсовая работа по линейному программированию с решением. Прямая Курсовая работа по линейному программированию с решением проходит через точки (16;0) и (10;30). Неравенства Курсовая работа по линейному программированию с решением ограничивают множество допустимых решений 1-ой координатной четвертью. Строим опорную прямую Курсовая работа по линейному программированию с решением, то есть Курсовая работа по линейному программированию с решением

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

Точка Курсовая работа по линейному программированию с решением — точка пересечения прямых Курсовая работа по линейному программированию с решением. Координаты точки Курсовая работа по линейному программированию с решением найдём, решив систему уравнений:

Курсовая работа по линейному программированию с решением

Итак, точка А(15;5).

Курсовая работа по линейному программированию с решением

Таким образом, максимум линейной функции

Курсовая работа по линейному программированию с решением

(денежных единиц) при оптимальном решении

Курсовая работа по линейному программированию с решением

Следовательно, наибольшая прибыль от реализации изделий — 70 денежных единиц будет при производстве 15 изделий Курсовая работа по линейному программированию с решением и 5 изделий Курсовая работа по линейному программированию с решением.

Возможно эта страница вам будет полезна:

Решение задач по математическому программированию

2-ой способ решения (симплексным методом)

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

Курсовая работа по линейному программированию с решением

С помощью дополнительных неотрицательных переменных перейдём к системе уравнений. Введём новые переменные Курсовая работа по линейному программированию с решением и добавим их к левым частям ограничений. Получим систему уравнений вместо системы неравенств.

Курсовая работа по линейному программированию с решением

Функция цели имеет вид:

Курсовая работа по линейному программированию с решением

Запишем эту систему уравнений в виде:

Курсовая работа по линейному программированию с решением

Запишем теперь эту систему ограничений в форме векторного уравнения:

Курсовая работа по линейному программированию с решением

Введём векторы:

Курсовая работа по линейному программированию с решением

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

Получим систему:

Курсовая работа по линейному программированию с решением

из которой следует

Курсовая работа по линейному программированию с решением

Итак, получаем первоначальный опорный план;

Курсовая работа по линейному программированию с решением

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

Курсовая работа по линейному программированию с решением

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

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

Курсовая работа по линейному программированию с решением

Поясним вычисления последней строки и последнего столбца.

Курсовая работа по линейному программированию с решением

Для векторов базиса Курсовая работа по линейному программированию с решением оценки Курсовая работа по линейному программированию с решением. Среди оценок имеются две отрицательные:

Курсовая работа по линейному программированию с решением

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

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

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

Курсовая работа по линейному программированию с решением

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

Найдём коэффициенты разложения всех векторов в новом базисе. Поставленная задача решается просто. Разрешающий элемент 5 стоит на пересечении третьей строки и столбца Курсовая работа по линейному программированию с решением. Подсчитаем новые элементы третьей строки. Для этого старые элементы этой строки (№3) разделим на разрешающий элемент 5 и запишем в строчку с номером 7 второй симплексной таблицы. Так как вектор Курсовая работа по линейному программированию с решением входит в базис, то его координаты кроме одной сделаем нулевыми. Для этого из всех элементов строки №1 вычтем соответствующие элементы строки №7 и результат запишем в строку №5. Затем все элементы строки №7 умноженные на 3 вычтем соответственно из элементов строки №2 и результат запишем в строку №6

Курсовая работа по линейному программированию с решением

Итак, получили новый опорный план:

Курсовая работа по линейному программированию с решением

и новое разложение векторов

Курсовая работа по линейному программированию с решением

в базисе

Курсовая работа по линейному программированию с решением

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

Курсовая работа по линейному программированию с решением

Для проверки плана на оптимальность вычисляем элементы строки №8:

Курсовая работа по линейному программированию с решением

Оценочная строка №8 второй симплексной таблицы содержит один отрицательный элемент. Критерий оптимальности не выполнен. Столбец Курсовая работа по линейному программированию с решением является разрешающим. Для того, чтобы определить какой вектор нужно исключить из базиса Курсовая работа по линейному программированию с решением, подсчитаем отношения координат Курсовая работа по линейному программированию с решением к элементам Курсовая работа по линейному программированию с решением разрешающего столбца Курсовая работа по линейному программированию с решением, то есть

Курсовая работа по линейному программированию с решением
Курсовая работа по линейному программированию с решением

Выбираем Курсовая работа по линейному программированию с решением, что соответствует строке №6, которая является разрешающей. Из базиса исключаем вектор Курсовая работа по линейному программированию с решением, вместо него вводим вектор Курсовая работа по линейному программированию с решением. Новый базис состоит из векторов Курсовая работа по линейному программированию с решением. Элемент

Курсовая работа по линейному программированию с решением

стоящий на пересечении разрешающей строки и разрешающего

столбца, является разрешающим. Новый опорный план имеет вид:

Курсовая работа по линейному программированию с решением

Аналогично как в прошлый раз, строим третью симплексную таблицу. Все элементы строки №6 делим на разрешающий элемент Курсовая работа по линейному программированию с решением и записываем в строку №10. Все координаты вектора Курсовая работа по линейному программированию с решением, кроме одного, должны обратится в нуль. Для этого все элементы строки №10 умножим на Курсовая работа по линейному программированию с решением и вычтем из соответствующих элементов строки №5, результат запишем в строку №9. Затем все элементы строки №10 умножим на Курсовая работа по линейному программированию с решением и вычтем из соответствующих элементов строки №7, результат запишем в строку №11.

Курсовая работа по линейному программированию с решением

Вычислим элементы строки №12:

Курсовая работа по линейному программированию с решением
Курсовая работа по линейному программированию с решением

Оценочная строка №12 не содержит отрицательных элементов. Критерий оптимальности выполнен. Значит,

Курсовая работа по линейному программированию с решением

оптимальное базисное решение, при котором функция цели

Курсовая работа по линейному программированию с решением

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

Курсовая работа по линейному программированию с решением

решение задачи; наибольшая прибыль

Курсовая работа по линейному программированию с решением

Ответ: план производства изделий Курсовая работа по линейному программированию с решением и Курсовая работа по линейному программированию с решением таков: наибольшая прибыль от реализации изделий — 70 денежных единиц будет при производстве 15 изделий Курсовая работа по линейному программированию с решением и 5 изделий Курсовая работа по линейному программированию с решением.

Возможно эта страница вам будет полезна:

Примеры решения задач по математическому программированию

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

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

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

Курсовая работа по линейному программированию с решением

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

Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое груз перевозится; 2) для решения задачи использовать методы: 1) северо-западного угла, 2) минимальной стоимости и 3) потенциалов.

Возможно эта страница вам будет полезна:

Заказать работу по математическому программированию

Решение:

1-ый способ решения (метод северо-западного угла)

Не учитывая стоимости перевозки, начинаем удовлетворение потребностей первого потребителя Курсовая работа по линейному программированию с решением за счет запаса поставщика Курсовая работа по линейному программированию с решением. Для этого сравниваем Курсовая работа по линейному программированию с решением. Запас Курсовая работа по линейному программированию с решением полностью выбираем ( в левый угол клетки Курсовая работа по линейному программированию с решением записываем 100). Остальная потребность Курсовая работа по линейному программированию с решением выбирается из запаса второго поставщика Курсовая работа по линейному программированию с решением ( в левый угол клетки Курсовая работа по линейному программированию с решением записываем 100). Потребность Курсовая работа по линейному программированию с решением удовлетворена. Теперь удовлетворяем потребности Курсовая работа по линейному программированию с решением. Ему нужно 200 тонн груза, а у поставщика Курсовая работа по линейному программированию с решением осталось 150. Выбираем этот груз потребителю Курсовая работа по линейному программированию с решением, недостающие 50 тонн груза выбираем у поставщика Курсовая работа по линейному программированию с решением и т. д. Процесс продолжаем до тех пор пока не удовлетворим всех потребителей.

Курсовая работа по линейному программированию с решением
Курсовая работа по линейному программированию с решением

Как следует из таблицы распределение груза производится из левого верхнего угла и следует в правый нижний угол, видимо поэтому, такой процесс называется методом северо-западного угла.

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

Найдём общую стоимость составленного плана как сумму произведений объёмов перевозок на соответствующие стоимости в этих же клетках:

Курсовая работа по линейному программированию с решением

Ответ: план представлен таблицей, общая стоимость всех перевозок 6950(ед.стоимости).

Возможно эта страница вам будет полезна:

Помощь по математическому программированию

2-ой способ решения (метод минимальной стоимости)

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

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

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

Курсовая работа по линейному программированию с решением
Курсовая работа по линейному программированию с решением

Найдём общую стоимость составленного плана как сумму произведений объёмов перевозок на соответствующие стоимости в этих же клетках:

Курсовая работа по линейному программированию с решением

Ответ: план представлен таблицей, общая стоимость всех перевозок 4300(ед.стоимости).

Возможно эта страница вам будет полезна:

Задачи математического программирования

3-ий способ решения (метод потенциалов)

В качестве первоначального плана возьмём план, полученный методом минимальной стоимости

Курсовая работа по линейному программированию с решением

Критерий оптимальности. Чтобы план был оптимальным, необходимо выполнение следующих условий:

а) для каждой занятой клетки сумма потенциалов должна быть равна стоимости Курсовая работа по линейному программированию с решением единицы перевозки груза, стоящей в этой клетке

Курсовая работа по линейному программированию с решением

б) для каждой незанятой клетки сумма потенциалов должна быть не больше стоимости Курсовая работа по линейному программированию с решением единицы перевозки груза, стоящей в этой клетке

Курсовая работа по линейному программированию с решением

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

Таким образом, для проверки плана на оптимальность необходимо построить систему потенциалов.

Возможно эта страница вам будет полезна:

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

Построение системы потенциалов для плана

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

Курсовая работа по линейному программированию с решением

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

Уравнений на одно меньше, чем число неизвестных, поэтому система имеет бесчисленное множество решений и одному неизвестному придают произвольное значение (обычно нулевое). После этого определяются остальные потенциалы.

В таблице 7 занятых клеток

Курсовая работа по линейному программированию с решением

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

Курсовая работа по линейному программированию с решением
Курсовая работа по линейному программированию с решением

Потенциалы Курсовая работа по линейному программированию с решением и Курсовая работа по линейному программированию с решением остались неопределёнными, это произошло потому, что опорный план вырожденный. Введем клетку с нулевыми перевозками, которую будем называть фиктивно занятой. Фиктивно занятую клетку надо сделать в строке Курсовая работа по линейному программированию с решением или в столбце Курсовая работа по линейному программированию с решением. Задача решается на минимизацию, поэтому целесообразно взять клетку с наименьшей стоимостью Курсовая работа по линейному программированию с решением (см. следующую таблицу).

Курсовая работа по линейному программированию с решением

В этой клетке Курсовая работа по линейному программированию с решением или Курсовая работа по линейному программированию с решением, значит, Курсовая работа по линейному программированию с решением. Далее из клетки Курсовая работа по линейному программированию с решением находим Курсовая работа по линейному программированию с решением или Курсовая работа по линейному программированию с решением, отсюда Курсовая работа по линейному программированию с решением. Система потенциалов построена.

2) Проверка выполнения условия оптимальности:

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

Курсовая работа по линейному программированию с решением

Если для всех незанятых клеток выполняется это условие, то план

оптимальный. Если для некоторых клеток и

Курсовая работа по линейному программированию с решением

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

Курсовая работа по линейному программированию с решением

и записываем в нижний левый угол этой клетки.

Курсовая работа по линейному программированию с решением
Курсовая работа по линейному программированию с решением

Это клетки

Курсовая работа по линейному программированию с решением

Таким образом, имеются три клетки, в которых нарушено условие оптимальности; разности соответственно равны 1,6 и 1.

3) Выбор клетки, в которую необходимо послать перевозку:

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

4) Построение цикла и определение величины перераспределения:

Отмечаем знаком (+) незанятую клетку Курсовая работа по линейному программированию с решением. До этого в таблице было Курсовая работа по линейному программированию с решением занятых клеток, которые составляли базис. Теперь в таблице стало Курсовая работа по линейному программированию с решением занятых клеток (линейно зависимых), поэтому должен существовать замкнутый цикл. Намечаем его пунктиром, поочерёдно расставляем знаки (+) и (-) на поворотах, начиная с клетки Курсовая работа по линейному программированию с решением.

Курсовая работа по линейному программированию с решением

Затем находим Курсовая работа по линейному программированию с решением, где Курсовая работа по линейному программированию с решением — перевозки, стоящие в вершинах цикла, отмеченные знаком (-). Величина Курсовая работа по линейному программированию с решением определяет количество груза, которое надо перераспределить по циклу. Величина Курсовая работа по линейному программированию с решением прибавляется к перевозкам, отмеченным знаком (+), и вычитается от перевозок, отмеченным знаком (-). Имеем в Курсовая работа по линейному программированию с решением. Следовательно, нулевую перевозку перемещаем в клетку Курсовая работа по линейному программированию с решением, остальные не изменяются.

В результате получен новый опорный план, который снова подлежит проверке на оптимальность.

5) Изменение системы потенциалов:

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

Курсовая работа по линейному программированию с решением

на самом деле

Курсовая работа по линейному программированию с решением

следовательно, потенциалы нужно уменьшать. Лучше уменьшить Курсовая работа по линейному программированию с решением на 6. Надо теперь переоценить потенциалы в клетке Курсовая работа по линейному программированию с решением. Имеем Курсовая работа по линейному программированию с решением или Курсовая работа по линейному программированию с решением, откуда следует Курсовая работа по линейному программированию с решением ( см. следующую таблицу).

Курсовая работа по линейному программированию с решением

Проверяем на оптимальность незанятые клетки. В первой строке клетки Курсовая работа по линейному программированию с решением, во второй строке клетки Курсовая работа по линейному программированию с решением не удовлетворяют условию оптимальности; находим для них величины разностей Курсовая работа по линейному программированию с решением и записываем в нижние левые углы этих клеток. Максимум разности находится в клетке Курсовая работа по линейному программированию с решением, поэтому эта клетка подлежит загрузке; отмечаем эту клетку знаком (+) и строим цикл ( см. следующую таблицу)

Курсовая работа по линейному программированию с решением

Затем находим по клеткам, отмеченным знаком (-), величину #=min (100;50;50)=50. Перераспределяем перевозки: прибавляем 50 единиц груза в клетки со знаком (+) и вычитаем такой же груз из клеток со знаком (-). Получим следующую таблицу

Курсовая работа по линейному программированию с решением

В полученном опорном плане изменяем систему потенциалов. У нас появилась новая клетка с грузом Курсовая работа по линейному программированию с решением.Чтобы выполнялось условие Курсовая работа по линейному программированию с решением, лучше уменьшить потенциал Курсовая работа по линейному программированию с решением, оставив неизменным потенциал Курсовая работа по линейному программированию с решением. В последнем столбце Курсовая работа по линейному программированию с решением есть ещё одна клетка с грузом Курсовая работа по линейному программированию с решением, в которой должно выполняться условие Курсовая работа по линейному программированию с решением. Так как Курсовая работа по линейному программированию с решением. Система потенциалов установлена. Проверяем незанятые клетки на оптимальность.

Клетки Курсовая работа по линейному программированию с решением не удовлетворяют условию оптимальности; находим для них величины разностей Курсовая работа по линейному программированию с решением и записываем в нижние левые углы этих клеток. Максимум разности находится в клетке Курсовая работа по линейному программированию с решением, поэтому эта клетка подлежит загрузке; отмечаем эту клетку знаком (+) и строим цикл ( см. следующую таблицу)

Курсовая работа по линейному программированию с решением

Находим величину

Курсовая работа по линейному программированию с решением

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

Курсовая работа по линейному программированию с решением

Пересчёт потенциалов: из клетки Курсовая работа по линейному программированию с решением получим Курсовая работа по линейному программированию с решением; из клетки Курсовая работа по линейному программированию с решением следует Курсовая работа по линейному программированию с решением; из клетки Курсовая работа по линейному программированию с решением вычислим Курсовая работа по линейному программированию с решением.

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

Найдём общую стоимость составленного плана как сумму произведений объёмов перевозок на соответствующие стоимости в этих же клетках:

Курсовая работа по линейному программированию с решением

Ответ: план представлен таблицей, общая стоимость всех перевозок 4150(ед.стоимости).

Возможно эти страницы вам будут полезны:

  1. Решение задач по линейному программированиюМетоды решения задач линейного программированияГрафическое решение задач линейного программированияГрафический метод решения задач линейного программированияЗаказать работу по линейному программированиюПомощь по линейному программированиюКонтрольная работа по линейному программированиюЛинейное программирование в Excel