5. Отчет должен содержать.

1.Наименование и цель работы;

2. Алгоритм расчета задачи по венгерскому методу;

3. Подробную блок-схему метода решения;

4. Исходные данные для расчета;

5. Ручной расчет задачи по варианту задания;

б. Результаты расчета на ПЭВМ ( распечатку);

7. Выводы.

6.Список используемых источников.

6.1.3айченко Ю.П. “Исследование операций”.Вища школа,1975-320С.

6.2. Дехтярев Ю.И. “И исследование операций”.высшая школа,М.:1986,-320С.

6.3. Кудрявцев Е.М. “Исследование операций в задачах, алгоритмах и программах.Радио и связь”,М.:1984-184С.

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

Цель работы: практическое освоение технологии решения транспортной задачи линейного программирования различными методами с использованием ПЭВМ.

1. Постановка задачи.

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

В пунктах производства А1, А2, … , Аm имеются запасы какого-то однородного продукта в количествах а1, а2, … , аm единиц. Необходимость в этом продукте в пунктах потребления В1, В2, … ,Вn выражается соответственно величинами b1, b2, … , bn. Из каждого пункта производства возможна транспортировка продукта в любой пункт потребления. Транспортные издержки на перевозку единицы продукции из пункта Ai в пункт Bj заданы и составляют

i = 1, ... , m; j = 1, ... , n.

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

2. Математическая формулировка задачи.

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

Для составления математической модели задачи введём переменные x_ij>=0 , i=1,...,m, j=1,...,n обозначающие количество груза перевозимого из i-го пункта производства в j-й пункт потребления. Требуется найти множество переменных x_ij>=0, минимизирующих функцию

(3.1)

и удовлетворяющую условиям

, i=1,...,m (3.2)

, j=1,...,n (3.3)

Транспортная задача представляет собой задачу ЛП с числом переменных m*n и числом ограничений равенств m+n.

Набор переменных (x_ij), удовлетворяющий условиям (3.2) и (3.3) записывают в виде матрицы

Матрицу X называют планом привозок Т-задачи, а переменные x_ij – перевозками.

План X^опт, при котором значение целевой функции минимально, называется оптимальным. Матрица , i=1,...,m, j=1,...,n, называется матрицей транспортных издержек.

На практике существует два вида задач:

(3.4)

(3.5)

Задача (3.4) называется Т-задачей закрытого типа, а задача (3.5) – открытого. Задача (3.5) приводится к задаче закрытого типа путём введения дополнительного пункта производства или потребления, в зависимости от условия и решается как задача закрытого типа.

Решение Т-задачи состоит из следующих основных этапов: определение исходного опорного плана задачи; оценка этого плана; переход к следующему, лучшему плану путём замены одной из базисных переменных на свободную.