Referat.me

Название: Транспортная задача и задача об использовании сырья

Вид работы: реферат

Рубрика: Математика

Размер файла: 98.43 Kb

Скачать файл: referat.me-216174.docx

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

Транспортная задача и задача об использовании сырья

Транспортная задача и задача об использовании сырья

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

75 5 3
83 4 7
50 1 5
4 5

Геометрический способ.

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

Цель задачи (максимализация прибыли) запишется в виде

Структура всех трёх ограничений одинакова

Перейдём из неравенств к уравнениям

Построим прямые на плоскости

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

.

Симплекс метод.

Приведём систему неравенств к системе уравнений

Целевая функция – функция прибыли

Составим симплекс таблицу:

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

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

- Третье ограничение запишем в третью строку

Целевую функцию запишем в строку

Б З
75 5 3 1 0 0
83 4 7 0 1 0
50 1 5 0 0 1
0 0 0 0

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

Проведём одну интеракцию метода замещения Жордано-Гаусса. Столбцы. Разрешающий элемент

равен поделим третью строку на 5, столбец сделаем единичным для этого третью строку умножим на и прибавим к первой строке, третью строку умножим на и сложим со второй строкой; третью строку сложим со строкой . Получим новую симплексную таблицу

Б З
45 0 1 0
13 0 0 1
10 1 0 0
50 0 0 0 1

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

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

Б З
23 0 0 1
5 1 0 0
9 0 1 0
65 0 0 0

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

Б З
13 0 0 1
12 1 0 0
5 0 1 0
73 0 0 0

Так как в строке все элементы неотрицательны, то найден оптимальный план

Оптимальный план найденный геометрическим способом и симплексным методом совпадают. Предприятию необходимо выпускать 12 единиц продукции первого вида и 5 единиц продукции второго вида. В этом случае предприятие получит прибыль денежных единиц.

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

60

50

85

75

65 8 10 6

5

65

80

4

30

3

50

5 9
35

11

25

4 4

8

10

90

5

5

5

3

85

6

Проверим необходимое и достаточное условие разрешимости задачи

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

Используя метод наименьшей стоимости заполним таблицу.

Среди тарифов наилучшим является и . Направим например,

в клетку

в клетку

в клетку

в клетку

в клетку

в клетку

в клетку

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

Определим значение целевой функции первого опорного плана

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

Найдём потенциалы и по занятым клеткам таблицы

Пусть , тогда:

Подсчитаем оценки свободных клеток

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

Переходим к его улучшению. Для клетки строим цикл перераспределения

В результате получили новый опорный план

60

50

85

75

65 8 10 6

5

65

80

4

55

3

25

5 9
35

11

4

25

4

8

10

90

5

5

5

3

85

6

Определим значение целевой функции

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

Подсчитаем оценки свободных клеток

План близок к оптимальному.

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

Похожие работы

  • Решение задачи линейного программирования симплексным методом

    ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение Высшего профессионального образования «Волгоградский государственный технический университет»

  • Типовой расчет по ЭМММ

    Типовой расчет Решение задач по дисциплине ЭМММ Вариант №23 Выполнил: Проверил: Екатеринбург 2009 Математическая модель ЗЛП Мат. модель ЗЛП называется стандартной, если система ограничений представлена в виде неравенств, а функция минимизируется или максимизируется

  • Математические программирование

    ЛАБОРАТОРНАЯ РАБОТА №2 по мат.программированию «Графический и симплексный методы решения ОЗЛП» Для изготовления 2-х различных изделий А и В используется 3 вида сырья. На производство единицы изделия А требуется затратить сырья 1-го вида а1 кг, сырья 2-го вида – а2 кг, сырья 3-го вида – а3 кг. На производство единицы изделия В требуется затратить сырья 1-го вида в1 кг, сырья 2-го вида – в2 кг, сырья 3-го вида – в3 кг.

  • Решение задачи про кондитерскую фабрику

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

  • Симплекс-метод

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

  • Курсовая работа по прикладной математике

    Министерство общего и профессионального образования Российской Федерации ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ ИНСТИТУТ ЗАОЧНОГО ОБУЧЕНИЯ Контрольная работа

  • Задачи по Математике 3

    Задача 1 Решить графическим методом задачу линейного программирования А) найти область допустимых значений многоугольник решений Б) найти оптимумы целевой функции

  • Математика

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

  • Решение задач по прикладной математике

    МОСКОВСКАЯ АКАДЕМИЯ ЭКОНОМИКИ И ПРАВА РЯЗАНСКИЙ ФИЛИАЛ КОНТРОЛЬНАЯ РАБОТА По курсу: «ПРИКЛАДНАЯ МАТЕМАТИКА» Выполнил: ст-т гр. ЭБ - 241 Лебедев Н. В.

  • Елементи інформаційних технологій в математичному програмуванні

    Завдання 1 Розв'язати графічним способом при умовах: Розв'язування Зобразимо розв’язок системи нерівностей та вектор F (1;2): Максимум функції досягається в точці А: