Нахождение оптимального плана транспортной задачи распределительным методом
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?ащаемся к пункту 4.
Если при решении транспортной задачи целевая функция стремится к min, то алгебраические суммы по всем контурам должны быть положительными или равными нулю.
Если целевая функция стремится к max, то алгебраические суммы по всем контурам должны быть отрицательными или равными нулю.
Если план перевозок не оптимальный, то перераспределение выполняется следующим образом:
а)выбирается контур, для которого нарушено условие оптимальности, если целевая функция стремится к min, то выбирается отрицательный контур. Если таких контуров несколько, то выбирается тот, который больше по модулю;
б)в вершинах выбранного контура расставляются фактические перевозки с теми знаками, которые были указаны при вычислении коэффициентов. Рассматривается вершины только с отрицательными значениями. Выбирается вершина с минимальным по модулю отрицательным значением, и оно вычитается из всех вершин контура. Полученный опорный план применяется без учета знаков;
в)проверяется сбалансированность перевозок по столбцам и строкам;
г)заново рассчитывается алгебраические суммы (по стоимости) для всех контуров;
д)проверяется условие оптимальности.
2.3 Описание программы
Код программы был написан в программной среде Borland Delphi7.
Программа состоит из трех окон.
Для запуска программу нужно два раза кликнуть левой кнопкой мыши по файлу "transportnaya zadacha. exe". При запуске программы открывается главное окно "Решение транспортной задачи распределительным методом =)", в котором необходимо выбрать количество потребителей и количество производителей, метод нахождения опорного плана, после этого ввести данные и нажать на кнопку "Рассчитать". Главное окно программы представлено на рисунке 1.
При нажатии кнопки "Рассчитать" происходит вычисление оптимального плана поставленной задачи распределительным методом.
. Таблица для ввода данных
. Об исполнителе работы
. Кнопка "Рассчитать"
. Выбор опорного плана
. Количество столбцов
. Количество строк
Рисунок 1 - Главное окно программы
На рисунке 2 изображено окно на вкладке "Опорный план", а на рисунке 3 - окно на вкладке "Оптимальный план"
. Значение целевой функции опорного плана
. Опорный план
. Вкладка "Оптимальный план"
Рисунок 2 - Окно вывода информации, вкладка "Опорный план"
. Значение целевой функции оптимального плана
. Оптимальный план
. Вкладка "Опорный план"
Рисунок 3 - Окно вывода информации, вкладка "Оптимальный план"
На рисунке 4 представлено окно программы "Info"
Рисунок 4 - Info
2.4 Тестирование программы
После нажатия на кнопку "Рассчитать" программа составит опорный план, на ваш выбор, высчитает значение целевой функции и на основе опорного плана построит оптимальный план и найдет оптимальное значение целевой функции.
В программе предусмотрена защита на ввод, т.е. нельзя ввести буквы, символы, какие-то знаки, так как программа предназначена для работы с целыми и неотрицательными числами.
Если не заполнить матрицу или заполнить ее не до конца, а также заполнить нулями, то программа выдаст сообщение "Заполните пустые клетки или уберите нули", рисунок 5.
Рисунок 5 - Заполните пустые клетки или уберите нули
Если введенная задача не сбалансирована, то выдаст сообщение "Задача не сбалансирована, приведите ее к сбалансированному виду", рисунок 6.
Рисунок 6 - Задача не сбалансирована, приведите ее к сбалансированному виду
Для тестирования программы возьмем задачу из пункта "Постановка задачи", исходные данные которой представлены в таблице 1 и решим с помощью написанной программы.
2.5 Анализ полученных результатов
Результаты решения задачи программно и вручную совпадают. Ниже представлены решения.
Решение, которое было произведено вручную:
Опорный план был рассчитан методом "Минимальных элементов".
Таблица 2 - Опорный план методом "Минимальных элементов"
26614841288101464
Теперь найдем пустые клети в опорном плане.
Пустые клетки:
a14; a22; a23; a31; a33; a34.
Строим контуры для всех пустых клеток
Контур a14:
,4; 2,4; 2,1; 1,1
Контур a22:
,2; 2,1; 1,1; 1,2
Контур a23:
,3; 2,1; 1,1; 1,3
Контур a31:
,1; 1,1; 1,2; 3,2
Контур a33:
,3; 3,2; 1,2; 3,2
Контур a34:
,4; 3,2; 1,2; 1,1; 2,1; 2,4
Вершинам построенных контуров присвоим значение матрицы данных, чередуя знаки.
Проведем оценку контуров.
Контур a14: С1=7+ (-2) +3+ (-6) =2
Контур a22: С2=6+ (-3) +6+ (-5) =4
Контур a23: С3=4+ (-3) +6+ (-8) =-1
Контур a31: С4=9+ (-6) +5+ (-1) =7
Контур a33: С5=3+ (-1) +5+ (-8) =-1
Контур a34: С6=6+ (-1) +5+ (-6) +3+ (-2) =5
Следующим шагом выбираем максимальный отрицательный элемент по модулю. Так как у нас |-1|=|-1| то выбираем контур a23.
Берем опорный план и присваиваем элементам в контуре a23 знаки чередуя их, начиная с a23 (Таблица 3)
Таблица 3 - Опорный план с расставленными знаками
26-614-841288101464
Теперь из отрицательных чисел мы выбираем минимальное по модулю, в данном случае это (-6). (-6) алгебраически вычтем из всех вершин и получим следующий опорный план (Таблица 4)
Таблица 4 - Опорный план после распределения
86142641288101464
Нам нужно сейчас снова найти пустые клетки
Это a13; a14; a22; a31; a33; a34
Найдем контур для каждого пу